Logical Clocks: Happens-Before, Lamport Clocks and Vector Clocks

Version note: The code in this post was built and run with C# 14 and .NET 10.

Guess First

Bookstore has three services: Catalog (C), Pricing (P) and Search (S). Catalog updates a book title (a) and sends a BookUpdated message to Pricing (b). Meanwhile Pricing, unaware of Catalog, changes a price (d) and then receives the message (e). Search minds its own business: it loads its configuration, then rebuilds its index (f), and talks to nobody.

Instead of reading a clock, each service keeps a counter, and according to those counters d gets 1 and f gets 2. 1 is less than 2. Does that mean d happened before f and could have influenced it? Would a debugging tool that sorts the logs by these counters tell you a true story?

Happens-Before: Ordering Without a Clock

In the previous post we saw that physical clocks are not reliable for ordering events on different machines. In his 1978 paper "Time, Clocks, and the Ordering of Events in a Distributed System", Leslie Lamport turned the question around: can we answer "which came first?" without looking at a clock at all? He built the answer on a relation that can be observed entirely within the system: happens-before, written a → b.

The definition has three rules. If a came before b in the same process, a → b. If a is the sending of a message and b is the receipt of that same message, a → b. And transitivity: if a → b and b → c, then a → c. Two events that cannot be connected by these rules are concurrent (a ∥ b). Concurrent does not mean "at the same time"; it means "could not have known about each other". There is no chain of messages between Search's event f and Pricing's event d, so whichever happened first in physical time, they are concurrent: neither could have influenced the other.

Happens-before is the distributed system counterpart of causality in physics. Lamport says explicitly in the paper that he borrowed the analogy from special relativity: if not even a signal at the speed of light can travel between two events, the question of which came first has no observer-independent answer. In a distributed system, messages take the place of light.

Lamport Clocks

Lamport's second step is to produce numbers consistent with happens-before. Each process keeps a counter. On every local event and every message send it increments the counter and attaches it to the outgoing message. When it receives a message, it sets its counter to one more than the larger of its own value and the value in the message:

namespace Bookstore.Clocks;

public sealed class LamportClock
{
    public long Time { get; private set; }

    // Local event or send: increment
    public long Tick() => ++Time;

    // Receive: max(local, received) + 1
    public long Receive(long received)
    {
        Time = Math.Max(Time, received) + 1;
        return Time;
    }
}

These rules give the following guarantee: if a → b, then L(a) < L(b). An event gets a larger number than every event that causally precedes it. If you break ties by process identity (counter first, process id if equal), you get a total order over all events that is consistent with happens-before. Lamport uses that total order for a distributed mutual exclusion algorithm in the paper; today the same idea underlies total order broadcast and consensus-based systems.

Let us run the opening scenario:

using Bookstore.Clocks;

// Three processes: Catalog (C), Pricing (P), Search (S)
LamportClock c = new(), p = new(), s = new();
long a = c.Tick();            // a: C updates a book title
long b = c.Tick();            // b: C sends "BookUpdated" to P
long d = p.Tick();            // d: P changes a price, unaware of C
long e = p.Receive(b);        // e: P receives the message
s.Tick();                     // S loads its configuration
long f = s.Tick();            // f: S rebuilds its index, talks to nobody
Console.WriteLine($"Lamport  a={a} b={b} d={d} e={e} f={f}");

Lamport  a=1 b=2 d=1 e=3 f=2

d got 1 and f got 2. But the converse does not hold: L(d) < L(f) does not mean d → f. The guarantee goes one way only: happens-before determines the order of the numbers, the order of the numbers does not determine happens-before. A Lamport clock cannot tell you whether two events are concurrent. If you merge the Search and Pricing logs by Lamport timestamp, you put d before f, and the reader assumes d may have led to f. The order is consistent, but the causality information is gone. Look at a and d as well: both are 1. A total order needs ties broken by process id.

Vector Clocks: Detecting What Is Concurrent

