A system uses vector clocks with one integer slot per process. Walk through the update rules for incrementing and merging a vector clock, and explain precisely how comparing two vector clocks lets you detect that two events are concurrent rather than causally ordered.

## The update rules A **vector clock** generalizes Lamport's single counter into an array with one slot per participating process, `VC = [c1, c2, ..., cn]`, held locally by every process and attached to outgoing messages. The update rules mirror Lamport's but operate **elementwise**. - **On any local event**, a process increments only its own index in its own vector -- e.g., process P2's local event bumps `VC[2]` and leaves every other slot untouched. - **On sending a message**, the process attaches its current full vector. - **On receiving a message** carrying vector `VCmsg`, the receiver sets its own vector to the elementwise maximum of its current vector and `VCmsg` (`VC[i] = max(VC[i], VCmsg[i])` for every `i`), and then increments its own index by one to record the receive as a new local event. Concretely, with three processes A, B, C: if A is at `[3,0,0]` and sends to B, who is at `[1,4,0]`, B first takes elementwise `max([1,4,0],[3,0,0]) = [3,4,0]`, then increments its own slot to get `[3,5,0]`. ## Why a single counter falls short This machinery exists because a single Lamport counter, by collapsing every event onto one number line, necessarily discards the information needed to tell 'a caused b' apart from 'a and b are unrelated' -- both cases can produce `LC(a) < LC(b)`. Vector clocks fix this by keeping enough state (one counter per process) that the full happens-before partial order can be reconstructed exactly from the vectors alone, with no false positives or negatives, given N covers every participating process. ## The comparison rule The comparison rule is what unlocks this. Given two vectors of the same length, define `VC(a) ≤ VC(b)` to mean every entry of `VC(a)` is less than or equal to the corresponding entry of `VC(b)`. Then `a → b` exactly when `VC(a) ≤ VC(b)` and `VC(a) ≠ VC(b)` -- every slot at least as large, and at least one strictly larger. If instead neither vector dominates the other -- for example `VC(a) = [3,4,0]` and `VC(b) = [2,5,0]`, where a leads in slot 1 but b leads in slot 2 -- then a and b are **concurrent**, written `a || b`, because the only way one could have happened-before the other is if it fully 'knew about' everything the other did, and here each vector reflects knowledge the other lacks. | What the two vectors look like | The verdict | |---|---| | `VC(a) ≤ VC(b)` and `VC(a) ≠ VC(b)` | `a → b` | | `VC(a) = [3,4,0]` against `VC(b) = [2,5,0]`, where a leads in slot 1 but b leads in slot 2 | concurrent | This is precisely the capability Lamport timestamps cannot offer: a mechanical, purely-local way to detect true concurrency, not just impose an arbitrary total order. ## The cost of that power The cost of that power is real. A vector clock needs one slot per participant, so its size is `O(n)` where n is the number of processes or replicas that can independently generate events -- this must be attached to every message and stored with every version of data, and the comparison itself costs `O(n)` time. - In a system with a fixed, small, known set of processes, this is entirely manageable. - In a system where the participant set grows without bound, vector clocks become impractical, both in message overhead and in the bookkeeping needed to know which slot belongs to which process; this scalability wall is exactly why version vectors and pruning/garbage-collection strategies exist. ## Sibling explosion in production In production, the visible failure mode of vector-clock-based conflict detection is **'sibling explosion'**: when concurrent writes are detected, the system can't safely pick a winner automatically, so it keeps both versions as siblings and pushes the merge decision up to the application or the next client read. If writes to a hot key happen concurrently across many replicas faster than clients read and resolve them, siblings can accumulate unboundedly, bloating storage and forcing increasingly complex merges -- a well-documented operational pain point. Amazon's **Dynamo** paper (2007) is the canonical real-world case study: it uses vector clocks explicitly to detect concurrent updates to the same key across replicas in a leaderless, eventually-consistent design, returning all conflicting sibling versions to the client for application-level reconciliation rather than silently picking a 'winner' the way naive last-write-wins would. **Riak**, built on the same lineage, inherited this same vector-clock-based sibling model and the same operational tuning challenges around vector growth and pruning.