Lamport and Vector Clocks in Go: Ordering Events Without a Shared Clock

In 1978, Leslie Lamport pointed out that "before" has little to do with time. Event a is before event b only if a could have influenced b: they are on the same machine, or a chain of messages connects them. If neither can reach the other, asking which came first has no answer.

That sounds like a philosophical detail until your conflict resolution depends on it. Wall clocks cannot settle the question: servers drift, NTP corrections jump them, and a 3 ms gap between two replicas is well inside the error of most setups. Even a logical clock can mislead. The classic Lamport clock gives different timestamps to nine unrelated pairs of events in ten (measured below), as if one had clearly come first.

This article builds the math that fixes it, an order that allows incomparable pairs, and two algorithms that implement it, Lamport clocks and vector clocks, in Go. It is the second in a series on the math inside distributed systems, after consistent hashing.

The math: "before" is a partial order

Start with what we actually want to know. For two events a and b, we want to answer: could a have influenced b? Leslie Lamport defined this in 1978 as the happened-before relation, written a → b, using three rules:

1. If a and b are on the same process and a comes first, then a → b.
2. If a sends a message and b receives that same message, then a → b.
3. If a → b and b → c, then a → c (transitivity).

Nothing here mentions a clock. It only follows cause and effect: a process's own sequence of steps, and messages between processes.

This relation is a partial order, and the word partial matters. A total order like 1 < 2 < 3 compares any two elements. A partial order allows pairs that are simply not comparable. Think of a family tree: a grandparent comes before their grandchildren in the line of descent, but two cousins are neither ancestor nor descendant of each other. Formally, happened-before is:

• irreflexive: no event happens before itself,
• transitive: if a → b and b → c then a → c,
• antisymmetric: a → b and b → a can never both hold.

Two events with neither a → b nor b → a are called concurrent, written a ∥ b. Concurrent does not mean "at the same instant". It means neither could have known about the other. Detecting that case is the whole point: those are exactly the events whose order the system must decide on purpose, or flag as a conflict.

So the real goal is to attach a label to every event so that comparing labels recovers →. Lamport clocks do half of this job, vector clocks do all of it.

Lamport clocks: one counter per process

The idea is a single integer per process. Rules:

• Before any local event or send, increment your counter.
• Attach the counter to every message you send.
• On receive, set your counter to max(yours, message's) + 1.

type Lamport struct{ t uint64 }

// Tick: local event or send.
func (c *Lamport) Tick() uint64 { c.t++; return c.t }

// Recv: take the max with the message's timestamp, then tick.
func (c *Lamport) Recv(m uint64) uint64 {
    if m > c.t {
        c.t = m
    }
    c.t++
    return c.t
}

What it guarantees

Write L(a) for the timestamp of event a. The guarantee, called the clock condition, is:

a → b   implies   L(a) < L(b)

The proof is short and follows the three rules. Along one process the counter only increases (rule 1). A receive sets the counter to more than the send's timestamp (rule 2). And < on integers is transitive (rule 3). So if a can influence b, a always has the smaller number.

What it does not guarantee

The arrow goes only one way. L(a) < L(b) does not imply a → b. A concrete run with three processes shows it:

L(e6) = 1 is smaller than L(e3) = 3, so the numbers suggest e6 came first. But C had heard nothing from A or B when e6 happened, so the two are concurrent. Lamport clocks manufacture an order that does not exist.

This is not a corner case. In 10,000 random executions of 4 processes (about 6.7 million event pairs), 59.9% of pairs were concurrent, and Lamport gave different timestamps to 90.0% of those concurrent pairs, making them look ordered. The clock condition itself held every time, as the proof says it must.

Where it is still useful

If you only need some order that respects causality, Lamport is enough, and it costs one integer per message. To make it a total order, break ties with the process id: sort by (L, processID). Every node then derives the same sequence from the same events, which is the basis of simple replicated logs and distributed mutual exclusion. What you cannot do with it is ask "were these two events concurrent?".

Vector clocks: one counter per process, kept by everyone

To detect concurrency we need to keep more information. Instead of one integer, each process keeps a vector: one counter for each process. Entry V[B] means "how many of B's events I know about".

Rules:

• On a local event or send, increment your own entry.
• Attach the whole vector to every message.
• On receive, take the component-wise maximum of your vector and the message's, then increment your own entry.

type VClock map[string]uint64

func (v VClock) Tick(id string) { v[id]++ }

func (v VClock) Recv(id string, m VClock) {
    for k, x := range m {
        if x > v[k] {
            v[k] = x
        }
    }
    v[id]++
}

The math: comparing vectors

Order two vectors component by component. V ≤ W means every entry of V is at most the matching entry of W. V < W means V ≤ W and they are not equal.

This is again a partial order, and that is exactly why it works. Two vectors can be incomparable: [A:3, B:0] and [A:1, B:2] each have one entry larger than the other, so neither is ≤ the other. The theorem:

a → b    if and only if    V(a) < V(b)
a ∥ b    if and only if    V(a) and V(b) are incomparable

Note the if and only if. Unlike Lamport, vector clocks preserve the order in both directions. The intuition is that V(a)[i] counts the events of process i that are in a's causal past. If a is in b's past, then everything in a's past is also in b's past, so every entry of V(b) is at least as large, and b itself adds one more. If a is not in b's past, b has not seen at least one event that a has, and some entry of V(b) is smaller. Comparison is then a few lines:

func Compare(a, b VClock) Order {
    aLE, bLE := true, true // a <= b ?   b <= a ?
    for k, x := range a {
        if x > b[k] {
            aLE = false
        }
    }
    for k, x := range b {
        if x > a[k] {
            bLE = false
        }
    }
    switch {
    case aLE && bLE:
        return Equal
    case aLE:
        return Before
    case bLE:
        return After
    }
    return Concurrent
}

On the same run as above, the two methods differ on exactly the pair that matters:

Comparing e3 and e6 gives concurrent (neither vector is ≤ the other), while Lamport said e6 came first. Comparing e3 and e7 gives before, which is correct: e3 → e4 → e5 → e7 through the messages.

Checking the claim

I did not want to rely on the proof alone. I generated 10,000 random executions (4 processes, 40 steps, random sends and receives), computed the true happened-before relation by transitive closure, and compared. Result over all 6.7 million pairs: the vector clock verdict matched the true relation every single time, concurrent pairs included.

Using it: detecting a write conflict

This is the use case that made vector clocks well known: Amazon's Dynamo, and databases in its lineage such as Riak. Two replicas accept writes to the same cart starting from the same version:

base := VClock{"A": 1}
wa := base.Copy(); wa.Tick("A")   // replica A writes: [A:2]
wb := base.Copy(); wb.Tick("B")   // replica B writes: [A:1 B:1]
Compare(wa, wb)                   // Concurrent

Neither version is ≤ the other, so the system knows it holds two siblings, not a newer and an older version. A newer-wins rule on wall-clock time would have deleted one without telling anyone. Here the database can hand both to the application to merge (take the union of the cart items, for example). The client then writes the merge with a clock that dominates both:

merged := wa.Copy(); merged.Recv("A", wb)  // [A:3 B:1]
Compare(wa, merged)  // Before
Compare(wb, merged)  // Before

The merged version is strictly greater than both siblings, so the conflict is resolved and both old versions can be discarded. Keep this picture in mind. The operation "take the component-wise maximum" is a join, the smallest vector that is above both inputs. It is associative, commutative and idempotent, and the next article in the series, on CRDTs, is built on exactly that property.

Costs and alternatives

• Size grows with the number of processes. A vector has one entry per writer, so every message and every stored value carries O(n) extra data. Systems with many short-lived clients need pruning or smarter variants such as dotted version vectors.
• Concurrent writes still need a decision. Detecting a conflict is not resolving it. Dynamo-style systems hand siblings to the application, others pick a rule such as last-writer-wins and accept losing data.
• Hybrid logical clocks (HLC) combine a physical timestamp with a Lamport-style counter. They keep a constant size and stay close to real time, which is why systems such as CockroachDB use them. Like Lamport clocks, they preserve causality but cannot detect concurrency.
• Physical clocks can be enough if you pay for it. Google's Spanner bounds clock uncertainty with special hardware and waits it out. That is an engineering answer where this article gave a mathematical one.

Takeaways

• Wall clocks cannot order events across machines. What you want is the happened-before relation, a partial order built from local sequence and messages.
• In a partial order some pairs are incomparable. Those are the concurrent events, and they are where conflicts live.
• Lamport clocks keep one counter: a → b implies L(a) < L(b), but not the reverse. In my test they made 90% of concurrent pairs look ordered. Use them when any consistent order is enough.
• Vector clocks keep one counter per process and compare component-wise: a → b if and only if V(a) < V(b). They detect concurrency exactly, at O(n) cost per message.
• The component-wise maximum used to merge clocks is a join, the same operation that powers CRDTs.

Next in the series: CRDTs, and how the join operation lets replicas merge without conflicts.