A single counter is not enough to detect concurrency; each process needs to know how much of every other process it has "seen". The vector clock, proposed independently by Colin Fidge and Friedemann Mattern in 1988, does exactly that: each process keeps a vector with N entries, increments its own slot on every event, merges vectors slot by slot with the maximum when it receives a message, and then increments its own slot.

using System.Collections.Immutable;

namespace Bookstore.Clocks;

public enum Ordering { Before, After, Equal, Concurrent }

public sealed record VectorClock(ImmutableSortedDictionary<string, long> Entries)
{
    public static VectorClock Empty { get; } = new(ImmutableSortedDictionary<string, long>.Empty);

    public long this[string node] => Entries.GetValueOrDefault(node);

    public VectorClock Increment(string node) => new(Entries.SetItem(node, this[node] + 1));

    // Element-wise maximum, used on receive
    public VectorClock Merge(VectorClock other)
    {
        ImmutableSortedDictionary<string, long> merged = Entries;
        foreach ((string node, long value) in other.Entries)
        {
            merged = merged.SetItem(node, Math.Max(this[node], value));
        }
        return new VectorClock(merged);
    }

    public Ordering Compare(VectorClock other)
    {
        IEnumerable<string> nodes = Entries.Keys.Union(other.Entries.Keys);
        bool less = false, greater = false;
        foreach (string node in nodes)
        {
            if (this[node] < other[node]) less = true;
            if (this[node] > other[node]) greater = true;
        }
        return (less, greater) switch
        {
            (false, false) => Ordering.Equal,
            (true, false) => Ordering.Before,
            (false, true) => Ordering.After,
            _ => Ordering.Concurrent
        };
    }

    public override string ToString() => "[" + string.Join(", ", Entries.Select(e => $"{e.Key}:{e.Value}")) + "]";
}

The comparison rule: if every slot of V(a) is less than or equal to the corresponding slot of V(b) and at least one is strictly less, then a → b. If some slots are smaller and others larger, a ∥ b. Unlike the Lamport clock, this rule works in both directions: a → b if and only if V(a) < V(b). The same scenario with vectors:

VectorClock vc = VectorClock.Empty, vp = VectorClock.Empty, vs = VectorClock.Empty;
VectorClock va = vc = vc.Increment("C");
VectorClock vb = vc = vc.Increment("C");
VectorClock vd = vp = vp.Increment("P");
VectorClock ve = vp = vp.Merge(vb).Increment("P");
vs = vs.Increment("S");
VectorClock vf = vs = vs.Increment("S");
Console.WriteLine($"Vector   a={va} b={vb} d={vd} e={ve} f={vf}");
Console.WriteLine($"d vs f : Lamport {d} < {f}? {d < f}, vector says {vd.Compare(vf)}");
Console.WriteLine($"b vs e : vector says {vb.Compare(ve)}");
Console.WriteLine($"a vs d : Lamport {a} == {d}, vector says {va.Compare(vd)}");

Vector   a=[C:1] b=[C:2] d=[P:1] e=[C:2, P:2] f=[S:2]
d vs f : Lamport 1 < 2? True, vector says Concurrent
b vs e : vector says Before
a vs d : Lamport 1 == 1, vector says Concurrent

The vector clock gives the right answer for d and f, which Lamport ordered as 1 < 2: concurrent. There is a message between b and e, so b → e. a and d had the same Lamport value; the vectors say they are concurrent too. The price is obvious: the timestamp is no longer a single number but a map with as many entries as there are processes. Trivial for three services, but in a system where thousands of clients write directly, attaching a vector with thousands of entries to every message is impractical.

Testing Concurrency with xUnit

The edge cases of this kind of code (missing slots, comparing with itself, incrementing after a merge) are easy to miss by eye. Let us pin the behavior down with three small tests:

using Bookstore.Clocks;
using Xunit;

namespace Bookstore.Clocks.Tests;

