Lamport Timestamps in TypeScript

From Partial to Total Order

The "happens-before" relation is sufficient to understand causality, but sometimes we need more. Imagine two users in your collaborative canvas application trying to claim a unique vanity URL for their project at the same time. Their requests might be concurrent (request_A || request_B). A partial order can't help us decide who was "first." We need a deterministic rule that every node in the system can agree upon. We need a total order.

This is what Leslie Lamport provided with his logical clock algorithm. The idea is to attach a simple, ever-increasing number—a logical timestamp—to every event. The algorithm ensures that if an event A happens-before an event B, then the timestamp of A will always be less than the timestamp of B.

The Lamport Clock Algorithm

The algorithm is remarkably simple. Each node (or client in your case) maintains a single integer counter, which acts as its logical clock.

As the article explains, the algorithm consists of three rules:

1. For a local event: Before executing an event that is internal to a node (e.g., a user editing text locally before sending), the node increments its own counter.
   counter = counter + 1

2. For a send event: Before sending a message, a node first increments its counter and then attaches the new counter value to the message.

3. For a receive event: When a node receives a message with a timestamp t_received, it updates its own counter by taking the maximum of its current value and the received timestamp, and then increments the result by one.
   counter = max(counter, t_received) + 1

The magic is in the receive rule. By setting its clock to be greater than both its own past and the sender's past, the receiving node ensures its logical time "jumps ahead" of the event that caused it. This simple mechanism guarantees that the timestamps respect the causal order defined by the happens-before relation.

The Limits of Lamport Timestamps

The algorithm guarantees that if A → B, then Timestamp(A) < Timestamp(B). However, the reverse is not true. This is a subtle but critical point.

As Kleppmann explains, if you have two timestamps L(A) = 3 and L(B) = 4, you cannot conclude that A → B. It's possible that A and B were concurrent. The Lamport clock on its own cannot distinguish between causal and concurrent relationships. All we know is that B did not happen before A.

Achieving a Total Order

So how do we solve our initial problem of needing a definitive, total order? We saw that timestamps can be tied, and even when they aren't, the numerical order doesn't perfectly map to the causal order for concurrent events.

The solution is to create a composite timestamp that can be used to break ties deterministically. We combine the Lamport timestamp with a unique identifier for the node that generated the event (e.g., a user ID or a machine ID).

A total order timestamp is thus a pair: (timestamp, node_id).

To compare two of these pairs, (t1, n1) and (t2, n2):

1. First, compare the timestamps t1 and t2. The one with the smaller timestamp comes first.
2. If the timestamps are equal (t1 == t2), then compare the node IDs n1 and n2 (lexicographically or numerically). The one with the "smaller" node ID comes first.

Since every node ID is unique, this process guarantees that we can always find a strict, total ordering between any two events in the system. And because we prioritize the Lamport timestamp, this total order is guaranteed to be consistent with causality.

Hands-On: Implementing a Lamport Clock in TypeScript

Now, let's put this into code. Your background as a senior frontend engineer means you'll find the implementation straightforward. We'll create a simple class in TypeScript to manage the clock for a single node.

Here is the basic structure of our LamportClock class.

// A unique identifier for each client/node. In a real app,
// this could be a user ID, a session ID, etc.
type NodeID = string;

class LamportClock {
  private time: number;
  public readonly nodeId: NodeID;

  constructor(nodeId: NodeID) {
    this.time = 0;
    this.nodeId = nodeId;
  }

  // To be called for any local event or before sending a message.
  // It increments the local time and returns the new timestamp.
  tick(): number {
    this.time++;
    return this.time;
  }

  // To be called upon receiving a message with a timestamp.
  // It updates the local time according to the Lamport algorithm.
  receive(receivedTime: number): number {
    this.time = Math.max(this.time, receivedTime) + 1;
    return this.time;
  }

  // Returns the current time of the clock.
  now(): number {
    return this.time;
  }
}

Let's simulate a small scenario with three clients—Alice, Bob, and Charlie—to see it in action.

// --- Simulation ---

// 1. Initialize clocks for three different clients
const aliceClock = new LamportClock("alice");
const bobClock = new LamportClock("bob");
const charlieClock = new LamportClock("charlie");

// 2. Alice performs a local action (e.g., types a character)
const t_alice_1 = aliceClock.tick(); // t_alice_1 is 1. Alice's clock is now 1.
console.log(`Alice local event. Time: ${t_alice_1}`);

// 3. Bob performs a local action
const t_bob_1 = bobClock.tick(); // t_bob_1 is 1. Bob's clock is now 1.
console.log(`Bob local event. Time: ${t_bob_1}`);

// 4. Alice sends a message to Bob. She 'ticks' her clock first.
const t_alice_send = aliceClock.tick(); // t_alice_send is 2. Alice's clock is now 2.
console.log(`Alice sends message to Bob. Time: ${t_alice_send}`);

// Bob receives the message from Alice.
const t_bob_receive = bobClock.receive(t_alice_send); // Bob's clock was 1. max(1, 2) + 1 = 3. Bob's clock is now 3.
console.log(`Bob receives message from Alice. Time: ${t_bob_receive}`);

// 5. Bob now sends a message to Charlie.
const t_bob_send = bobClock.tick(); // t_bob_send is 4. Bob's clock is now 4.
console.log(`Bob sends message to Charlie. Time: ${t_bob_send}`);

// Charlie receives the message from Bob.
const t_charlie_receive = charlieClock.receive(t_bob_send); // Charlie's clock was 0. max(0, 4) + 1 = 5.
console.log(`Charlie receives message from Bob. Time: ${t_charlie_receive}`);

/*
Expected Output:
Alice local event. Time: 1
Bob local event. Time: 1
Alice sends message to Bob. Time: 2
Bob receives message from Alice. Time: 3
Bob sends message to Charlie. Time: 4
Charlie receives message from Bob. Time: 5
*/

This simulation precisely mirrors the worked example from the article. Notice how the timestamps (1, 2, 3, 4, 5) strictly increase along the causal chain of events: Alice's initial action → Alice's send → Bob's receive → Bob's send → Charlie's receive.

To generate a total order timestamp, you would simply pair the returned number with the nodeId from the clock instance, for example [t_alice_1, aliceClock.nodeId] which would be [1, "alice"].

Conclusion

In this lesson, we made a significant leap from abstract theory to a practical, implementable algorithm.

Here are the key takeaways:

• Lamport clocks assign a single integer to each event, providing a logical timestamp.
• The core of the algorithm is the receive rule: local_time = max(local_time, received_time) + 1. This ensures that timestamps respect causality: if A → B, then Timestamp(A) < Timestamp(B).
• A smaller timestamp does not imply causality. Concurrent events can have timestamps that are ordered, but this order is arbitrary.
• To create a total order, we use a composite timestamp (timestamp, node_id) and break ties using the node ID.

You now have a tool to create a single, deterministic order of operations across all clients. This is a valid way to resolve conflicts: if two concurrent operations occur, just let the one with the smaller total-order timestamp "win." This is known as a "Last-Writer-Wins" approach, which we'll explore more later.

However, Lamport clocks have a crucial limitation: they can't tell you if two events were concurrent. In our next lesson, we will introduce vector clocks, an evolution of Lamport clocks that can detect concurrency. This ability is fundamental to the conflict-free merging strategies used by CRDTs.