Logical Clocks: Lamport Timestamps and Event Ordering

Physical clocks drift and skew. NTP helps but cannot solve the fundamental problem: in distributed systems, you cannot rely on time to tell you which event happened first. Logical clocks offer an alternative.

The insight behind logical clocks is simple: you do not need to know the exact time an event occurred. You only need to know whether it happened before or after another event. Leslie Lamport formalized this in 1978, and his solution remains foundational.

This post covers Lamport timestamps and the happens-before relationship. If you have not read the Physical Clocks post, start there.

---

The Problem with Physical Time

In a single machine, events have a total order. The CPU executes instructions sequentially. Even with multiple cores, memory operations have defined ordering through hardware.

Across machines, no global clock exists. Machine A might timestamp an event at 10:00:00.001, and Machine B might timestamp a causally-later event at 10:00:00.000. Physical timestamps lie about causality.

sequenceDiagram
    participant A as Machine A
    participant B as Machine B

    Note over A: Event E1 at T=10:00:00.000 (physical)
    A->>B: Network message

    Note over B: Event E2 at T=10:00:00.001 (physical)
    Note over B: But E2 causally depends on E1!
    Note over B: Physical time lies about ordering

This is not a hardware problem to solve. It is a fundamental characteristic of distributed systems. Causality must be reasoned about differently.

---

The Happens-Before Relationship

Lamport introduced a way to reason about ordering without physical clocks. The happens-before relation (also called causal ordering) works like this:

Definition

For events in a single process, if event A occurs before event B, then A happens-before B.

For messages: if event A sends a message, and event B receives that message, then A happens-before B.

The happens-before relation is transitive. If A happens-before B, and B happens-before C, then A happens-before C.

// Single process: sequential execution
const x = 1; // E1
const y = 2; // E2
const z = x + y; // E3
// E1 -> E2 -> E3

// Two processes with message passing
// Process 1:
send(m, Process2); // E1
x = 5; // E2

// Process 2:
y = receive(m); // F1
z = y + 1; // F2
// E1 -> E2 (in Process 1)
// F1 -> F2 (in Process 2)
// E1 -> F1 (message causality)

Concurrency

Two events are concurrent (or causally independent) if neither happens-before the other. This does not mean they occurred at the same instant. It means we cannot determine ordering from the events alone.

// Concurrent events
// Machine A: Event X
// Machine B: Event Y
// No message between them
// X and Y are concurrent - we cannot say which happened first

---

Lamport Timestamps

Lamport timestamps assign numbers to events in a way that respects the happens-before relationship. If A happens-before B, then the timestamp of A is less than the timestamp of B.

The Algorithm

Each process maintains a logical counter. The rules are simple:

1. When an event occurs locally, increment the counter and assign it to the event
2. When sending a message, include the current counter value
3. When receiving a message, set your counter to max(local counter, received counter) + 1

class LamportClock {
  constructor() {
    this.counter = 0;
    this.processId = process.pid;
  }

  // Local event
  tick() {
    this.counter++;
    return this.counter;
  }

  // Send message
  send() {
    this.counter++;
    return this.counter;
  }

  // Receive message
  receive(receivedCounter) {
    this.counter = Math.max(this.counter, receivedCounter) + 1;
    return this.counter;
  }
}

// Usage
const clock = new LamportClock();

const t1 = clock.tick(); // Local event
const t2 = clock.send(); // Sending a message
// ... message travels over network ...
const t3 = clock.receive(5); // Received message with counter 5

Properties

Lamport timestamps have one important property: if A happens-before B, then timestamp(A) < timestamp(B). The converse is not true. Two events might have timestamps where T(A) < T(B) but A and B are concurrent.

graph TD
    A[Process A: E1, T=1] --> B[Process A: E2, T=2]
    B -->|message| C[Process B: F1, T=3]
    C --> D[Process B: F2, T=4]

    E[Process C: G1, T=1] --> F[Process C: G2, T=2]

    A -.->|concurrent| E
    F -.->|concurrent| C

---

Why Lamport Clocks Are Not Enough

Lamport clocks establish ordering for causally-related events. But they do not let you determine whether two events are causally related or concurrent. This limitation matters in practice.