public class VectorClockTests
{
    [Fact]
    public void Message_creates_happens_before()
    {
        VectorClock sent = VectorClock.Empty.Increment("C");
        VectorClock received = VectorClock.Empty.Increment("P").Merge(sent).Increment("P");

        Assert.Equal(Ordering.Before, sent.Compare(received));
        Assert.Equal(Ordering.After, received.Compare(sent));
    }

    [Fact]
    public void Independent_updates_are_concurrent()
    {
        VectorClock onCatalog = VectorClock.Empty.Increment("C");
        VectorClock onPricing = VectorClock.Empty.Increment("P");

        Assert.Equal(Ordering.Concurrent, onCatalog.Compare(onPricing));
    }

    [Fact]
    public void Lamport_order_does_not_imply_causality()
    {
        LamportClock pricing = new(), search = new();
        long d = pricing.Tick();
        search.Tick();
        long f = search.Tick();

        Assert.True(d < f);  // the timestamps are ordered...
        Assert.Equal(Ordering.Concurrent,  // ...but the events are not
            VectorClock.Empty.Increment("P").Compare(VectorClock.Empty.Increment("S").Increment("S")));
    }
}

Passed!  - Failed:     0, Passed:     3, Skipped:     0, Total:     3, Duration: 10 ms - Clocks.Tests.dll (net10.0)

The third test puts the main idea of this post into code: the Lamport timestamps are ordered, but the events are concurrent. If you see the sentence "we sort these two events by Lamport timestamp, so d came before f" in a code review, this test shows why it is wrong.

Detecting Conflicts with Version Vectors

The most common practical use of vector clocks is conflict detection in replication. There they are usually called version vectors, with a small difference: the slots of the vector are replicas rather than processes, and a separate vector is kept per key. When a replica writes a key, it increments its own slot. When two replicas synchronize, they compare the two versions of the key: if one is greater, the older one is discarded; if they are concurrent, both are kept.

Amazon's 2007 Dynamo paper stored shopping carts exactly this way. When two replicas accepted concurrent writes to the same cart, Dynamo did not decide which one was "right"; it kept both versions (siblings) and handed both to the application on the next read, and the application merged the carts. The difference from last-write-wins (LWW) in the previous post is significant: LWW silently drops one of the concurrent writes, a version vector makes the conflict visible and leaves the resolution to code that understands the data. Systems such as Riak use refined variants like dotted version vectors to keep the vector from bloating as the number of clients grows. In the seventh post we will see a peculiar trap in merging carts, and in the eleventh, CRDTs (Conflict-free Replicated Data Types), which do this correctly by construction.

Hybrid Logical Clocks: Close to Physical Time, Faithful to Causality

Logical clocks have one shortcoming: their values mean nothing to a human. You cannot answer "show me the state at 14:00 yesterday" with a Lamport counter. And we have seen that physical clocks can break causality. The hybrid logical clock (HLC) proposed by Kulkarni and colleagues in 2014 combines the two: part of the timestamp comes from the physical clock, but it never falls behind the largest value it has seen or the value in an incoming message; when several events happen in the same millisecond or the clock is behind, a small counter covers the gap.

namespace Bookstore.Clocks;

public readonly record struct HlcTimestamp(long WallMs, int Counter) : IComparable<HlcTimestamp>
{
    public int CompareTo(HlcTimestamp other) =>
        WallMs != other.WallMs ? WallMs.CompareTo(other.WallMs) : Counter.CompareTo(other.Counter);

    public override string ToString() => $"{WallMs}.{Counter}";
}

// Hybrid logical clock (Kulkarni et al., 2014): close to physical time, but never goes backwards
public sealed class HybridLogicalClock(Func<long> physicalMs)
{
    private HlcTimestamp _last;

    public HlcTimestamp Now()
    {
        long pt = physicalMs();
        _last = pt > _last.WallMs ? new(pt, 0) : _last with { Counter = _last.Counter + 1 };
        return _last;
    }

