Mumbai University > Computer Science > Sem 8 > Parallel And Distributed System

Logical clock:

Is a mechanism for capturing chronological and causal relationships in a distributed system. Distributed systems may have no physically synchronous global clock, so a logical clock allows global ordering on events from different processes in such systems. The first implementation, the Lamport timestamps, was proposed by Leslie Lamport in 1978.

Lamport's Logical Clocks:

The algorithm of Lamport timestamps is a simple algorithm used to determine the order of events in a distributed computer system. As different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a partial ordering of events with minimal overhead, and conceptually provide a starting point for the more advanced vector clock method.

For synchronization of logical clocks, Lamport established a relation termed as "happens-before" relation.

1. Happens- before relation is a transitive relation, therefore if p$\rightarrow$q and q$\rightarrow$r, then p$\rightarrow$r.
2. If two events, a and b, occur in different processes which not at all exchange messages amongst them, then a$\rightarrow$b is not true, but neither is b$\rightarrow$a which is antisymmetry.

The algorithm follows some simple rules:

• A process increments its counter before each event in that process.
• When a process sends a message, it includes its counter value with the message.
• On receiving a message, the counter of the recipient is updated, if necessary, to the greater of its current counter and the timestamp in the received message. The counter is then incremented by 1 before the message is considered received.

Example how lamport synchronize clocks

Concurrent events in Lamport timestamps.

1. Totally Ordered Multicast

   • We need to guarantee that concurrent updates on a replicated database are seen in the same order everywhere. This requires a totally-ordered multicast.
   • Update 1: add $100 to an account (initial value = $1000)
   • Update 2: add 1% interest to account.
   • Lamport's logical clocks can be used to implement totally-ordered multicast in a completely distributed fashion
   • Lamport's logical clocks can be used to implement totally-ordered multicast in a completely distributed fashion

1. Causality

• Lamport's logical clocks: If A $\rightarrow$ B then L(A) < L(B), Reverse is not true. Nothing can be said about events by comparing timestamps.
• Need to capture causality: If A $\rightarrow$ B then A causally precedes B. Need a timestamping mechanism such that: T(A) < T(B) if A causally precedes B