Need of logical clock synchronization

Logical clock synchronization

Logical clock synchronization means giving every event in a distributed system a logical timestamp (counter value) so that the timestamps agree with the causal "happened-before" order (a → b implies C(a) < C(b)). It is not tied to real time and needs no time server.

Need

• Distributed systems have no global clock, and physical clocks cannot be synchronised exactly because of drift and variable message delays.
• Many applications need only the same order of events at all nodes: mutual exclusion, totally ordered multicast, replicated database updates, consistent snapshots and deadlock detection.

Example

A bank account with balance Rs 1000 is replicated at Kathmandu and Pokhara. Two clients issue two updates almost simultaneously, and each update is sent to both replicas: update 1 deposits Rs 100 and update 2 adds 1% interest. If the replicas apply them in different orders, one gets (1000 + 100) × 1.01 = 1111 and the other gets 1000 × 1.01 + 100 = 1110, so the replicas become inconsistent. Logical timestamps order the two updates, so all replicas apply them in the same order.

Lamport's algorithm

1. Each process Pi has a counter Ci = 0.
2. Before every event, Ci = Ci + 1.
3. A message carries t = Ci of the send event.
4. On receipt of (m, t): Ci = max(Ci, t) + 1.
5. For a total order use (Ci, process id); ties are broken by id.

In the example, both updates get timestamps, e.g. (5,K) and (5,P); with the tie broken by id, both replicas order K's update first, and the results agree.

Limitation: C(a) < C(b) does not prove a → b; vector clocks solve this.