    public HlcTimestamp Receive(HlcTimestamp remote)
    {
        long pt = physicalMs();
        long wall = Math.Max(pt, Math.Max(_last.WallMs, remote.WallMs));
        int counter = (wall == _last.WallMs, wall == remote.WallMs) switch
        {
            (true, true) => Math.Max(_last.Counter, remote.Counter) + 1,
            (true, false) => _last.Counter + 1,
            (false, true) => remote.Counter + 1,
            _ => 0
        };
        _last = new(wall, counter);
        return _last;
    }
}

Remember the LWW scenario from the previous post: B's clock was 300 milliseconds behind, and its newer write was lost because of that. This time B makes its write after receiving A's write through replication:

// Hybrid logical clock: server B's physical clock is 300 ms behind A's
long trueMs = 1_000_000;
HybridLogicalClock hlcA = new(() => trueMs);
HybridLogicalClock hlcB = new(() => trueMs - 300);
HlcTimestamp writeOnA = hlcA.Now();                 // price=450 on A
trueMs += 100;
HlcTimestamp seenOnB = hlcB.Receive(writeOnA);      // B replicates A's write
HlcTimestamp writeOnB = hlcB.Now();                 // price=399 on B, 100 ms later
Console.WriteLine($"HLC      A write={writeOnA} B receive={seenOnB} B write={writeOnB} B > A? {writeOnB.CompareTo(writeOnA) > 0}");

HLC      A write=1000000.0 B receive=1000000.1 B write=1000000.2 B > A? True

Even though B's physical clock is 200 milliseconds behind A's write, the timestamp B produces after seeing A's write is larger. The write that comes later causally also comes later by timestamp. Note that this does not fully solve the two-editor case from the previous post; had B written without seeing A's write, the two writes would be concurrent and the HLC could not know which one happened later in real time. An HLC preserves causality; it does not eliminate clock skew. CockroachDB and MongoDB use variants of this approach; in the eleventh post we will look at how CockroachDB combines HLC with NTP (Network Time Protocol) and an uncertainty interval.

Common Pitfalls

Mistaking Lamport order for causality. L(a) < L(b) only says "b cannot have happened before a", not "a led to b". If your question is about causality, you need a vector clock or explicit causal metadata.

Putting clients in the vector. The number of slots in a vector clock is the number of actors that write. If every user or every HTTP (Hypertext Transfer Protocol) request is an actor, the vector grows without bound. Slots should be few and long-lived: replicas or service instances.

Forgetting to increment your own slot after a merge. A receive is an event too. If you merge without incrementing, the sender's event and the receive event carry the same vector and look "equal".

Not breaking ties for a total order. Two processes can produce the same Lamport value. A second key (the process id) is required to make the order deterministic; otherwise different nodes put the same events in different orders.

Using an HLC as a substitute for clock synchronization. The physical part of an HLC follows the node with the fastest clock. If one node's clock runs an hour ahead, the HLC values of the whole system move an hour ahead and the counter bloats to cover it. That is why databases using HLCs monitor the maximum clock offset and stop a node when it is exceeded.

A Small Experiment

★☆☆ Extend the scenario: after f, Search sends a message to Catalog, which receives it and produces event g. What is the relationship between g and d? Guess on paper first, then confirm with the vector clock.

★★☆ Add a "merge is commutative" test to VectorClockTests: x.Merge(y) and y.Merge(x) must give the same vector. Then test that merge is idempotent (x.Merge(x)). Why do these two properties matter for replication?

★★★ Write a VersionedCart: every version carries a VectorClock and an ISet<string>. Add a Merge method that compares versions from two replicas, drops the older one and keeps concurrent ones as siblings. What happens when a book removed from the cart meets a concurrent add?

In this post we talked about the order of events. In the next post we move to copies of data: leader-based, multi-leader and leaderless replication, the quorum rule R + W > N, and a C# simulation showing what happens when a node goes down.