On this page

Causality, Version Vectors & Dotted Version Vectors

A replicated key-value store holds two versions of the same key. Which one should a reader get? If one version was written by a client who had seen the other, the answer is obvious: the newer one supersedes the older. If the two were written independently — two people editing the same shopping cart on two phones at once — neither supersedes the other, and throwing either away loses data.

The whole problem reduces to one question: given two versions, is one in the causal past of the other, or are they concurrent? Wall-clock timestamps cannot answer it (Clock Synchronization explains why), and last-write-wins pretends the question does not exist. This page is about the data structures that answer it exactly — and about the surprisingly subtle ways the obvious structures get it wrong in a real database.

The Vector Clocks & Lamport Timestamps page covers the mechanics of logical clocks from first principles: Lamport's rules, vector clock rules and their proofs, and hybrid logical clocks. This page builds on it and goes where that page stops — to the specific problem of versioning replicated data:

  1. Total vs partial orders, and why causality is a partial order
  2. Happens-before and concurrency — a short recap
  3. What Lamport clocks cannot tell you
  4. Version vectors vs vector clocks — the distinction that most explanations blur
  5. Conflict detection with siblings in a client–server store
  6. Choosing actors: why both obvious choices fail
  7. The sibling-explosion problem, worked through step by step
  8. Dotted version vectors — how a single "dot" fixes it, with a worked example and code
  9. Interval tree clocks, briefly
  10. How Dynamo, Riak and friends actually use these structures
  11. Causal consistency and causal broadcast

1. Total Orders and Partial Orders

1.1 Definitions

An order is a relation that says when one thing comes "before" another. Two kinds matter here.

A strict partial order < on a set is a relation that is:

  • Irreflexive: nothing comes before itself (not a < a)
  • Transitive: if a < b and b < c then a < c
  • (and therefore asymmetric: if a < b then not b < a)

A total order is a partial order in which every pair is comparable: for any distinct a and b, either a < b or b < a.

The difference is the pairs that are incomparable. In a partial order, some pairs have no order at all. In a total order, there are no such pairs.

ExampleKindIncomparable pairs?
Integers by <TotalNone
Sets ordered by ⊂ (proper subset)Partial{1} and {2} — neither contains the other
Git commits ordered by "is an ancestor of"PartialTwo branches' tips
Tasks ordered by "must finish before" (a build graph)PartialIndependent tasks
Events in one single-threaded process, by program orderTotalNone
Events across a distributed system, by causalityPartialConcurrent events

1.2 Linear extensions

Any partial order can be extended to a total order that respects it — by breaking ties between incomparable elements in some arbitrary way. A topological sort of a DAG is exactly this. There are usually many possible linear extensions, and nothing in the partial order tells you which one is "right".

That is the core insight of this page in miniature. Causality is a partial order. Lamport timestamps and wall-clock timestamps impose one particular total order on top of it. They are useful for breaking ties deterministically, but the tie-breaks are arbitrary — and if you use them to decide which write to discard, you are discarding data based on an arbitrary choice.

flowchart LR
    A["a: x=1"] --> B["b: read x, set y=2"]
    A --> C["c: set z=3"]
    B --> D["d: read y and z, set w=4"]
    C --> D

In this causal graph, a precedes everything, d follows everything, but b and c are incomparable. Both "a, b, c, d" and "a, c, b, d" are valid linear extensions. A timestamp-based system picks one of them; a causality-tracking system knows that b and c are concurrent.


2. Happens-Before and Concurrency

Lamport's 1978 happens-before relation (→) is the smallest relation satisfying:

  1. If a and b are events in the same process and a comes first, then a → b.
  2. If a is the sending of a message and b is its receipt, then a → b.
  3. If a → b and b → c, then a → c.

Two events are concurrent (a ∥ b) when neither a → b nor b → a. "Concurrent" here does not mean "at the same instant": it means neither could have influenced the other. Two events a day apart are concurrent if no chain of messages connects them.

sequenceDiagram
    participant P as Process P
    participant Q as Process Q
    participant R as Process R
    Note over P: p1 — local event
    P->>Q: m1 (sent at p2)
    Note over Q: q1 — receive m1
    Note over R: r1 — local event
    Q->>R: m2 (sent at q2)
    Note over R: r2 — receive m2
    Note over P,R: p1 → p2 → q1 → q2 → r2, but r1 is concurrent with p1, p2, q1 and q2

The full treatment, including proofs, is in Vector Clocks & Lamport Timestamps. For this page, the important facts are:

  • → is a strict partial order on events.
  • Potential causality, not actual causality. a → b means a could have influenced b. Whether b's logic actually used information from a is invisible to the system.
  • For data versioning, we care about a narrower question: did the writer of version y know about version x when it wrote y? If so, y supersedes x. If neither writer knew about the other's version, they are concurrent.

3. What Lamport Clocks Cannot Tell You

A Lamport clock assigns each event an integer L such that if a → b then L(a) < L(b). The converse does not hold:

  • L(a) < L(b) is consistent with a → b, but also with a ∥ b.
  • L(a) = L(b) for distinct events implies a ∥ b — but concurrent events usually do not have equal timestamps.

3.1 A worked example

EventProcessLamport timestampCausal relationships
x1: write cart = [milk]Client P1—
x2: write cart = [eggs]Client Q, which has done 4 unrelated things first5Concurrent with x1
x3: read cart, write [milk, bread]Client P2After x1 only

