Vector Clocks and the Detection of Concurrency

A scalar logical clock answers “in what order” but not “were these two related”. Getting the second answer requires keeping enough state to represent the partial order itself rather than a linear extension of it, the distinction drawn in Happens-Before and the Scalar Logical Clock. The representation that does this is a vector of counters, one per process, and its comparison is a componentwise partial order rather than a single integer comparison.

The representation

With n processes, each process i keeps a vector V_i of length n. The entry V_i[j] counts the events of process j that process i knows about, including its own. The update rules mirror the scalar ones:

• Initially all entries are zero.
• Before executing an event, process i increments its own entry: V_i[i]++.
• When i sends a message, it attaches a copy of V_i.
• When i receives a message with vector W, it sets V_i[j] = max(V_i[j], W[j]) for every j, then increments V_i[i].

The merge is a componentwise maximum followed by the local increment. The vector attached to a message carries the sender’s entire knowledge, so the receiver learns not only how many events the sender had performed but how much the sender knew about every other process. Information about third parties propagates transitively: if i learns from j that j knew of k’s fifth event, then i’s vector records k’s fifth event as causally preceding this receipt.

Every message carries a vector of the same length, whichever process sent it, so a receiver can compare the incoming vector against its own without needing to know which index the sender occupies. The alternative encoding, where a process transmits only its own counter, carries no information about third parties and therefore cannot detect concurrency at all.

Comparing two vectors

The comparison is componentwise and yields three outcomes rather than two:

• V_a < V_b when V_a[j] ≤ V_b[j] for all j, and V_a[j] < V_b[j] for at least one. Then a → b.
• V_a > V_b under the symmetric condition. Then b → a.
• Otherwise, with at least one component larger in each direction, a ∥ b.

The third case is the point. A single comparison identifies concurrency directly, without needing to know the message graph.

def happens_before(a, b):
    """Compare two causal histories of equal length."""
    assert len(a) == len(b)
    le = all(x <= y for x, y in zip(a, b))
    lt = any(x < y for x, y in zip(a, b))
    return le and lt

def concurrent(a, b):
    return not happens_before(a, b) and not happens_before(b, a)

The two functions are exact for the happens-before relation defined by the execution that produced the vectors. If a → b, the vectors satisfy the strict componentwise inequality; if the vectors satisfy it, a → b. The equivalence is a theorem about the construction, not an approximation, provided the vector has an entry for every process that ever participated.

What the extra state buys

The canonical application is conflict detection in a replicated key-value store. Each write to a key is stamped with the writing replica’s vector. A replica receiving a write compares the incoming vector with the vector of the version it currently holds:

• If the incoming vector is greater, the incoming write supersedes the stored one and the store replaces it.
• If it is less, the write is stale and the store discards it or returns the newer version.
• If the two are concurrent, the store keeps both as siblings and hands the conflict to the application, which resolves it by some domain rule and writes a new version whose vector is the componentwise maximum of the two, plus one.

Keeping both siblings is the semantically honest choice, and it is the behaviour of several well-known eventually consistent stores. It requires the store to keep a set of values per key rather than a single value, which is the storage cost of not losing writes. A last-write-wins register avoids that cost by discarding one sibling, and it can only do so because it has abandoned the ability to detect the conflict in the first place.

The same mechanism detects causal dependencies in debugging and tracing: given two log records, a tool can state whether one caused the other or whether they were independent, which is the question an operator actually asks when two failures appear near each other in time.

The size problem

A vector clock has one entry per process, so its size grows linearly with the number of participants. For ten processes that is ten integers; for a thousand it is a thousand. Each entry is typically 4 or 8 bytes on the wire, and every message carries the whole vector, so per-message overhead grows with cluster size even though most messages carry no new information about most processes.

The overhead is not merely bandwidth. Comparing two vectors costs O(n), and a store that must compare against many versions pays that cost per comparison. The entries are also mostly redundant: a process that has been idle for a long time still occupies a slot, and a process that has left still occupies a slot if its departure is not handled.

Practical systems reduce the cost in three ways. The first is sparse encoding, transmitting only the nonzero entries as index-value pairs, which helps when the number of processes that have actually interacted with the sender is small. The second is to bound the number of participants that can write to a given key, so that the vector length is a property of the key’s replica set rather than the whole cluster. The third is to change the representation entirely, replacing fixed slots with a structure that tolerates membership change, which is the subject of Interval Tree Clocks and Membership Change.

None of these removes the fundamental scaling: the exact detection of concurrency needs state proportional to the number of independent sources of events, and no encoding compresses that below the information-theoretic minimum for arbitrary patterns of communication.

Where vectors are weaker than they look

A vector clock orders events, not versions of a value. If a process writes a key, then writes it again, the second write’s vector dominates the first, and a replica that receives only the second cannot distinguish “one write superseded another” from “one write happened” — both look like a single version with a larger vector. Version vectors, which are the variant used in practice for replicated data, attach a vector per key and count writes to that key rather than all events at the process, which makes the comparison meaningful at the granularity of the object.

The distinction matters for correctness. Causal histories that include unrelated events inflate the vector without changing the ordering of writes to a particular key, so a store comparing raw vector clocks will treat two versions as ordered when the ordering came from an unrelated event on one replica. Version vectors avoid this by incrementing only on writes to the object, and the sibling-keeping rule then triggers exactly when two writes to the same key were concurrent.

There is also an assumption about the observation of messages. The construction assumes a message is delivered exactly once and that the receiver’s vector reflects every message it has processed. A protocol that drops, duplicates, or reorders messages must still ensure the vector merge happens once per logical send, or the counters drift from the actual causal history. Deduplication by message identity, not by vector value, is the usual safeguard.

Vector clocks are the exact encoding of a partial order and the first place where the cost of exactness becomes visible. Every subsequent mechanism in this cluster trades some of that exactness for a smaller representation, a cheaper comparison, or a bounded message size.