Lamport Logical Clocks

Leslie Lamport, 1978 — "Time, Clocks, and the Ordering of Events in a Distributed System"

---

The Problem: No Shared Clock

Computers on a network do not share a perfectly synchronised clock. Node 0's clock might read 10:00:00.005 while Node 1's clock reads 10:00:00.003. If Node 0 logs an event at 10:00:00.005 and Node 1 logs an event at 10:00:00.004, which happened first?

You can't tell using wall-clock time alone.

In a distributed file system, we need to know the order of events to prevent inconsistency. If two clients upload different versions of the same file, we must decide which one "came first" and apply that order consistently across all replicas.

The Solution: Logical Clocks

A Lamport clock is just an integer counter — it doesn't tell you what time it is. It tells you the order of events.

The Three Rules

Event	Rule	Code
Local event (do something)	Increment counter by 1	clock++
Send a message	Increment counter, attach it to the message	++clock; msg.timestamp = clock;
Receive a message with value v	Set counter to max(clock, v) + 1	clock = Math.max(clock, v) + 1;

Why max()?

The max() rule is the key insight. If Node 0 has clock=5 and receives a message with timestamp=10, Node 0 knows that at least 10 events happened before this message. Setting its clock to max(5, 10) + 1 = 11 means its clock now correctly reflects the global ordering.

Without max(), Node 0 would set clock=6 and appear to be "behind" — messages it later sends would have timestamps smaller than events that actually happened before them.

Visual Timeline

The Guarantee

If event A causally happens before event B (A → B), then clock(A) < clock(B).

This is the happens-before guarantee. It's the property that makes TO-Multicast ordering work.

The Implementation

Our LogicalClock.java is just 3 methods:

public class LogicalClock {
    private long time = 0;

    // Called before sending a message — increments and returns new value
    public synchronized long tick() {
        return ++time;
    }

    // Called when receiving a message — merges clocks and increments
    public synchronized long update(long received) {
        time = Math.max(time, received) + 1;
        return time;
    }

    // Read current value without side effects
    public synchronized long getTime() {
        return time;
    }
}

Usage in the system

Before broadcasting a TO-Multicast message (ReplicaNode):

long ts = clock.tick();                        // clock becomes 5
ClockMessage msg = new ClockMessage(nodeId, ts, op);
for (ReplicaNodeInterface peer : peers) {
    peer.receiveMulticast(msg);                // attached ts=5
}

When receiving a TO-Multicast message (ReplicaNode):

public void receiveMulticast(ClockMessage msg) throws RemoteException {
    long myTs = clock.update(msg.getTimestamp());  // clock = max(old, msg.ts) + 1
    messageQueue.addMessage(msg);                   // enqueue
    for (ReplicaNodeInterface peer : peers) {
        peer.sendAck(nodeId, msg.getMessageId(), myTs);  // send ack with new clock value
    }
}

Why This Matters for TO-Multicast

When the delivery loop checks if a message is deliverable, it looks at two things:

1. Are all ACKs received?
2. Is every ACK timestamp > message timestamp?

The second condition relies on Lamport clocks. If Node 1 receives a message with ts=5 and ACKs with ts=7, that ACK timestamp of 7 "proves" that Node 1 has no undelivered messages with timestamps ≤ 5 — because its clock is already at 7, meaning it's seen at least 7 events.

---

Common Misconception

:::danger Lamport clocks are NOT wall clocks A Lamport timestamp of 1000 doesn't mean "1,000 milliseconds" — it means "this is the 1,000th event in the causal ordering." The actual wall-clock time could be anything. :::

---

Next: Totally Ordered Multicast

Now you understand the timestamps. The next page explains the TO-Multicast algorithm that uses them to guarantee all replicas stay in sync. → Totally Ordered Multicast