Sort by Lamport timestamp: x1 (1), x3 (2), x2 (5). A last-writer-wins store using these timestamps keeps x2 = [eggs] and silently discards x3 = [milk, bread] — even though x3 and x2 are concurrent, and the user who wrote x3 never saw x2. Lamport timestamps produced a valid linear extension of causality, but they cannot tell you that x2 and x3 are concurrent, and so cannot tell you that discarding one of them loses information.

3.2 What each mechanism can answer

QuestionWall clockLamport clockVector clock / version vector
Deterministic total order for tie-breaking?Yes (if no ties)Yes, with process ID tie-breakNo (by design)
If a → b, does the timestamp say a < b?Not guaranteed (skew)YesYes
If timestamp(a) < timestamp(b), did a → b?NoNoYes
Can it detect concurrency?NoNoYes
SizeOne numberOne numberOne counter per actor

Lamport clocks are the right tool when you need a total order consistent with causality — for example, to order commands in a log or to break ties deterministically. They are the wrong tool when you need to know whether two updates conflict.


4. Version Vectors vs Vector Clocks

These two structures look identical — a map from actor ID to counter — and the literature and blog posts often use the names interchangeably. They are not the same thing, and the difference explains most of the design mistakes in this area. Carlos Baquero, one of the authors of the dotted version vector work, has written about exactly this confusion under the title "Version Vectors are not Vector Clocks".

4.1 Vector clocks: ordering events

A vector clock (Fidge and Mattern, 1988) timestamps events in a system of processes:

  • There is one entry per process.
  • A process increments its own entry on every event it wants to track — local steps, sends, receives.
  • On receiving a message, the receiver takes the pointwise maximum with the sender's vector, then increments its own entry.
  • Comparing two vector timestamps tells you whether two events are causally related or concurrent.

The thing being ordered is events, and every process is an actor.

4.2 Version vectors: ordering replica states

A version vector (Parker et al., 1983, introduced for detecting mutual inconsistency in replicated file systems) summarises the update history of one replicated data item at one replica:

  • There is one entry per replica that can accept updates to that item.
  • A replica increments its own entry only when it accepts an update to the item — not on reads, not on unrelated events.
  • When two replicas synchronise the item, the merged state's version vector is the pointwise maximum.
  • Comparing two version vectors tells you whether one replica state includes all the updates of the other, or whether they have diverged.

The thing being ordered is states of a data item, and only updating replicas are actors.

4.3 The differences, side by side

Vector clockVersion vector
OrdersEventsReplica states of a data item
ActorsAll processesReplicas that accept updates to the item
Incremented onEvery tracked event, including sends/receivesUpdates only
Combined howMax-then-increment on message receiptPointwise max on synchronisation (no increment)
ScopeWhole systemUsually per data item
Typical question"Did event a potentially cause event b?""Is replica A's copy of key k newer than, older than, or divergent from replica B's?"
Sync of two equal statesReceipt still increments the receiver's entryMerge produces the same vector, no change

The last row is a practical giveaway. If two replicas with identical copies of a key exchange it in anti-entropy and both counters go up, the system is using vector-clock semantics for something that should be a version vector — and it will soon see differences where none exist.

4.4 Why it matters

Version vectors have a property vector clocks do not need: their size is bounded by the number of replicas, not the number of processes or clients that ever touched the data. And synchronising identical states is a no-op. Both are essential for a database, where data is synchronised constantly and clients number in the millions.

But as soon as you put a version vector inside a client–server store — where clients read from a server, think, and write back — you hit a problem that neither the classic vector clock nor the classic version vector was designed for. That is the subject of the next sections.


5. Conflict Detection with Siblings

5.1 The client–server interaction pattern

In a Dynamo-style store (see Quorums & Leaderless Replication), clients don't hold replicas. The interaction looks like this:

  1. Read: the client asks a replica for key k. The replica returns the current value(s) and an opaque causal context describing what the client has now seen.
  2. Write: the client sends a new value along with the context from its read. The context says "this write supersedes everything I saw".
  3. The replica uses the context to decide which stored versions the new write supersedes, and which it is concurrent with.

Versions that are concurrent are kept side by side as siblings. The next reader gets all siblings plus a context covering all of them, merges them in application logic, and writes back a single value that supersedes them all.

sequenceDiagram
    participant C1 as Client 1
    participant S as Replica A
    participant C2 as Client 2
    C1->>S: get k
    S-->>C1: v0, context ctx0
    C2->>S: get k
    S-->>C2: v0, context ctx0
    C1->>S: put k = v1, context ctx0
    Note over S: v1 supersedes v0
    C2->>S: put k = v2, context ctx0
    Note over S: v2 supersedes v0 but not v1 — keep siblings v1 and v2
    C1->>S: get k
    S-->>C1: siblings v1 and v2, context ctx2
    Note over C1: Merge v1 and v2 into v3
    C1->>S: put k = v3, context ctx2
    Note over S: v3 supersedes v1 and v2 — one value again

5.2 The comparison rules

Given a stored version with causal history H_s and a new write whose context covers history H_c:

RelationshipMeaningAction
H_s ⊆ H_cThe writer had seen the stored versionDiscard the stored version (it is superseded)
H_s ⊄ H_cThe writer had not seen itKeep it as a sibling of the new write

For replica-to-replica synchronisation of two stored versions x and y:

