Logical Clock: Lamport Clock and Vector Clock in Distributed System – Logical Time-Lamport’s and Vector Algorithm

Logical Clock: Lamport Clock and Vector Clock in Distributed System – Logical Time-Lamport’s and Vector Algorithm. Lampor’t Clock and Vector Clock With Algorithm in Distributed System.

https://www.gyanodhan.com/video/7A2.%20Computer%20Science/Distributed%20Computing/320.%20Day%2003%20Part%2003%20Lamport%20Clock%20in%20Distributed%20System.mp4

Logical Clock In Distributed System Lamport Logical Clock In Distributed System Difference Between Logical Clock And Vector Clock Advantages Of Vector Clock Over Lamport Clock Lamport Clocks And Vector Clocks Lamport’s And Vector Algorithm In Distributed System. Physical Clock In Distributed System Lamport Logical Clock Vs Vector Clock Global Clock In Distributed System Lamport Logical Clock Video Lecture Disadvantages Of Lamport Logical Clock Logical Time In Distributed System Lamport Clock Example Lamport Logical Clock Program In Python.

Logical Clocks: Lamport Clock and Vector Clock in Distributed Systems

In distributed systems, there is no global clock to keep track of events, so we use logical clocks to maintain the ordering of events. Two widely used logical clocks are:

1. Lamport Timestamps (Lamport Clock)
2. Vector Clocks

Let’s dive into how they work and their differences.

1. What is a Logical Clock?

A logical clock is a mechanism to assign timestamps to events in a distributed system without relying on physical clocks. It helps to maintain event order across different processes.

Two key conditions for logical clocks:
Causal Order Condition: If an event A happens before event B, then timestamp(A) < timestamp(B).
Consistency: The logical clock must be consistent with the actual order of events in a system.

2. Lamport Clock (Lamport Timestamps)

Concept

 Proposed by Leslie Lamport (1978), the Lamport Clock provides a way to order events in a distributed system.
 It does not detect concurrent events.
 Every process maintains a counter that is incremented for each event and synchronized using message passing.

Lamport’s Algorithm (Step-by-Step)

1. Initialization:

Each process P maintains a logical clock L(P), initialized to 0.

2. Event Execution:

Whenever a process executes an event, it increments its clock:

$$L(P)=L(P)+1$$

3. Sending a Message:

When a process P sends a message to another process Q, it includes its current timestamp in the message:

$$M(T)=L(P)$$

4. Receiving a Message:

When process Q receives a message M(T) from process P, it updates its clock as:

$$L(Q)=\max (L(Q),M(T))+1$$

Example of Lamport Timestamps

Consider three processes (P1, P2, P3) with events labeled as A, B, C, etc.

Initial State:

Message Passing & Timestamp Updates

P1 sends message M1 to P2:

• P1’s clock: 1 → increments → 2
• P2 receives message: Updates its clock: max(2, 1) + 1 = 3

P2 sends message M2 to P3:

• P2’s clock: 3 → increments → 4
• P3 receives message: Updates its clock: max(4, 1) + 1 = 5

Final Timestamps:

Problem with Lamport Clocks:
 Lamport timestamps do not capture concurrency (i.e., whether two events happened at the same time).

3. Vector Clocks (Improved Logical Clock)

Concept

Vector clocks solve the concurrency problem by maintaining a vector of logical clocks, one for each process.
 Each process maintains an array (vector) of timestamps to track event order.

Vector Clock Algorithm (Step-by-Step)

1. Initialization:

Each process Pᵢ maintains a vector clock V(Pᵢ) initialized to [0,0,…,0].

2. Event Execution:

Whenever a process executes an event, it increments its own clock in the vector:

V(Pi)[i]=V(Pi)[i]+1V(Pᵢ)[i] = V(Pᵢ)[i] + 1V(Pi​)[i]=V(Pi​)[i]+1

3. Sending a Message:

When a process Pᵢ sends a message to another process Pⱼ, it attaches its vector timestamp V(Pᵢ) to the message.

4. Receiving a Message:

When process Pⱼ receives a message from Pᵢ, it updates its vector clock as:

V(Pj)[k]=max⁡(V(Pj)[k],V(Pi)[k])∀kV(Pⱼ)[k] = \max(V(Pⱼ)[k], V(Pᵢ)[k]) \quad \forall kV(Pj​)[k]=max(V(Pj​)[k],V(Pi​)[k])∀k

Then, it increments its own entry:

V(Pj)[j]=V(Pj)[j]+1V(Pⱼ)[j] = V(Pⱼ)[j] + 1V(Pj​)[j]=V(Pj​)[j]+1

Example of Vector Clocks

Consider three processes (P1, P2, P3).

Initial State:

Each process starts with [0,0,0].

Message Passing & Vector Updates

P1 sends message M1 to P2:

• P1’s clock: [1,0,0] → increments → [2,0,0]
• P2 receives M1: Updates: [2,1,0]

P2 sends message M2 to P3:

• P2’s clock: [2,1,0] → increments → [2,2,0]
• P3 receives M2: Updates: [2,2,1]

Final Vector Clocks:

Vector Clocks Preserve Causal Relationships – If V(A) < V(B), then A happened before B.
They Detect Concurrency – If V(A) and V(B) are incomparable, the events are concurrent.

4. Differences: Lamport Clock vs. Vector Clock

5. Conclusion

• Lamport Clocks provide a simple way to order events but fail to detect concurrency.
• Vector Clocks solve this problem by tracking full event history at the cost of extra storage.
• Use Lamport Clocks when event ordering is enough (e.g., distributed logs, messaging).
• Use Vector Clocks for causality tracking (e.g., distributed databases, version control).

Would you like a real-world example or a Python implementation?

Logical Clock: Lamport Clock and Vector Clock in Distributed System – Logical Time-Lamport’s and Vector Algorithm

Time, Clocks, and the Ordering of Events in a Distributed System

Lecture 14: March 29 14.1 Logical and Vector Clocks