Skip to main content

Clock synchronization need; Lamport

Short answer

Clock synchronization makes distributed clocks agree on time or event order. It is needed because clocks drift, making timestamps incomparable, affecting event ordering, mutual exclusion, and security. Lamport's algorithm uses a logical counter: increment on each event, timestamp messages, and on receive set counter to max(local, received)+1. Example: send at 2, receive at 3 ensures happened-before ordering.

Define clock synchronization. What is the need of clock synchronization? Explain the Lamport's clock synchronization algorithm along with an example.

Clock synchronization

Clock synchronization is the process of making the clocks of different computers in a distributed system agree, either with each other (internal) or with an external reference such as UTC (external), or, for logical clocks, agree on the order of events.

Need

  • Each machine has its own clock, and the clocks drift apart, so timestamps on different machines are not comparable.
  • Correct ordering of events and transactions (log files, banking, make build tools using file times).
  • Distributed algorithms: mutual exclusion, deadlock detection, replication, consistent snapshots.
  • Security (Kerberos ticket expiry), billing, scheduling and real-time systems.

Lamport's clock synchronization algorithm

Lamport defined the happened-before relation (→): events in one process are ordered; a message send happens before its receipt; the relation is transitive. The algorithm gives counters consistent with it.

  1. Each process Pi keeps a counter Ci, initialised to 0.
  2. Before each event Ci = Ci + 1.
  3. When Pi sends a message m, it timestamps it with t = Ci.
  4. When Pj receives (m, t), it sets Cj = max(Cj, t) + 1.

Example

 P1: a(1)---s1(2)---------------------d(5)
              \ m1(t=2)                  ^
 P2: c(1)------e(3)----s2(4)-------------+
                       m2(t=4)

P1's event a has C1 = 1, and the send of m1 has C1 = 2. P2's local event c gives C2 = 1. On receiving m1 (t=2), P2 sets C2 = max(1,2)+1 = 3 (event e). P2 sends m2 at C2 = 4. P1 (C1 = 2) receives m2 and sets C1 = max(2,4)+1 = 5 (event d). Thus send of m1 (2) < receive (3), send of m2 (4) < receive (5). Equal timestamps on different processes are ordered by process number.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Distributed System chapter 5 questions →