RelationshipMeaningAction
H_x ⊂ H_yy descends from xKeep y
H_y ⊂ H_xx descends from yKeep x
H_x = H_ySame versionKeep one
NeitherConcurrentKeep both as siblings

The question is entirely about how to represent these histories compactly and correctly. Version vectors are the obvious candidate. The trouble starts with deciding whose counters go into the vector.


6. Choosing Actors: Both Obvious Choices Fail

6.1 Option A: one entry per client

Make every client an actor. When client c writes with context ctx, the new version's vector is ctx with c's entry incremented.

This is exactly right for causality: two clients writing from the same context produce {c1:1} and {c2:1}, which are incomparable — correctly detected as concurrent.

The problem is size. Every client that ever writes a key adds an entry to that key's vector, forever. A popular key written by a hundred thousand clients carries a hundred-thousand-entry vector on every read and write. Systems that used client IDs had to prune vectors — drop the oldest entries when the vector grew past a threshold. The Dynamo paper describes truncating the vector clock when it exceeds a size threshold (it mentions 10 entries), dropping the oldest pair by timestamp, and acknowledges that this can lose causal information so that descendants may be mistaken for concurrent versions. Pruning trades correctness for space: a pruned vector may make an older version look concurrent (a spurious sibling), or in the worst case let an older version appear to dominate.

6.2 Option B: one entry per server replica

Make every server replica (or vnode) an actor. Vectors now have at most N entries (one per replica of the key) — bounded and small.

But now two clients writing through the same replica look like the same actor. Consider a single replica A with key k empty:

StepEventStoredProblem
1Client 1 reads: nothing, context {}—
2Client 2 reads: nothing, context {}—
3Client 1 writes v1 with {}. A increments its entryv1 @ {A:1}
4Client 2 writes v2 with {}. A increments its entry?v2's vector would be {A:2}, which dominates v1's {A:1} — but Client 2 never saw v1

At step 4 the replica has two bad options:

  • Tag v2 with {A:2} and discard v1 because {A:2} > {A:1}. That silently loses Client 1's update — the exact problem siblings were supposed to prevent.
  • Notice that the incoming context {} does not cover the stored {A:1}, and keep both v1 and v2 as siblings under a single merged vector {A:2}. No data is lost — but the individual siblings no longer have their own accurate causal histories. The key as a whole is tagged {A:2}.

Riak, when it used per-vnode vector clocks, took the second option. It is safe, but it creates the next problem.


7. The Sibling-Explosion Problem

Continue the per-replica example. Replica A stores siblings {v1, v2} under the single vector {A:2}. Client 1 still has the context {A:1} that came back with its earlier write, and writes again.

StepEventStored siblingsObject vectorWhat should be stored
5Client 1 writes v3 with context {A:1}v1, v2, v3{A:3}v2, v3 (v3 supersedes v1)
6Client 2 writes v4 with context {A:2} (returned with its step-4 write)v1, v2, v3, v4{A:4}v3, v4 (v4 supersedes v2, and v1 is already gone)

Look at step 5 closely. The incoming context is {A:1}. The object's vector is {A:2}. Since {A:1} does not cover {A:2}, the replica knows some stored sibling is concurrent with the new write — but with only one vector for the whole object, it cannot tell which. Was v1 the sibling at A:1 (superseded) and v2 the one at A:2 (concurrent)? The per-sibling information is gone. The only safe move is to keep all existing siblings plus the new one. So v1, which Client 1 explicitly overwrote, survives as a "false" sibling.

Now picture two clients, each in a loop of "write, take the returned context, write again" — a common pattern with session-cached contexts or rapid updates from the same user on two devices:

RoundClient 1 writes with its last contextClient 2 writes with its last contextSiblings after the round (per-vnode vectors)Correct siblings
1v1v222
2v3 (saw v1 only)v4 (saw v2 only)42
3v5v662
k……2k2

Each client's write really supersedes only its own previous write, so the true number of concurrent versions stays at two. But because the stored object has a single vector and every new context is "behind" it, nothing is ever discarded. The sibling count grows linearly with the number of interleaved writes until a reader resolves them — and if readers don't read-merge-write promptly, keys accumulate hundreds or thousands of siblings, bloating objects, slowing reads and eventually hurting the whole node.

This is sibling explosion. It is not a bug in an implementation; it is the information-theoretic consequence of representing the causal histories of several concurrent versions with one version vector whose actors are servers.

7.1 The root cause in one sentence

A version vector can precisely describe a contiguous history per actor — "all of A's events 1 through n". But concurrent writes through the same server replica produce non-contiguous histories: v1 is A's event 1, v2 is A's event 2, and they are concurrent with each other. "Events 1 and 2 of A, but not each other's" cannot be written as a version vector. Something extra is needed to name a single event that is not part of a contiguous prefix.

That something is a dot.


8. Dotted Version Vectors

Dotted version vectors (DVVs) were introduced by Nuno Preguiça, Carlos Baquero, Paulo Sérgio Almeida, Victor Fonte and Ricardo Gonçalves (first described around 2010, with a later formal treatment of the client–server setting). They keep the server-ID actors of option B — so the size stays bounded by the number of replicas — but tag each sibling with its own precise causal history.

8.1 The structure

A dotted version vector is a pair:

  • (r, n) is the dot: the single event that created this version — the n-th update accepted by replica r.
  • V is a version vector — the causal past of the version: everything the writer had seen.

