- 2070 Asar · 2+6 marks
Physical vs logical clocks; Lamport
Short answer
Physical clocks measure real time and need synchronization; logical clocks are counters that only order events. Lamport's algorithm increments a counter before each event, attaches it to messages, and on receive takes max with the received timestamp plus one. Benefits: simple and small; drawback: C(a) < C(b) does not imply causality.
Compare physical clocks and logical clocks with its implementation semantics. Describe Lamport's timestamp algorithm with its benefits and drawbacks.
Physical vs logical clocks
| Point | Physical clock | Logical clock |
|---|---|---|
| Measures | Real time (UTC) | Order of events only |
| Implementation | Hardware oscillator, synchronised by Cristian, Berkeley, NTP | Software counter (integer or vector) |
| Value meaning | Time of day | Count, no relation to real time |
| Drift | Drifts, needs periodic correction | No drift issue |
| Needs time server | Usually yes | No |
| Semantics | Event a before b if time(a) < time(b) | a → b implies C(a) < C(b) |
| Accuracy | Limited by network delay | Consistent with causality (exact, if and only if, only for vector clocks) |
| Use | Timestamps, billing, real-time tasks | Ordering, mutual exclusion, consistency |
Lamport's timestamp algorithm
Each process Pi has a counter Ci (initially 0).
- Before every event, Ci = Ci + 1.
- A message is sent with timestamp t = Ci.
- On receipt of (m, t): Ci = max(Ci, t) + 1.
To get a total order, ties are broken by process id: (Ci, i).
Example: P1 sends m at C=3 (timestamp 3). P2 has C=1; on receipt P2 sets C = max(1,3)+1 = 4, so the receive is later than the send.
Benefits: simple; no physical clock needed; small overhead (one integer); gives an order consistent with causality; useful for distributed mutual exclusion and totally ordered multicast.
Drawbacks: C(a) < C(b) does not imply a → b; concurrent events cannot be identified (vector clocks fix this); no link with real time; a total order can be artificial.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Lamport's logical clock algorithm · Distributed System, chapter 5 · asked 5×
- Physical/logical clocks; NTP and Berkeley · Distributed System, chapter 5
- Physical vs logical clock; sync method · Distributed System, chapter 5 · asked 2×
- Physical clock synchronization algorithm · Distributed System, chapter 5
- Synchronising physical clock using logical clock · Distributed System, chapter 5 · asked 2×
- Lamport algorithm for mutual exclusion · Distributed System, chapter 6
- Logical and physical address bits · Operating System, chapter 4
- Structural model vs implementation model · Object Oriented Analysis and Design, chapter 1