Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 36 ยท Time and Ordering

Vector Clocks and Causality

Build vector clocks in Python to tell causal order from concurrency, then see causal delivery and version vectors that detect conflicting writes.

A Lamport clock gives each event one number, and that number respects causality in one direction only: if a caused b, then a has the smaller number. But when you compare two stamps you cannot tell whether the smaller one caused the larger one or whether the two events were simply unrelated.

A vector clock fixes this by keeping one counter per node instead of one counter in total. With a vector you can answer a stronger question: did I see everything you saw? If yes, one event came after the other. If neither saw all of what the other saw, the events are concurrent, and the system knows it has a conflict. This is the foundation of causal ordering, of version vectors in databases like Dynamo-style stores, and of many collaborative editors.

The idea

For a cluster of n nodes, a vector clock is a list of n integers. Entry i means "how many events of node i I know about". Node i follows three rules:

  1. Local event or send: increment your own entry V[i]. A send attaches a copy of the whole vector.
  2. Receive: take the element-wise maximum of your vector and the message's vector, then increment your own entry.
  3. Compare two vectors V and W:
    • V โ‰ค W if every entry of V is โ‰ค the same entry of W.
    • V < W (V happened before W) if V โ‰ค W and they are not equal.
    • If neither V โ‰ค W nor W โ‰ค V, the events are concurrent.

Comparing two vectors

Before [2,1,0] vs [3,1,1]. Every entry is smaller or equal.
After Every entry is larger or equal. The mirror case.
Concurrent [2,0,0] vs [0,1,0]. Each is ahead in one place.
Equal Same history, same event.

Concurrent means neither saw the other, so there is a real conflict.

1 / 2

Unlike Lamport clocks, the vector comparison is exact: V(a) < V(b) if and only if a โ†’ b. You pay with space: the vector grows with the number of nodes.

Building a vector clock

We represent the vector as a dictionary from node name to counter, so that missing entries count as zero and the node set may change.

Python A vector clock class

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

a1 is before b1 because B received a message that already included a1's history. But b1 and c1 are concurrent: C acted without hearing from anyone, and B never heard from C. With a Lamport clock both b1 and c1 would simply have been given numbers, and you could not have told these two situations apart.

Testing the rules

A comparison function is exactly the kind of code that rewards a few quick property checks. The law we want: merging produces a clock that is after or equal to both inputs, and compare is antisymmetric.

Python Property checks for the vector clock

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The merge is commutative, associative and idempotent (merging twice changes nothing). Those three properties are what let replicas exchange clocks in any order, even repeatedly, and still agree. You will see the same trio again in CRDTs.

Causal broadcast

Vector clocks let a system deliver messages in an order that respects causality, called causal broadcast. Suppose Ada posts a question and Ben answers it. A third user Cleo might receive Ben's answer before Ada's question if the network reorders messages. That would look absurd. With vector clocks, the receiver buffers a message until everything that causally precedes it has been delivered.

The delivery rule for a message m from sender s with vector V, when the local delivered-vector is D: deliver only if V[s] == D[s] + 1 (it is the next message from s) and V[k] โ‰ค D[k] for every other node k (we already delivered everything s had seen).

Python Causal delivery buffer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The answer waits in the buffer until the question is delivered, then both are released in causal order. Messages that are truly concurrent are delivered in whatever order they arrive, since no order is required.

Version vectors in storage

Replicated databases use the same idea under the name version vector: each stored value carries a vector that counts the updates seen from each replica. When a client reads a value, it gets the vector; when it writes back, it sends the vector it read from. The server compares:

  • The write's vector is after the stored one: the client had seen the current value, so it is a plain update and replaces it.
  • The write's vector is before or equal: it is stale, so it is dropped or ignored.
  • The vectors are concurrent: two clients updated without seeing each other. Neither is right, so the store keeps both as siblings and lets the application (or a later write) resolve it.

Compare this with last-write-wins from the clock lesson: LWW throws away one of the concurrent writes silently, whereas version vectors notice the conflict and keep both. The next sections of the tutorial, multi-leader and leaderless replication and CRDTs, build on that.

Python Version vectors detect a conflicting write

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The shopping cart conflict is kept intact until a client reconciles it. That is the trade: more work for the application, no silent data loss.

Costs and alternatives

A vector with one entry per node is large when there are thousands of nodes or clients. Real systems limit it: they track replicas rather than clients, prune old entries, or use dotted version vectors, a refinement that avoids false conflicts. Hybrid and Lamport clocks are cheaper when you only need a consistent order and can tolerate ties being broken arbitrarily.

Matrix clocks

A vector clock tells a process what it knows about everyone's events. A matrix clock goes one level deeper: row i records what this process knows about what process i has seen, so entry m[i][j] means "process i has seen at least this many events of process j." The rules mirror vector clocks: increment your own diagonal entry on every event, attach the whole matrix to each message, and on receipt take the element-wise maximum, then also fold the sender's own row into yours.

The payoff is that a process can tell when information is globally known. If the smallest value in column j is k, every process has seen at least k events of j, so older log entries, tombstones or buffered messages can be discarded safely. The price is n * n numbers per message, so matrix clocks are rare outside garbage-collection protocols and teaching.

Python A matrix clock and the safe-to-discard check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After the first exchange A knows B has seen A's events, but not C. Only after C and B report back does the minimum of column 0 rise, and A may drop events up to that count.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Two vector clocks are [2,0,0] and [0,1,0]. How do the events relate?

    Each vector is larger in one entry and smaller in another, so neither history contains the other. The events are concurrent.
  2. 2. What does a node do with its vector when it receives a message?

    The maximum captures everything either side has seen, and the increment records the receive event itself.
  3. 3. What advantage do vector clocks have over Lamport clocks?

    With vectors, V(a) < V(b) holds exactly when a happened before b. A single Lamport number cannot detect concurrency.
  4. 4. A store receives a write whose version vector is concurrent with the stored one. What should a version-vector store do?

    Concurrent writes are a true conflict. Keeping siblings avoids the silent data loss that last-write-wins can cause.
  5. 5. In causal broadcast, why would a receiver buffer a message?

    A message must wait until everything that causally precedes it has been delivered, so effects never show up before their causes.

Summary

  • A vector clock keeps one counter per node; increment your own on events, take the element-wise maximum on receive.
  • Comparing vectors gives before, after, equal or concurrent, exactly matching happens-before.
  • Merge is commutative, associative and idempotent, so replicas can exchange clocks in any order.
  • Causal broadcast buffers messages until their causes are delivered.
  • Version vectors in storage detect conflicting writes and keep siblings instead of silently dropping one.
  • The price is space proportional to the number of participants.

Next: Messages, RPC and Delivery Guarantees, where nodes start talking over an unreliable network.