Synchronising physical clock using logical clock

Why synchronising physical clocks is difficult

1. Each node has its own oscillator with a different drift rate, so clocks diverge continuously.
2. Message delay is unpredictable and variable (queueing, routing, congestion), so a received time value is already old, and delays in two directions may differ.
3. There is no shared global clock or memory.
4. Time servers and links can fail; clocks themselves can be faulty.
5. A clock cannot be moved backward without breaking ordering, so adjustment must be gradual.
6. Synchronisation must be repeated and costs network traffic in large systems. Hence, perfect synchronisation is impossible; only a bounded error can be achieved.

Solving it using logical clocks

Most distributed applications need the order of events, not real time. Lamport observed that two processes need to agree on order only if they interact. Logical clocks give that order without any physical clock.

Using the happened-before relation (a → b if a precedes b in a process, or a is a send and b is its receive, plus transitivity):

1. Each process Pi keeps counter Ci, initially 0.
2. Increment Ci before every event.
3. A sent message carries timestamp t = Ci.
4. On receiving (m, t): Ci = max(Ci, t) + 1. This guarantees a → b implies C(a) < C(b). If two events get the same value, order them by process id for a total order.

Example: P1 sends m at time 5. P2 with clock 2 receives it and sets its clock to max(2,5)+1 = 6, so receive is after send even though P2's local clock was behind. Thus no physical synchronisation is needed.

If concurrent events must be identified, use vector clocks. Logical clocks therefore solve ordering problems (mutual exclusion, replicated updates, totally ordered multicast) without synchronising the physical clocks; they cannot give the actual time of day.