It represents the set of events

i.e. a contiguous prefix per actor (from V) plus one extra, possibly non-contiguous event (the dot). That one extra event is exactly what option B was missing.

8.2 The rules

Coverage. A dot (r, n) is covered by a version vector V iff n ≤ V[r].

Supersession. Version x is in the causal past of version y iff x's dot is in y's history: the dot is covered by y's V, or it equals y's dot.

Read. A replica returns all sibling values plus a context: the version vector that covers every sibling's history — the pointwise max of all siblings' V's and dots.

Write (update) at replica r with context C:

  1. Discard every stored sibling whose dot is covered by C — the writer had seen it.
  2. Create a new dot (r, n) where n is one greater than the largest counter for r that appears anywhere in the stored state or in C.
  3. Store the new value with DVV ((r, n), C) alongside the surviving siblings.

Sync between replicas: take the union of both sibling sets, drop duplicates (same dot), and drop any sibling whose dot is covered by another sibling's history.

8.3 Worked example — the same scenario, fixed

Replay sections 6.2 and 7 on a single replica A, now with DVVs. Notation: (A,2)|{A:1} means dot (A,2) with causal past {A:1}.

StepEventDiscarded (dot covered by context)New DVVSiblings stored after
1Client 1 reads: empty, context {}—
2Client 2 reads: empty, context {}—
3Client 1 writes v1, context {}—v1 (A,1)|{}v1
4Client 2 writes v2, context {}v1? (A,1) covered by {}? No → keepv2 (A,2)|{}v1, v2
5Client 1 writes v3, context {A:1} (from its step-3 response)v1: (A,1) covered by {A:1} → discard. v2: (A,2) covered? No → keepv3 (A,3)|{A:1}v2, v3
6Client 2 writes v4, context {A:2} (from its step-4 response)v2: (A,2) covered by {A:2} → discard. v3: (A,3) covered? No → keepv4 (A,4)|{A:2}v3, v4
7Client 3 readsreturns v3, v4 with context {A:4}
8Client 3 writes merged v5, context {A:4}v3 (A,3) ✓, v4 (A,4) ✓ → discard bothv5 (A,5)|{A:4}v5

At every step the stored siblings are exactly the truly concurrent versions — two at most, never growing — even though the vectors only ever mention replica A. The key is step 4: v1 and v2 are both "events of A", but because each carries its own dot, the replica knows v2's history is {(A,2)}, which does not include (A,1). The two are correctly concurrent, and at step 5 the replica can tell precisely that v3 supersedes v1 but not v2.

Comparing two DVVs directly — say during sync — works the same way. Is v2 (A,2)|{} in the past of v3 (A,3)|{A:1}? Its dot (A,2) is not covered by {A:1} and is not v3's dot, so no. Is v3 in the past of v2? (A,3) not covered by {} — no. They are concurrent, as they should be.

8.4 A multi-replica example

Two replicas A and B hold key k; both start with v0 (A,1)|{}.

StepWhereEventResult
1AClient X reads v0, context {A:1}, writes vxA stores vx (A,2)|{A:1} (v0 discarded)
2BClient Y reads v0, context {A:1}, writes vyB stores vy (B,1)|{A:1} (v0 discarded)
3A ↔ BAnti-entropy syncvx's dot (A,2) not covered by vy's history {A:1, B:1}; vy's dot (B,1) not covered by vx's history {A:2}. Concurrent → both replicas store {vx, vy}
4AClient Z reads: siblings vx, vy, context {A:2, B:1}; writes merged vzBoth dots covered → discarded. vz (A,3)|{A:2, B:1}
5A ↔ BSyncB's vx and vy are covered by vz's history → B keeps only vz

The vector never grows beyond the two replicas, no matter how many clients participate.

8.5 Compact form: DVV sets

