---
title: "Lamport's logical clock algorithm"
subject: "Distributed System"
chapter: 5
key: "semester_7/distributed_system:lamport-clock"
source: https://www.bctengineer.com/q/semester_7/distributed_system/lamport-clock
site: BCT Engineering
---

# Lamport's logical clock algorithm

Distributed System · Chapter 5: Time and State in Distributed Systems

- Asked in: 2069 Chaitra, 2+6 marks; 2073 Shrawan, 2+6 marks; 2076 Asoj; 2075 Asoj, 3 marks; Model question (asked 5 times)
- Video: [Lamport's Logical Clock Algorithm Explained | Distributed System & Computing Lectures ✅](https://www.youtube.com/watch?v=lzn6AUBHmxw) — Last moment tuitions
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/distributed_system/lamport-clock
- Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-5

## Question

Explain Lamport's logical clock (timestamp) algorithm with an example. What are its pros and cons? (Define logical and physical clocks; what do you mean by logical clock?)

## Short answer

A logical clock is a counter that orders events using the happened-before relation: each event increments it, outgoing messages carry the timestamp, and on receipt set C = max(local, received) + 1, so a→b gives C(a)<C(b). It is simple, needs no physical clocks, and provides total order, but cannot detect concurrent events or relate to real time.

## Answer

#### Physical and logical clocks
A **physical clock** is a hardware clock that measures real time (seconds). Different machines' clocks drift, so they must be synchronised. A **logical clock** is a software counter that does not measure real time; it only orders events so that if event *a* happened before event *b* then C(a) < C(b). It is based on the happened-before relation.

#### Happened-before (→)
1. If a and b are in the same process and a occurs before b, then a → b.
2. If a is the sending of a message and b is its receipt, then a → b.
3. If a → b and b → c then a → c (transitive).
Events not related by → are **concurrent**.

#### Lamport's logical clock algorithm
Each process Pi keeps a counter Ci, initially 0.
1. **Before each event** (including send), Pi does Ci = Ci + 1.
2. **On sending** message m, Pi attaches the timestamp t = Ci.
3. **On receiving** (m, t), Pi sets Ci = max(Ci, t) + 1, then delivers the message.

#### Example
```text
 P1: a(1)---b(2)------------------------e(5)
              \ m1(2)                    ^
 P2: c(1)------d(3)---------m2(4)---------+
```
P1 does a (C=1), then b = send m1 with timestamp 2. P2 does c (C=1); on receiving m1 sets C = max(1,2)+1 = 3 (event d). P2 then sends m2 with timestamp 4. When P1 (C=2) receives m2: C = max(2,4)+1 = 5 (event e). Clearly b → d and d → e, and the timestamps 2 < 3 < 5 follow the order.

#### Pros
- Simple, cheap: one integer per process and per message.
- No physical clock or time server needed.
- Gives a consistent total order of events (ties broken with process id), used in mutual exclusion and replicated databases.

#### Cons
- If C(a) < C(b) it does **not** mean a → b; concurrent events cannot be detected (solved by vector clocks).
- No relation to real time.
- Can give an order that differs from the real order, if there is outside communication.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Process P2 has C=1 and receives a message with timestamp 2. What does P2's clock become?
   A. 2
   B. 1
   C. 4
   D. 3
   Answer: D. On receipt Ci = max(Ci, t) + 1 = max(1,2)+1 = 3. (Key point: Lamport receive rule)

2. What does a Lamport logical clock guarantee?
   A. If a happened before b then C(a) < C(b)
   B. If C(a) < C(b) then a happened before b
   C. It measures real elapsed time
   D. Concurrent events always get equal timestamps
   Answer: A. Only the forward implication holds; the converse is false. (Key point: Logical clock guarantee)

3. What is the key limitation of Lamport timestamps?
   A. They require a central time server
   B. They cannot detect concurrent events because C(a) < C(b) does not mean a -> b
   C. They need a vector of N integers per message
   D. They drift away from UTC over time
   Answer: B. Lamport clocks lose causality information; vector clocks fix this. (Key point: Main drawback)

4. How is a total order obtained from Lamport timestamps when two events have the same value?
   A. Use the real clock time
   B. Discard one of the events
   C. Break ties using the process id
   D. Add a random number
   Answer: C. The pair (Ci, process id) gives a total order. (Key point: Total order)

## Related in Distributed System

- [Physical vs logical clocks; Lamport](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-physical-compare) — Distributed System, chapter 5
- [Physical/logical clocks; NTP and Berkeley](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aphysical-logical-ntp-berkeley) — Distributed System, chapter 5
- [Physical clock synchronization algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aphysical-clock-sync-algorithm) — Distributed System, chapter 5
- [Physical vs logical clock; sync method](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aphysical-clock-sync-difficulty) — Distributed System, chapter 5, asked 2×
- [Synchronising physical clock using logical clock](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Async-physical-with-logical) — Distributed System, chapter 5, asked 2×
- [Problems of Lamport's clock; vector clock](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-problems-vector-clock) — Distributed System, chapter 5, asked 2×

## Related in other subjects

- [Distribution layouts, pros/cons, improvements](https://www.bctengineer.com/question.md?key=semester_5%2Fwater_supply_engineering%3Adistribution-layouts-improvements) — Water Supply Engineering, chapter 7, asked 4×
- [Phase shift method of SSB generation: pros and cons](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Assb-phase-shift-pros-cons) — Communication Systems, chapter 2, asked 2×
- [Collective intelligence pros and cons](https://www.bctengineer.com/question.md?key=semester_8%2Finformation_system%3Acollective-intelligence-pros-cons) — Information System, chapter 4
- [Brushless excitation pros and cons](https://www.bctengineer.com/question.md?key=semester_8%2Fpower_plant_design%3Abrushless-pros-cons) — Power Plant Design, chapter 4