Course contentsShow
← Computer Science
Lesson 2629 of 2,87258. Distributed Systems BasicsFree lesson

Lamport Clock Algorithm Implementation

Implementing rules for incrementing and updating Lamport timestamps on events and messages.

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.