What is a logic clock. Why are logic clock required in distributed sytem. How does Lamport synchronize logical clocks? Which event are said to be constructed in Lamport Timestamp? May 2017) (10 Marks)

Q. What is a logic clock. Why are logic clock required in distributed sytem. How does Lamport  synchronize logical clocks? Which event are said to be constructed in Lamport Timestamp?

Ans -  A 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 . 

Why logical clock ?

People use physical time to order events. For example, we say that an event at 8:15 AM occurs before an event at 8:16 AM. In distributed systems, physical clocks are not always precise, so we can't rely on physical time to order events. Instead, we can use logical clocks to create a partial or total ordering of events.

 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→q and q→r, then p→r.
2. If two events, a and b, occur in different processes which not at all exchange messages amongst them, then a→b is not true, but neither is b→ a which is antisymmetry.

 

The algorithm follows some simple rules:

1.  A process increments its counter before each event in that process.
2.  When a process sends a message, it includes its counter value with the message.
3.  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.

 

How lamport synchronize clocks

 

 

 

Concurrent events in Lamport timestamps
 

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 100toanaccount(initialvalue=1000)
• Update 2: add 1% interest to account.
• Lamport's logical clocks can be used to implement totally-ordered multicast in a completely distributed fashionLamport's logical clocks can be used to implement totally-ordered multicast in a completely distributed fashion.

 

Causality

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