Catalog My learning Blog
Distributed Systems Explained: CAP, Clocks and Replication · Phase 1 · Lesson 4 · 6 min read

Lamport Timestamps vs Vector Clocks

On this page
  1. The happened-before relation
  2. Lamport timestamps
  3. Vector clocks
  4. Lamport timestamps and vector clocks in Python
  5. How vector clocks detect concurrent events
  6. Where each logical clock is used
  7. Hybrid logical clocks (HLC)
  8. Check yourself

The happened-before relation

Since physical clocks can't order events across machines (Day 3), Leslie Lamport's 1978 paper proposed ordering by causality. Event a happened before event b (written a → b) if:

  • they're on the same process and a came first, or
  • a is sending a message and b is receiving that message, or
  • there's a chain: a → c and c → b.

If neither a → b nor b → a, the events are concurrent: neither could have influenced the other.

Lamport timestamps

Each process keeps one counter:

  1. Before each local event or send, increment the counter.
  2. Attach the counter to every message sent.
  3. On receive, set the counter to max(own, received) + 1.

This guarantees: if a → b, then L(a) < L(b). The reverse doesn't hold.

Vector clocks

Each process keeps a counter per process:

  1. On a local event or send, increment its own entry.
  2. Attach the whole vector to messages.
  3. On receive, take the element-wise maximum, then increment its own entry.

Comparing two vectors: if every entry of A is ≤ B's (and they differ), A happened before B. If each has an entry larger than the other's, they're concurrent.

Lamport timestamps and vector clocks in Python

Python
# clocks.py: Lamport timestamps and vector clocks for three processes
class Process:
    def __init__(self, name, names):
        self.name, self.lamport = name, 0
        self.vc = {n: 0 for n in names}

    def local(self, label):
        self.lamport += 1
        self.vc[self.name] += 1
        print(f"{label:<8} {self.name}  L={self.lamport}  V={self.vc}")

    def send(self, label):
        self.local(label)
        return self.lamport, dict(self.vc)        # timestamp travels with the message

    def receive(self, label, msg):
        l, v = msg
        self.lamport = max(self.lamport, l) + 1
        for n in self.vc:
            self.vc[n] = max(self.vc[n], v[n])
        self.vc[self.name] += 1
        print(f"{label:<8} {self.name}  L={self.lamport}  V={self.vc}")

names = ["A", "B", "C"]
A, B, C = (Process(n, names) for n in names)
m1 = A.send("a1 send")        # A sends to B
C.local("c1")                 # C works independently
B.receive("b1 recv", m1)
m2 = B.send("b2 send")        # B sends to C
C.receive("c2 recv", m2)
Code
a1 send  A  L=1  V={'A': 1, 'B': 0, 'C': 0}
c1       C  L=1  V={'A': 0, 'B': 0, 'C': 1}
b1 recv  B  L=2  V={'A': 1, 'B': 1, 'C': 0}
b2 send  B  L=3  V={'A': 1, 'B': 2, 'C': 0}
c2 recv  C  L=4  V={'A': 1, 'B': 2, 'C': 2}
Messages carry timestamps between processes; Lamport clocks give one number per event, while vector clocks keep a counter per process and reveal concurrency.
Messages carry timestamps between processes; Lamport clocks give one number per event, while vector clocks keep a counter per process and reveal concurrency.

How vector clocks detect concurrent events

  • c1 and b1: Lamport says 1 < 2, which might suggest c1 happened first. But c1 is local to C and never influenced B. The vectors {C:1} and {A:1, B:1} each have an entry the other lacks: concurrent. Lamport timestamps can't tell you that; vector clocks can.
  • a1 → c2: the chain a1 → b1 → b2 → c2 shows up as {A:1, B:0, C:0} ≤ {A:1, B:2, C:2} in every entry: a1 happened before c2.

Where each logical clock is used

  • Lamport timestamps give a cheap total order (break ties by process id) consistent with causality: useful for ordering log entries or as version numbers.
  • Vector clocks (and their relatives, version vectors and dotted version vectors) detect concurrent updates to the same data in multi-writer stores, so conflicts aren't silently overwritten (Day 10). Their cost is size: one entry per writer.
  • Hybrid logical clocks combine physical time with a logical counter, staying close to wall time while preserving causality. CockroachDB and YugabyteDB use them; the next section shows how they work.

Hybrid logical clocks (HLC)

Lamport timestamps respect causality but say nothing about real time: L=4 could mean a second ago or last week. Wall clocks are readable, but they can put a cause after its effect (Day 3). A hybrid logical clock (Kulkarni and colleagues, 2014) keeps the useful half of each. A timestamp is a pair (l, c): l is the largest wall-clock time the node has seen, from its own clock or from any message it received, and c is a counter that breaks ties while l stays the same.

Python
# hlc.py: a hybrid logical clock (Kulkarni and colleagues, 2014)
class HLC:
    def __init__(self, name, physical):
        self.name, self.pt = name, physical     # pt() returns this node's wall clock, in ms
        self.l, self.c = 0, 0                   # l: largest wall time seen; c: counter for ties

    def now(self):                              # local event or send
        l_old = self.l
        self.l = max(l_old, self.pt())
        self.c = self.c + 1 if self.l == l_old else 0
        return (self.l, self.c)

    def receive(self, msg):
        l_old, (l_m, c_m) = self.l, msg
        self.l = max(l_old, l_m, self.pt())
        if self.l == l_old == l_m:  self.c = max(self.c, c_m) + 1
        elif self.l == l_old:       self.c += 1
        elif self.l == l_m:         self.c = c_m + 1
        else:                       self.c = 0
        return (self.l, self.c)

a = HLC("A", lambda: 1000)                      # A's clock reads 1000 ms
b = HLC("B", lambda: 900)                       # B's clock is 100 ms behind
m = a.now();        print("A sends   ", m)
print("B receives", b.receive(m))
print("B writes  ", b.now())
print("B writes  ", b.now())
Code
A sends    (1000, 0)
B receives (1000, 1)
B writes   (1000, 2)
B writes   (1000, 3)

B's own clock reads 900, but B has seen a message stamped 1000, so its timestamps stay at 1000 and the counter climbs. Everything B does after the receive sorts after A's send, even though B's clock is 100 ms behind. Once B's clock passes 1000, l follows the wall clock again and c drops back to 0.

That gives HLC three useful properties: timestamps stay within the clock skew of real time, so you can read them as dates and query by time; if a happened before b, a's timestamp is smaller; and they're compact, a wall time plus a small counter, whatever the number of nodes. What HLC can't do is detect concurrency: like Lamport timestamps, it produces one total order. CockroachDB stamps every transaction with an HLC and pairs it with a configured maximum clock offset (500 ms by default). When a read finds a value whose timestamp falls within that offset of its own, it can't be sure which came first, so it restarts at a later timestamp.

Check yourself

Not necessarily; the two events may be concurrent. Lamport timestamps only guarantee one direction: if a happened before b, then L(a) < L(b). To tell causality from concurrency, you need vector clocks.

They're concurrent. The first has a larger A entry and the second a larger B entry, so neither is greater than or equal to the other in every position, meaning neither event could have seen the other.

They need to detect concurrent updates to the same item, which only vector clocks reveal, so conflicts can be resolved instead of overwritten.

(1000, 2): the receive itself becomes (1000, 1) because l keeps the largest time seen, and the next event increments the counter, so B's events sort after A's send even though B's clock is behind.

Their size grows with the number of nodes or writers, so systems with many clients need pruning or a fixed set of server-side entries.