The Concurrent Events Problem

Consider this scenario:

sequenceDiagram
    participant A as Machine A
    participant B as Machine B

    Note over A: E1 at T=1
    A->>B: Message (carries T=1)

    Note over B: F1 at T=2
    Note over B: G1 at T=3
    Note over B: F1 and G1 are concurrent
    Note over B: Cannot determine from timestamps alone

Both F1 and G1 happen after receiving the message (T=1), so their timestamps are greater than 1. But F1 and G1 are independent of each other. Lamport timestamps cannot tell you this.

Why This Matters for Conflict Resolution

In a distributed database, you might have two writes to the same key, committed simultaneously on different nodes. Lamport timestamps tell you which is “later” but not whether they are causally related.

If they are causally related (one write was based on seeing the other), you have a true conflict. If they are concurrent, you might be able to auto-merge with CRDTs.

This is why most distributed databases use vector clocks, which we will cover in the next post.

---

Implementing Lamport Clocks

Simple Implementation

// Node.js implementation of Lamport clock
class LamportClock {
  constructor(nodeId) {
    this.nodeId = nodeId;
    this.time = 0;
  }

  now() {
    return this.time;
  }

  // Call on local events
  tick() {
    this.time++;
    return this.time;
  }

  // Call before sending a message
  send() {
    this.time++;
    return this.time;
  }

  // Call when receiving a message
  receive(messageTime) {
    this.time = Math.max(this.time, messageTime) + 1;
    return this.time;
  }

  // Compare two timestamps
  static compare(a, b) {
    if (a.time !== b.time) {
      return a.time - b.time;
    }
    // Tie-breaker: lower node ID wins
    return a.nodeId.localeCompare(b.nodeId);
  }
}

Usage in a Distributed System

// Example: distributed key-value store with Lamport clocks
class ReplicatedKVStore {
  constructor(nodeId) {
    this.nodeId = nodeId;
    this.clock = new LamportClock(nodeId);
    this.data = new Map();
    this.metadata = new Map(); // key -> {value, timestamp, nodeId}
  }

  async put(key, value) {
    const timestamp = this.clock.tick();

    // Propagate to other nodes
    await this.broadcast({
      type: "put",
      key,
      value,
      timestamp: { time: timestamp, nodeId: this.nodeId },
    });

    this.data.set(key, value);
    this.metadata.set(key, {
      value,
      timestamp: { time: timestamp, nodeId: this.nodeId },
    });
    return timestamp;
  }

  async handleMessage(msg) {
    const localTs = this.clock.receive(msg.timestamp.time);

    if (msg.type === "put") {
      const existing = this.metadata.get(msg.key);
      if (
        !existing ||
        LamportClock.compare(msg.timestamp, existing.timestamp) > 0
      ) {
        this.data.set(msg.key, msg.value);
        this.metadata.set(msg.key, msg);
      }
    }
  }
}

Integration with Message Passing

The key insight is that timestamps travel with messages. Every message carries the logical timestamp of its sender at send time.

// Message passing with Lamport timestamps
class Message {
  constructor(sender, payload, lamportTime) {
    this.sender = sender;
    this.payload = payload;
    this.lamportTime = lamportTime;
    this.timestamp = Date.now(); // Physical time for debugging
  }
}

// Sender side
function sendMessage(recipient, payload, clock) {
  const logicalTime = clock.send();
  const msg = new Message(myNodeId, payload, logicalTime);
  network.send(recipient, msg);
  return msg;
}

// Receiver side
function receiveMessage(msg, clock) {
  const logicalTime = clock.receive(msg.lamportTime);
  // Process message with updated clock
  processMessage(msg.payload, logicalTime);
}

---

Total Order Broadcast

Lamport clocks enable a powerful primitive called Total Order Broadcast (also known as atomic broadcast). This is the mechanism that consensus algorithms like Paxos and Raft use to agree on the order of operations.

What is Total Order Broadcast?

Total Order Broadcast guarantees two properties:

1. Reliability: All correct nodes deliver the same messages, or none
2. Total Order: All correct nodes deliver messages in the same order