Storing a full DVV per sibling is redundant, because siblings at one replica share most of their causal past. The authors also described a compact representation, often called a DVVSet, that stores per key one entry per replica of the form (replica, counter, list of values for that replica's recent dots). The causal past of the whole set is implied by the counters; each value's dot is derived from its position in its replica's list. Riak's DVV support is based on this compact form. The semantics are the same as in the table above.

8.6 Implementation

A self-contained TypeScript implementation of a per-key DVV store, with the worked example from 8.3 as an executable check:

import assert from "node:assert/strict";

export type VV = Record<string, number>;
export type Dot = { r: string; n: number };
export type Sibling<T> = { dot: Dot; past: VV; value: T };

const covers = (vv: VV, d: Dot) => (vv[d.r] ?? 0) >= d.n;

function join(a: VV, b: VV): VV {
  const out: VV = { ...a };
  for (const [r, n] of Object.entries(b)) out[r] = Math.max(out[r] ?? 0, n);
  return out;
}

/** The smallest version vector covering a sibling's full history (past + dot). */
const historyOf = <T>(s: Sibling<T>): VV => join(s.past, { [s.dot.r]: s.dot.n });

/** x is in y's causal past iff x's dot is covered by y's history. */
export const descends = <T>(y: Sibling<T>, x: Sibling<T>) =>
  covers(y.past, x.dot) || (y.dot.r === x.dot.r && y.dot.n === x.dot.n);

export class DvvKey<T> {
  siblings: Sibling<T>[] = [];
  constructor(readonly replica: string) {}

  read(): { values: T[]; context: VV } {
    const context = this.siblings.reduce<VV>((acc, s) => join(acc, historyOf(s)), {});
    return { values: this.siblings.map((s) => s.value), context };
  }

  write(value: T, context: VV): Dot {
    // Largest counter for this replica seen anywhere — computed BEFORE discarding,
    // so a new dot can never reuse a counter.
    let max = context[this.replica] ?? 0;
    for (const s of this.siblings) max = Math.max(max, historyOf(s)[this.replica] ?? 0);

    this.siblings = this.siblings.filter((s) => !covers(context, s.dot)); // writer saw these
    const dot = { r: this.replica, n: max + 1 };
    this.siblings.push({ dot, past: { ...context }, value });
    return dot;
  }

  /** Anti-entropy: merge another replica's siblings for the same key. */
  sync(remote: Sibling<T>[]): void {
    const all = [...this.siblings, ...remote];
    const unique = all.filter((s, i) => all.findIndex((t) => t.dot.r === s.dot.r && t.dot.n === s.dot.n) === i);
    this.siblings = unique.filter((s) => !unique.some((t) => t !== s && descends(t, s) && !descends(s, t)));
  }
}

// Executable worked example (section 8.3): siblings never exceed the truly concurrent set.
if (process.argv[1]?.endsWith("dvv.ts") || process.env.DVV_SELFTEST) {
  const k = new DvvKey<string>("A");
  k.write("v1", {});                                          // client 1, read nothing
  k.write("v2", {});                                          // client 2, read nothing
  assert.deepEqual(k.read().values, ["v1", "v2"]);            // correctly concurrent
  k.write("v3", { A: 1 });                                    // client 1 saw only v1
  assert.deepEqual(k.read().values, ["v2", "v3"]);            // v1 superseded, v2 kept
  k.write("v4", { A: 2 });                                    // client 2 saw only v2
  assert.deepEqual(k.read().values, ["v3", "v4"]);
  const { context } = k.read();
  assert.deepEqual(context, { A: 4 });
  k.write("v5", context);                                     // client 3 merges
  assert.deepEqual(k.read().values, ["v5"]);

  // Multi-replica example (section 8.4)
  const a = new DvvKey<string>("A"), b = new DvvKey<string>("B");
  a.write("v0", {}); b.sync(a.siblings);
  a.write("vx", { A: 1 }); b.write("vy", { A: 1 });
  a.sync(b.siblings); b.sync(a.siblings);
  assert.deepEqual(a.read().values.sort(), ["vx", "vy"]);
  a.write("vz", a.read().context); b.sync(a.siblings);
  assert.deepEqual(b.read().values, ["vz"]);
  console.log("dvv ok");
}

The interesting line is the max computation: the new dot must be strictly greater than any counter for this replica that appears anywhere — in the stored siblings' histories or in the client's context. Reusing a counter would make two different versions share a dot, and the store would treat them as the same event.

8.7 What DVVs do and do not solve

ProblemSolved by DVVs?
Vector size grows with number of clientsYes — actors are replicas only
Concurrent writes through the same replica mistaken for ordered (lost update)Yes — each gets its own dot
False siblings / sibling explosion from stale contextsYes — each sibling's history is exact
Blind writes (no read, empty context) create siblingsNo — and they should: a blind write genuinely didn't see anything
Applications that never merge siblingsNo — the true concurrent set still has to be resolved by someone
Vector growth from replica churn (many replicas over time)No — retired replica IDs must still be garbage-collected
Merging sibling valuesNo — that is application logic or a CRDT

9. Interval Tree Clocks (Briefly)

DVVs bound vector size by the number of replicas — assuming replicas have stable, globally unique IDs. Some systems have dynamic participants that appear and disappear constantly: mobile devices, short-lived processes, peer-to-peer nodes. Allocating permanent IDs to all of them and carrying an entry per participant is wasteful, and retiring IDs safely requires coordination.

Interval tree clocks (ITC), by Paulo Sérgio Almeida, Carlos Baquero and Victor Fonte (2008), remove global IDs entirely. Each participant owns a portion of the interval [0, 1) instead of an ID, and its clock is a tree describing event counts over sub-intervals. Three operations replace the usual increment and merge:

OperationWhat it does
forkSplit a participant's ID interval in two, giving one half to a new participant — no coordination with anyone else
eventIncrement the event tree over (part of) the participant's own interval
joinMerge two clocks: sum the ID intervals, take the pointwise max of event trees, and simplify

Because a retiring participant can join its interval back into another's, the ID space is reclaimed automatically, and trees normalise to a compact form as participants come and go. The cost is more complex encoding and operations than a simple map of counters. ITCs are worth knowing for systems with high churn; for a database with a fixed set of replicas, DVVs are simpler and sufficient. The Vector Clocks & Lamport Timestamps page shows the tree structure in more detail.


10. How Dynamo-Style Stores Use Them

10.1 Amazon Dynamo (2007 paper)

The Dynamo paper describes vector clocks attached to each object version, with entries of the form (node, counter), where the node is the server that coordinated the write. Divergent versions are returned to the client on read; the client reconciles and writes back with the merged context. To bound size, the clock is truncated when it exceeds a threshold, removing the oldest entry by a stored wall-clock timestamp. The authors note this has not been a significant problem in their production experience but acknowledge it can lose lineage information.

Note that the paper's clock is, by the definitions in section 4, closer to a version vector with server actors — and so subject to the concurrent-writes-through-one-coordinator issue of section 6.2.

10.2 Riak

Riak's history is a tour through every design on this page. Based on Basho's documentation and the DVV papers:

EraActorsBehaviour
Early RiakClient IDs (clients could supply their own)Accurate concurrency detection, but vectors grew with the number of clients; Riak exposed pruning settings (small_vclock, big_vclock, young_vclock, old_vclock) to bound them
Riak 1.0 onwardsVnode IDs ("vnode vclocks")Bounded size, but concurrent writes coordinated by the same vnode had to be kept as siblings without per-sibling histories → the sibling-explosion behaviour of section 7
Riak 2.0 onwardsDotted version vectors (enabled per bucket type with dvv_enabled; on by default for new bucket types in 2.0)Bounded size and exact sibling sets

Riak exposes the causal context to HTTP clients as an opaque header (X-Riak-Vclock) returned on reads and sent back on writes. Its guidance to application developers follows directly from the mechanics:

  • Always read before you write, and send back the context you got. A write with no context is a blind write and will create a sibling.
  • Resolve siblings on read and write back the merged value promptly.
  • Use allow_mult = true if concurrent updates matter; last_write_wins = true discards concurrency (and the causal context) entirely.
  • Or use Riak data types (counters, sets, maps, flags, registers), which are CRDTs: the store merges concurrent updates itself, so the application never sees siblings. See CRDTs.

10.3 Others

  • Voldemort (LinkedIn's Dynamo-inspired store) used vector clocks for versioning, with client-side resolution.
  • Cassandra does not track causality per value. It uses per-cell last-write-wins timestamps, so concurrent updates to the same cell are resolved by timestamp and the loser is discarded. That is a deliberate trade: no siblings, no client merge logic, but concurrent updates can be lost (see Quorums & Leaderless Replication on LWW and clock skew).
  • CRDT-based systems often use dots directly: an observed-remove set tags each added element with a dot, and a remove deletes the specific dots it observed. The same "single event plus causal context" idea underpins delta-state CRDTs and causal-length designs.
SystemCausality metadataConcurrent writesWho merges
Dynamo (paper)Vector clock, coordinator-node actors, truncatedSiblingsApplication
Riak ≥ 2.0 (default bucket types)Dotted version vectorsExact siblingsApplication, or CRDT data types
VoldemortVector clocksSiblingsApplication
CassandraPer-cell timestampHighest timestamp winsNobody — loser discarded
DynamoDB global tablesTimestampsLast writer wins across regionsNobody

11. Causal Consistency and Causal Broadcast

So far we have used causality to detect conflicts between versions of one key. The same machinery gives a consistency model across many keys.

11.1 Causal consistency

A store is causally consistent if every client observes writes in an order consistent with happens-before: if write w1 causally precedes write w2, no client may see w2 and then fail to see w1. Concurrent writes may be observed in different orders by different clients. The Consistency Models page places causal consistency in the hierarchy; the key facts are:

  • It is stronger than eventual consistency and the session guarantees (it implies read-your-writes, monotonic reads, monotonic writes and writes-follow-reads).
  • It is weaker than sequential consistency and linearizability — and therefore achievable without coordination, under partitions. Mahajan, Alvisi and Dahlin (2011) showed that a variant called real-time causal consistency is, in a precise sense, the strongest model achievable by an always-available, convergent system.

The classic anomaly it prevents:

sequenceDiagram
    participant Alice
    participant R1 as Replica 1
    participant R2 as Replica 2
    participant Bob
    Alice->>R1: w1 — remove Bob from album ACL
    Alice->>R1: w2 — upload private photo to album
    R1-->>R2: replicate w2 (arrives first)
    Bob->>R2: read album
    R2-->>Bob: sees the private photo, ACL still includes Bob
    R1-->>R2: replicate w1 (arrives late)
    Note over Alice,Bob: w1 happened before w2, but R2 exposed w2 without w1 — violates causal consistency

A causally consistent store would not make w2 visible at Replica 2 until w1 was visible there too.

11.2 Implementing it: dependency tracking

Causally consistent stores attach dependencies to each write and delay making it visible until its dependencies are visible:

  • COPS (Lloyd et al., SOSP 2011) tracks, for each write, the versions of the keys the client had read or written before it, and a remote datacenter only exposes the write after checking those dependencies are committed locally. It also introduced causal+ consistency: causal consistency plus convergence of concurrent writes (via a deterministic conflict handler).
  • MongoDB (since 3.6) offers causally consistent client sessions: each operation returns an operationTime and the session passes afterClusterTime on later reads, so a secondary will wait until it has replicated at least that far before answering. This gives read-your-writes, monotonic reads, monotonic writes and writes-follow-reads within a session (with appropriate read and write concerns).
  • Many systems approximate causal consistency with client-carried tokens: a version vector or a hybrid logical clock timestamp the client sends with each request, which a replica must have caught up to before serving it.

11.3 Causal broadcast

Causal broadcast is the messaging primitive underneath: if the broadcast of m1 happens-before the broadcast of m2, every process delivers m1 before m2. Concurrent messages may be delivered in any order.

The standard vector-clock implementation (from Birman, Schiper and Stephenson's work on ISIS, among others) works like this. Each process i keeps a vector D where D[j] counts messages from j it has delivered.

  • Broadcast: increment D[i], attach a copy of D to the message.
  • Deliver a message from j with vector M only when:
    • M[j] = D[j] + 1 (it is the next message from j), and
    • M[k] ≤ D[k] for every k ≠ j (everything the sender had delivered before sending, we have delivered too).
  • Otherwise buffer it; after each delivery, re-check the buffer.
sequenceDiagram
    participant P1 as P1
    participant P2 as P2
    participant P3 as P3
    Note over P1: broadcast m1, vector [1,0,0]
    P1->>P2: m1 [1,0,0]
    P1-->>P3: m1 [1,0,0] (slow)
    Note over P2: deliver m1, D = [1,0,0]
    Note over P2: broadcast m2 as a reply, vector [1,1,0]
    P2->>P3: m2 [1,1,0]
    Note over P3: D = [0,0,0]. m2 needs P1 entry at most 0 but has 1 — buffer m2
    P1-->>P3: m1 [1,0,0] arrives
    Note over P3: deliver m1, D = [1,0,0]
    Note over P3: buffer check — m2 now deliverable, deliver m2, D = [1,1,0]

P3 receives the reply before the original, but delivers them in causal order. The cost is a vector per message and buffering — and if a process crashes after some processes received its message and others didn't, messages that depend on it may wait forever unless the broadcast layer also re-forwards messages (reliable causal broadcast). The Vector Clocks & Lamport Timestamps page includes a TypeScript implementation of the delivery rule.

Causal broadcast is how many CRDT systems deliver operations ("op-based" CRDTs require causal delivery), and how group-communication toolkits historically provided causally ordered messaging.

11.4 The spectrum of causality tracking

NeedMechanismMetadata size
Total order consistent with causalityLamport clock, HLCOne counter / timestamp
Detect conflicts between versions of one keyVersion vector (server actors) + dotsO(replicas) per key
Exact siblings in a client–server storeDotted version vectorsO(replicas) per key
Dynamic participants without global IDsInterval tree clocksVaries with fork/join history
Causal order of messagesVector-clock causal broadcastO(processes) per message
Causal consistency across keys and datacentersDependency tracking (COPS), session tokens (MongoDB)Dependencies per write, or one token per session

12. Practical Guidance

12.1 Do's and don'ts

  • Do read before writing, and pass back the context. Blind writes always produce siblings.
  • Do merge siblings with domain knowledge, or use CRDTs so that the store merges for you.
  • Do monitor sibling counts per key (Riak exposes sibling statistics) — a steadily rising count means clients aren't resolving.
  • Don't use client IDs as vector actors in a store with many clients.
  • Don't use plain server-ID version vectors to version individual siblings — use dots.
  • Don't assume a timestamp ordering says anything about conflicts.
  • Don't forget deletes: a delete is a write with a causal context; a tombstone must carry it, or a concurrent update can make the deleted value reappear (or a late-arriving old value can undo the delete).

12.2 Choosing a conflict strategy

flowchart TD
    Q1{"Can concurrent updates<br/>to one key happen?"} -->|"No — single writer or immutable"| LWW["Timestamps or LWW are fine"]
    Q1 -->|"Yes"| Q2{"Is losing one of them<br/>acceptable?"}
    Q2 -->|"Yes"| LWW2["LWW, knowingly"]
    Q2 -->|"No"| Q3{"Is there a natural<br/>merge for the data type?"}
    Q3 -->|"Yes — counter, set, map"| CRDT["CRDT data type"]
    Q3 -->|"No — needs domain logic"| DVV["Siblings tracked with<br/>dotted version vectors"]
    Q2 -->|"No, and must reject the conflict"| CONS["Consensus / CAS instead<br/>of optimistic replication"]

13. War Stories

War Story (illustrative) — the profile with nine thousand siblings

A social app stored user profiles in a Dynamo-style store with per-server version vectors and siblings enabled. The mobile client cached the causal context from its last write and reused it for subsequent writes instead of re-reading — an optimisation to save a round trip. Most users had one device, so nothing went wrong. A handful of power users had a phone, a tablet and a browser session all open, each periodically saving a "last seen" field. Every save arrived with a stale context; every save added a sibling and none were ever discarded. One account's profile grew past nine thousand siblings and several megabytes. Reads of that key started timing out, and the replica holding it spent so much time serialising the object that it fell behind on everything else. The fix had three parts: re-read before write in the client, move "last seen" into a separate key with LWW semantics (losing an update to it is harmless), and enable dotted version vectors so that stale-context writes no longer created false siblings.

War Story (illustrative) — LWW and the vanishing comment

A team migrated a comment-threading feature from a store with sibling support to one with per-cell last-write-wins, reasoning that "conflicts are rare". The thread's replies were stored as a list in a single cell. Two users replying within the same second to a popular thread, through different coordinators, produced two concurrent updates to that cell — and LWW kept only one. The other reply vanished without an error. The fix was not a better clock but a better data model: one row per reply (so concurrent replies are different cells and never conflict), which is the standard way to design out conflicts in an LWW store.


14. Summary

  • Causality is a partial order. Timestamps impose an arbitrary total order on it; only causality-tracking structures can tell "newer" from "concurrent".
  • Lamport clocks respect causality but cannot detect concurrency.
  • Vector clocks order events among processes; version vectors order replica states of a data item among updating replicas. They look alike but answer different questions and evolve differently.
  • In a client–server store, client-ID actors make vectors grow unboundedly; server-ID actors make concurrent writes through one server indistinguishable, leading to lost updates or sibling explosion.
  • Dotted version vectors add a single dot per version — the event that created it — so each sibling has an exact history while vectors stay bounded by the number of replicas.
  • Interval tree clocks handle dynamic participants without global IDs.
  • The same ideas extend to causal consistency across keys (dependency tracking, session tokens) and to causal broadcast of messages.

Interview Questions

1. What is the difference between a total order and a partial order? Why is causality a partial order?

A partial order is irreflexive and transitive but may leave pairs incomparable; a total order compares every pair. Causality (happens-before) relates two events only when a chain of local steps and messages connects them. Events with no such chain are concurrent — incomparable — so causality is partial. Any total order consistent with it (Lamport order, timestamp order) is just one of many linear extensions.

2. What can't Lamport timestamps tell you, and why does that matter for a database?

L(a) < L(b) does not imply a → b; Lamport timestamps can't distinguish "a happened before b" from "a and b are concurrent". A database that discards the lower-timestamped of two writes (LWW) may therefore discard a concurrent write the other writer never saw — silent data loss. Detecting concurrency needs vector-style metadata.

3. Explain the difference between vector clocks and version vectors.

Vector clocks timestamp events among processes: one entry per process, incremented on every tracked event, combined by max-then-increment on message receipt; they answer "did event a potentially cause event b?". Version vectors describe the update history of a data item at a replica: one entry per updating replica, incremented only on updates, merged by pointwise max on sync with no increment; they answer "is this replica's copy newer, older, or divergent?". Version vectors stay bounded by the number of replicas and syncing equal states is a no-op.

4. In a client–server key-value store, why do client-ID actors and server-ID actors both cause problems?

Client IDs give accurate concurrency detection but vectors grow with every client that writes a key, requiring pruning that loses causal information. Server IDs bound vector size, but two clients writing concurrently through the same server look like successive events of one actor — so the server either loses one update (newer counter dominates) or must keep siblings without per-sibling histories, leading to false siblings and sibling explosion.

5. Walk through how sibling explosion happens.

With server-ID version vectors and one vector per object, a write arriving with a context older than the object's vector cannot be matched to specific siblings, so the server keeps all existing siblings plus the new one. Two clients repeatedly writing with their own last contexts each supersede only their own previous write, but nothing is ever discarded: siblings grow by two per round while the true concurrent set stays at two.

6. What is a dotted version vector and how does it fix sibling explosion?

A DVV is ((r, n), V): a dot naming the single event that created the version (the n-th update at replica r), plus a version vector V of its causal past. Its history is V's contiguous prefixes plus that one dot, which can express non-contiguous histories like "A's event 2 but not A's event 1". On a write with context C, the server discards siblings whose dots are covered by C and tags the new value with a fresh dot and past C. Each sibling has an exact history, so only truly concurrent versions remain, while vectors stay bounded by the number of replicas.

7. Given siblings (A,1)|{} and (A,2)|{}, a client writes with context {A:1}. What is stored afterwards?

(A,1) is covered by {A:1}, so it is discarded. (A,2) is not covered (2 > 1), so it stays. The new write gets dot (A,3) with past {A:1}. Stored: (A,2)|{} and (A,3)|{A:1} — two concurrent siblings.

8. When would you use interval tree clocks instead of version vectors?

When participants are dynamic — created and retired frequently (mobile devices, ephemeral processes) — so assigning and garbage-collecting unique IDs is costly. ITCs give each participant a share of the [0,1) interval via fork, and join reclaims it, so no global ID allocation is needed and the clock adapts in size to the current participants. For a database with a fixed set of replicas, DVVs are simpler.

9. How did Riak's approach to causality evolve, and why?

Early Riak used client-ID vector clocks (accurate but growing with the number of clients, bounded by pruning settings). Riak 1.0 switched to vnode-ID clocks (bounded size but sibling explosion for concurrent writes via the same vnode). Riak 2.0 introduced dotted version vectors, enabled by default for new bucket types, which keep bounded size with exact sibling sets. It also added CRDT data types so the store can merge concurrent updates itself.

10. What is causal consistency and why is it attractive for geo-replicated systems?

Every client observes causally related writes in causal order; concurrent writes may appear in different orders. It implies all four session guarantees, prevents anomalies like seeing a private photo before the ACL change that preceded it, and — unlike linearizability or sequential consistency — can be provided while remaining available under partitions. Implementations track dependencies (COPS) or use session tokens (MongoDB causally consistent sessions with afterClusterTime).

11. Describe the delivery condition for vector-clock-based causal broadcast.

Process i delivers a message from j with vector M only if M[j] = D[j] + 1 (it's the next message from j) and M[k] ≤ D[k] for all k ≠ j (i has already delivered everything j had delivered before sending). Otherwise buffer it and re-check after each delivery. On delivery, set D[j] = M[j].

12. A client writes to a Riak bucket without reading first. What happens, and why is it the correct behaviour?

The write carries an empty causal context, so it covers none of the existing versions; the server keeps them all and adds the new value as a sibling. That's correct: the client genuinely hadn't seen the existing versions, so the store can't know whether the new value should replace them. The fix is to read first (or use a CRDT data type, or last-write-wins if losing concurrent updates is acceptable).