0
19kviews
What is a logic clock? Why are logic clocks required in distributed systems? How does Lamport synchronize logical clocks? Which events are said to be concurrent in Lamport timestamps.

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

1 Answer
0
713views

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 enter image description here

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

enter image description here

  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

enter image description here

Please log in to add an answer.