This is different from causal broadcast, which only guarantees that causally-related messages are ordered correctly. Total order broadcast imposes a global order on ALL messages.

sequenceDiagram
    participant P1 as Process 1
    participant P2 as Process 2
    participant P3 as Process 3
    participant TOB as Total Order Broadcast

    Note over P1,P3: Messages must be delivered in same order to ALL processes

    P1->>TOB: Broadcast(M1)
    P2->>TOB: Broadcast(M2)
    P3->>TOB: Broadcast(M3)

    TOB->>P1: Deliver(M1)
    TOB->>P2: Deliver(M1)
    TOB->>P3: Deliver(M1)

    Note over P1,P3: Then M2, then M3 - same order everywhere

How Lamport Clocks Enable Total Order Broadcast

The connection works through the concept of “slot numbers”:

1. Each message carries a Lamport timestamp
2. The broadcaster also performs a consensus/agreement step (via Paxos/Raft)
3. Messages are assigned slot numbers based on agreement
4. All nodes deliver messages in slot number order

// Total Order Broadcast using Lamport clocks
class TotalOrderBroadcast {
  constructor(nodeId, consensusModule) {
    this.nodeId = nodeId;
    this.consensus = consensusModule; // Paxos or Raft
    this.clock = new LamportClock(nodeId);
    this.deliveryQueue = [];
    this.delivered = [];
  }

  // Broadcast a message with total order
  async broadcast(payload) {
    const timestamp = this.clock.send();

    // Propose to consensus module with timestamp
    // The consensus module assigns a slot number
    const slot = await this.consensus.propose({
      payload,
      timestamp,
      sender: this.nodeId,
    });

    return slot;
  }

  // Deliver messages in total order
  deliver(proposal) {
    // Wait until all earlier slots are delivered
    if (proposal.slot === this.getNextSlot()) {
      this.delivered.push(proposal);
      this.deliverNext();
    } else {
      // Buffer out-of-order messages
      this.deliveryQueue.push(proposal);
      this.deliveryQueue.sort((a, b) => a.slot - b.slot);
    }
  }

  getNextSlot() {
    return this.delivered.length + 1;
  }
}

Connection to Paxos

Multi-Paxos uses Total Order Broadcast implicitly:

1. The leader proposes values in slot number order
2. Acceptors accept values for specific slots
3. Once a value is chosen for a slot, all nodes learn the same value for that slot
4. This gives total order without explicit broadcast protocol

graph LR
    subgraph Paxos
        L[Leader] -->|Propose slot N| A1[Acceptor 1]
        L -->|Propose slot N| A2[Acceptor 2]
        L -->|Propose slot N| A3[Acceptor 3]

        A1 -->|Accepted| L
        A2 -->|Accepted| L
        A3 -->|Accepted| L

        L -->|Learn| All[All Replicas]
    end

    Note over L,All: Once slot N is chosen, all nodes see same value

Connection to Raft

Raft implements total order through its log replication:

1. Leader receives client requests
2. Leader appends to local log with new entry term
3. Leader replicates entries to followers via AppendEntries RPC
4. Once entry is committed (majority ack), it can be applied
5. All nodes apply entries in same order (log index order)

graph LR
    subgraph Raft
        C[Client] --> L[Leader]
        L -->|AppendEntries| F1[Follower 1]
        L -->|AppendEntries| F2[Follower 2]

        F1 -->|ACK| L
        F2 -->|ACK| L

        L -->|Commit| AP1[Apply to State Machine]
        L -->|Commit| AP2[Apply to State Machine]
    end

    Note over L: Log index = total order

When Total Order Broadcast Matters

Use Case	Why Total Order is Needed
Distributed database commits	All nodes must see writes in same order
Blockchain / distributed ledger	Transaction ordering determines state
Distributed mutex / locks	Must acquire locks in globally consistent order
Replicated state machines	Same inputs in same order = same outputs
Configuration updates	All nodes must apply config in same order

Scalability Bottleneck Analysis

Total Order Broadcast has a fundamental scalability limitation: someone must coordinate the ordering.

Single Leader Bottleneck (Paxos/Raft):

