Lamport Clock Algorithm Implementation
You'll learn how to correctly increment and update Lamport timestamps when your distributed system processes events and sends/receives messages.
The Core Mechanism
Lamport timestamps give each event in a distributed system a logical clock value. The algorithm has three simple rules that maintain the happens-before relationship we studied earlier:
Rule 1: Local Event Increment
Before processing any local event (computation, I/O, etc.), a process increments its own logical clock by 1.
Rule 2: Send Event
When sending a message, increment your clock first, then attach the current timestamp to the message.
Rule 3: Receive Event
When receiving a message with timestamp T_msg:
- Set your clock to
max(your_clock, T_msg) + 1 - This ensures your clock is ahead of both your previous value and the sender's timestamp
Why This Works
Think of Lamport clocks like version numbers on a collaborative document. When you edit locally, you bump your version (+1). When you receive someone else's changes, you make sure your next version is higher than theirs and yours, avoiding any conflict.
The max() operation in Rule 3 is crucial—it handles clock skew. If you receive a message from the "future" (their clock is ahead), you jump forward. If it's from the "past," you just increment normally.
Implementation Pattern
# Each process maintains:
clock = 0
# Local event:
clock = clock + 1
# Sending message:
clock = clock + 1
send(message, clock)
# Receiving message (timestamp, data):
clock = max(clock, received_timestamp) + 1
Key Takeaway: Lamport clock implementation requires incrementing before local events and sends, and taking the maximum-plus-one when receiving messages to preserve causal ordering across distributed processes.