Logical time: Lamport clocks
Order events across machines without a shared clock by counting events and message receipts.
On this page
Classes and the idea of message passing.
- Order events across machines without a shared clock by counting events and message receipts.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
In a distributed system each machine has its own physical clock, and those clocks drift apart, so timestamps from different machines cannot be trusted to order events. Leslie Lamport's 1978 paper replaced wall-clock time with logical time based on causality. The happened-before relation, written →, says that event a happened before b if they occur in that order in the same process, or if a is the sending of a message and b is its receipt, or if the two are linked by a chain of such steps. Events not related this way are concurrent.
A Lamport clock is a counter kept by each process. A process increments it before each local event or send, and attaches the value to every message. When it receives a message with timestamp t, it sets its clock to max(its clock, t) + 1. This guarantees the clock condition: if a → b then the timestamp of a is smaller than the timestamp of b.
The converse is false: a smaller timestamp does not prove that one event caused the other. Vector clocks keep one counter per process and can tell causal order from concurrency. The program runs a send from A and a receive at B. B's local clock was only 1, but the message carried 2, so after receiving B's clock jumps to 3, which is later than the send. A real system would also break timestamp ties with a process identifier to get a total order.
Code example
class Process:
def __init__(self, name):
self.name = name
self.clock = 0
def local_event(self):
self.clock += 1
return self.clock
def send(self):
self.clock += 1
return self.clock
def receive(self, timestamp):
self.clock = max(self.clock, timestamp) + 1
return self.clock
a = Process("A")
b = Process("B")
a.local_event()
sent = a.send()
b.local_event()
received = b.receive(sent)
print(sent, received)
print(received > sent)
print(a.clock, b.clock)2 3 True 2 3
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
class Process: def __init__(self, name): self.name = name self.clock = 0 def local_event(self): self.clock += 1 return self.clock def send(self): self.clock += 1 return self.clock def receive(self, timestamp): self.clock = max(self.clock, timestamp) + 1 return self.clock a = Process("A")b = Process("B")a.local_event()sent = a.send()b.local_event()received = b.receive(sent)print(sent, received)print(received > sent)print(a.clock, b.clock)Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Every local event or send advances the process's own counter. | — | — | |
| A sends a message after its first event, so the message carries timestamp 2. | A.clock = 2, message timestamp 2 | — | |
| B has its own independent clock, which is only 1 so far. | A.clock = 2, message timestamp 2 | — | |
| On receipt, B takes the larger of its clock and the message timestamp, then adds one: max(1, 2) + 1 = 3. | A.clock = 2, message timestamp 2 | — | |
| The receive event gets a larger timestamp than the send, honouring happened-before. | A.clock = 2, message timestamp 2 | 2 3 True | |
| Final logical clocks: A is 2 and B is 3. | A.clock = 2, message timestamp 2 | 2 3 True 2 3 |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
Cost and common mistakes
Each clock update is O(1) time and each message carries one integer. Vector clocks need O(n) per message for n processes.
- If a → b then C(a) < C(b), but C(a) < C(b) does not imply a → b. Lamport timestamps cannot detect concurrency; vector clocks can.
- Logical clocks are not wall-clock time. They say nothing about how many seconds passed.
- Two different events can have the same Lamport timestamp. Break ties with a process id to create a total order.
Try it yourself
If B receives a message with timestamp 10 while its clock is 4, what is the clock afterwards?
Reveal answer and reasoning
max(4, 10) + 1 = 11. The receiver's clock jumps past the timestamp carried by the message.