Nodes	Throughput (ops/sec)	Latency (ms)
3	~10,000-50,000	5-15
5	~5,000-30,000	10-30
7	~3,000-20,000	15-50
9+	Degrades significantly	50+

The leader becomes a bottleneck because it must sequence all operations.

Alternatives for Scale:

• Paxos with flexible quorums:降低负载 but complex
• EPaxos: Exploits commutativity for better scaling
• Chain replication: Pipeline ordering through chain
• Partial ordering: Only order causally-related events

Benchmark comparison (approximate, YCSB workload):

Configuration: 3-node cluster, 3x replication
Leader-based (Raft): ~15,000 writes/sec at 10ms latency
EPaxos: ~25,000 writes/sec at 8ms latency (with commutative workload)
Chain Replication: ~40,000 writes/sec at 5ms latency (pipelined)

---

Real-World Applications

Debugging Distributed Systems

Lamport timestamps help reconstruct event order from logs:

# Given logs with Lamport timestamps from multiple services:
# Service A: [T=1] Started
# Service B: [T=1] Received request
# Service A: [T=2] Sent response
# Service B: [T=2] Processed request

# You can reconstruct the true causal order:
# 1. Service A: T=1 (first local event)
# 2. Service A -> Service B (message)
# 3. Service B: T=1 (received, receive rule)
# 4. Service A: T=2 (sent response)
# 5. Service B: T=2 (processed)

Event Sourcing

Event sourcing systems use Lamport timestamps to order events:

// Banking example: events must be ordered correctly
const events = [
  { type: "deposit", amount: 100, timestamp: { time: 1, nodeId: "A" } },
  { type: "withdrawal", amount: 50, timestamp: { time: 1, nodeId: "B" } },
  // Both have T=1 - which happened first?
];

// With Lamport clocks alone, you cannot tell
// B's withdrawal at T=1 and A's deposit at T=1 are concurrent
// Need additional info (or vector clocks) to resolve

---

Limitations

No Causal Awareness

Lamport clocks cannot distinguish causally-related events from concurrent events. If A happens-before B, timestamps work. But if A and B are concurrent, timestamps are ambiguous.

No Bound on Concurrency

Lamport timestamps give no upper bound on how many concurrent events might exist. You cannot look at a timestamp and know how many other events might be concurrent with it.

Single Node Bottleneck

In naive implementations, each event increments a counter. Under high concurrency, this can become a bottleneck. Optimizations exist but add complexity.

---

Decision Tree: Lamport vs Vector Clocks

Choosing between Lamport clocks and vector clocks depends on your requirements:

flowchart TD
    A[Do you need to determine<br/>causal ordering?] --> B{Do you need to detect<br/>concurrent updates?}

    B -->|Yes| VC[Use Vector Clocks]
    B -->|No| C{Do you only need<br/>total ordering?}

    C -->|Yes - with consensus| TOB[Use Lamport Clocks<br/> + Total Order Broadcast<br/> + Consensus]
    C -->|No - only causal| LC[Use Lamport Clocks<br/> for causal ordering]

    VC -->|Simpler| DynamoStyle[Version Vectors<br/>Dynamo-style]
    VC -->|Full causality| FullVC[True Vector Clocks<br/>Full causal tracking]

    TOB --> RaftStyle[Raft / Multi-Paxos]
    TOB --> ChubbyStyle[Chubby / Zookeeper]

Decision Matrix

Requirement	Lamport Clocks	Vector Clocks
Detect concurrent updates	No	Yes
Know if A caused B	Yes	Yes
Know if A and B are concurrent	No	Yes
Space efficiency	O(1)	O(n) per object
Simple implementation	Yes	Moderate
Total ordering	With TOB	With TOB
Common use cases	Debugging, logging, distributed consensus	Conflict detection, CRDTs, Dynamo-style DBs

Quick Decision Guide

Ask yourself these questions:

1. Do you need to detect if two events are concurrent?

   • YES: Use Vector Clocks
   • NO: Continue to question 2

2. Do you need total ordering across all nodes?

   • YES: Use Lamport Clocks + Total Order Broadcast + Consensus (Raft/Paxos)
   • NO: Use Lamport Clocks for causal ordering only

