Introduction
Lamport clocks are a mechanism used in distributed systems to assign a logical timestamp to events in order to capture the order of events across different processes or nodes. Unlike physical clocks, which represent actual time, Lamport clocks are logical clocks that help establish a causal relationship between events.
Key Concepts:
- Logical Clocks: • Lamport clocks assign a numerical value (timestamp) to each event in a distributed system. • These timestamps are used to determine the order of events, rather than their actual physical time of occurrence.
- Partial Ordering: • The main purpose of Lamport clocks is to provide a partial order of events across distributed processes. • If one event causally influences another, Lamport clocks can determine this relationship.
- How Lamport Clocks Work: • Each process in the system maintains its own local counter. • When a process performs an event (e.g., sending a message, performing a computation), it increments its counter. • When a process sends a message, it includes its current counter value (timestamp) with the message. • When a process receives a message, it updates its counter to be the maximum of its current value and the received timestamp, and then increments it.
- Rules for Timestamps: • Internal Events: For any internal event within a process, the Lamport clock is incremented by 1. • Sending a Message: When a process sends a message, it increments its clock by 1 and assigns this value to the message’s timestamp. • Receiving a Message: When a process receives a message, it sets its clock to the maximum of its current clock and the received message’s timestamp, then increments by 1.
- Happens-Before Relationship (→): • Lamport clocks help establish the “happens-before” (→) relationship between events: • If event A happens before event B in the same process, then the timestamp of A is less than the timestamp of B. • If event A sends a message to event B, then the timestamp of A is less than the timestamp of B.
- Limitations: • Lamport clocks can determine the order of events, but they do not capture concurrency. • If two events have the same timestamp (in different processes), Lamport clocks cannot determine which event happened first; they are considered concurrent.
