Lamport's logical clock algorithm

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

 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.