3. Do you need to know all events that causally preceded an event?

   • YES: Use Vector Clocks
   • NO: Lamport Clocks may suffice

Real System Examples

Google Chubby (Early): Used Lamport clocks internally for coordinating leader election. The Chubby lock service uses a consensus protocol (modified Paxos) for total ordering, with Lamport clocks providing causal context within a cell.

Cassandra 1.x: Used Lamport timestamps for write ordering within a datacenter. Timestamps propagate with data but only track happened-before, not full causal history.

Modern Cassandra (2.0+): Switched to version vectors (similar to vector clocks) for tracking concurrent modifications to the same data across replicas.

DynamoDB: Uses timestamp-based conflict resolution, not true vector clocks. Last-write-wins based on physical timestamps (with hybrid logical clocks in some internal implementations).

Riak: Uses vector clocks (version vectors) for conflict detection. When a key has concurrent modifications, Riak returns all versions and lets the client resolve conflicts.

etcd: Uses Raft consensus with Lamport-style logical clocks for operation ordering. The Raft log provides total order; Lamport clocks aren’t needed separately.

Consul: Uses Raft for total ordering of service registrations and key-value updates.

---

Conclusion

Lamport timestamps solve a specific problem: establishing an ordering that respects causality. If A happens-before B, Lamport timestamps guarantee T(A) < T(B).

They do not solve the inverse problem: given T(A) < T(B), you cannot conclude A happens-before B. Events might be concurrent.

For most distributed systems, this limitation matters. Vector clocks, covered in the next post, extend Lamport clocks to track causal history explicitly.

Key takeaways:

1. The happens-before relationship captures causal ordering
2. Lamport timestamps respect happens-before but not vice versa
3. Lamport clocks are simple to implement
4. They cannot distinguish concurrent events from causally-ordered ones
5. Most production systems use vector clocks for conflict detection

The Vector Clocks post covers how to track full causal history.

---

When to Use / When Not to Use Lamport Clocks

Scenario	Recommendation
Debugging and tracing	Use Lamport clocks
Total ordering of events	Use Lamport clocks + broadcast
Conflict detection in databases	Do not use alone
CRDT merge decisions	Do not use alone
Determining causal independence	Do not use alone

When TO Use Lamport Clocks

• Adding causal ordering to application logs
• Implementing total order broadcast
• When you need a simple way to compare event order
• As a component of more complex clock systems

When NOT to Use Lamport Clocks

• When you need to detect concurrent updates
• When you need to merge concurrent states automatically
• When you need to know all events causally preceding another

---

Production Considerations

Scalability

Each event requires an atomic increment. Under high throughput, this can become a bottleneck:

// Bottleneck: centralized counter
class GlobalLamportClock {
  constructor() {
    this.time = 0;
    this.lock = new Mutex();
  }

  async tick() {
    await this.lock.acquire();
    this.time++;
    const t = this.time;
    this.lock.release();
    return t;
  }
}

// Better: per-node counters
// Nodes only sync on message receipt
// Message carries counter, not global sync

Monitoring

Track clock skew between nodes to detect synchronization issues:

// Detect anomalous clock behavior
metrics.on("message", ({ fromNode, receivedTime, sentTime }) => {
  const skew = receivedTime - sentTime;
  if (Math.abs(skew) > 1000) {
    // 1 second skew is suspicious
    alerts.emit("clock_skew", { fromNode, skew });
  }
});

Debugging Tips

Log both logical and physical timestamps. When debugging, physical time helps you understand when things happened. Logical time helps you understand why.

logger.info("Event processed", {
  event: "user_action",
  logicalTime: clock.now(),
  physicalTime: new Date().toISOString(),
  nodeId: myNodeId,
});

---

Quick Recap

• Happen-before captures causal ordering without clocks
• Lamport timestamps assign numbers respecting happen-before
• T(A) < T(B) if A happens-before B, but not vice versa
• Lamport clocks cannot detect concurrent events
• Use for total ordering and debugging, not conflict detection

For more on distributed systems fundamentals, see CAP Theorem, Consistency Models, and Geo-Distribution.