Vector clock architecture, in depth: causal delivery, consistent cuts and debugging distributed traces

The clock in two sentences

Each process i keeps a vector V with one counter per process; it increments V[i] on every event it cares about, attaches a copy of V to every message it sends, and on receipt takes the element-wise maximum with the incoming vector. Event x happened before event y exactly when V(x) is less than or equal to V(y) in every entry and strictly less in at least one; if each vector is larger somewhere, the events are concurrent.

Everything below relies on that if-and-only-if. A Lamport clock, or a hybrid logical clock, can order events consistently with causality but cannot detect concurrency. When the question is "could these two things have influenced each other?", only a vector answers it.

The architecture: a clock layer, a hold-back queue and a log

In a real system the clock is not scattered through business code. It sits in a thin layer between the application and the transport, the same place you would put tracing or authentication. It has three jobs: on send, increment the local entry and attach the vector as a header; on receive, decide when a message may reach the application, which is where the hold-back queue lives; and on every event, write a log line carrying the vector for later offline analysis.

Because the application never touches counters, it cannot forget to merge, and the header format is defined once for every hop.

Causal broadcast: never show an effect before its cause

In a replicated group chat, Alice posts "Is the deploy done?", Bob replies "Yes", and Carol's network delivers the reply first: Carol sees an answer to nothing. Causal broadcast is the guarantee that if the broadcast of m1 happened before the broadcast of m2, every process delivers m1 before m2. Concurrent messages may still be delivered in different orders at different processes; enforcing one order for them is the stronger and costlier total order broadcast.

The classic implementation, due to Birman, Schiper and Stephenson, uses a vector in which entry k counts the broadcasts from process k that this process has delivered. The sender increments its own entry and stamps the message. A receiver i accepts a message m from j for delivery only when two conditions hold: VT_m[j] equals VT_i[j] + 1, so m is the very next message from j, and VT_m[k] is at most VT_i[k] for every other k, so i has already delivered everything j had delivered when it sent m. A message that fails the test waits in the hold-back queue. When it is delivered, only entry j needs updating, and the receiver does not increment its own entry, because receiving is not a broadcast.

class CausalBroadcast:
    '''Birman-Schiper-Stephenson causal delivery for a fixed group of n processes.

    vt[k] counts broadcasts FROM process k that this process has delivered.
    '''

    def __init__(self, me, n, transport, deliver):
        self.me, self.n = me, n
        self.vt = [0] * n
        self.pending = []            # hold-back queue of (sender, vector, payload)
        self.transport, self.deliver_fn = transport, deliver

    def broadcast(self, payload):
        self.vt[self.me] += 1        # a send is an event of mine
        stamp = list(self.vt)
        self.deliver_fn(self.me, payload)   # deliver to myself at once
        self.transport.send_all(self.me, stamp, payload)

    def deliverable(self, j, vm):
        if vm[j] != self.vt[j] + 1:  # must be the next broadcast from j
            return False
        return all(vm[k] <= self.vt[k] for k in range(self.n) if k != j)

    def on_receive(self, j, vm, payload):
        self.pending.append((j, vm, payload))
        progress = True
        while progress:              # one delivery may unblock others
            progress = False
            for item in list(self.pending):
                j, vm, payload = item
                if self.deliverable(j, vm):
                    self.pending.remove(item)
                    self.vt[j] = vm[j]   # merge: only entry j can have grown
                    self.deliver_fn(j, payload)
                    progress = True

Delivery can cascade, which is why the loop repeats until nothing changes. And the algorithm assumes reliable delivery underneath. If a message is lost for good, every later message from its sender, and everything causally after them, waits forever. Causal broadcast therefore sits on top of retransmission, not instead of it.

Worked example: the reply that arrived first

Three processes, Alice (0), Bob (1) and Carol (2), all start at [0,0,0]. Alice broadcasts the question m1 stamped [1,0,0] and delivers it to herself. Bob receives m1: the stamp's Alice entry is 1, which is Bob's 0 plus 1, and the other entries are not ahead, so he delivers it and sets his vector to [1,0,0]. Bob broadcasts his reply m2: he increments his own entry and stamps [1,1,0].

Carol, still at [0,0,0], receives m2 first. The Bob entry passes the test (1 equals 0 plus 1), but the Alice entry fails: the stamp says 1 and Carol has delivered 0 of Alice's messages. m2 goes into the hold-back queue. Then m1 arrives with [1,0,0]; it passes, Carol delivers it and her vector becomes [1,0,0]. The loop re-examines the queue, m2 now passes, Carol delivers it and reaches [1,1,0]. The user interface shows the question, then the answer, even though the network did the opposite.

Had Carol independently broadcast m3 = [0,0,1], members could place it before or after the question, because m3 and m1 are concurrent. If everyone must see the same interleaving, you need total order.

Consistent cuts: global states that could actually have existed

A cut picks, for every process, a point in its history. It is consistent if, whenever a receive is in, the matching send is in too. An inconsistent cut shows money that arrived in account B before it left account A, so any invariant checked against it (total balance, no two leaders) can report a violation that never happened.

With vector-stamped logs the test is mechanical. Let cut[i] be the vector of the last included event of process i. The cut is consistent exactly when, for every pair i and j, cut[j][i] is at most cut[i][i]: nobody in the cut knows of more events of process i than the cut includes for i. From the same rule you can compute the latest consistent cut from the tail of each log by pulling back any process that has seen too far.

def is_consistent(cut):
    '''cut[i] is the vector of the last event of process i included in the cut.

    Consistent iff no process is known (by anyone in the cut) to have
    done more than the cut includes for it.
    '''
    n = len(cut)
    return all(cut[j][i] <= cut[i][i] for i in range(n) for j in range(n))


def latest_consistent_cut(logs):
    '''logs[i] is process i's list of event vectors in order.

    Walk every process back until the frontier is consistent.
    '''
    idx = [len(l) - 1 for l in logs]      # -1 means "no events included"

    def own(i):
        return logs[i][idx[i]][i] if idx[i] >= 0 else 0

    changed = True
    while changed:
        changed = False
        for i in range(len(logs)):
            for j in range(len(logs)):
                # j has seen more of i than i's frontier includes: pull j back
                while idx[j] >= 0 and logs[j][idx[j]][i] > own(i):
                    idx[j] -= 1
                    changed = True
    return idx

This is offline analysis: no coordination at run time, just logs. It differs from the Chandy-Lamport snapshot algorithm, which records a consistent global state online by flooding marker messages along FIFO channels and uses no vector clocks at all. Use markers when you need a checkpoint while the system runs; use vector-stamped logs when you want to ask questions about what happened.

Worked example: two processes, A and B. A's log ends with events [3,0] and a send [4,0]. B's log ends with an event [0,2] and a receive of that send, [4,3]. Taking both tails gives cut[B][A] = 4, which is not more than cut[A][A] = 4, so the cut is consistent. Had A's log been truncated at [3,0], B's tail would claim knowledge of A's fourth event, the test would fail, and the algorithm would pull B back to [0,2].

Debugging with vector-stamped logs

The most common production payoff is diagnosis. Two services both believe they own a shard. With wall-clock timestamps you argue about skew; with vectors you ask the exact question: was service A's "acquired" event before service B's "acquired", or were they concurrent? If they were concurrent, no amount of retrying fixes it; the protocol allowed both. Research tools such as ShiViz draw these logs as space-time diagrams, but the core analysis is small enough to write yourself.

def concurrent(a, b):
    le = all(x <= y for x, y in zip(a, b))
    ge = all(x >= y for x, y in zip(a, b))
    return not le and not ge

def find_races(events):
    # events: dicts with 'proc', 'vc', 'op', 'resource'
    writes = [e for e in events if e["op"] == "write"]
    for i, a in enumerate(writes):
        for b in writes[i + 1:]:
            if a["resource"] == b["resource"] and concurrent(a["vc"], b["vc"]):
                yield a, b

Pairwise comparison is quadratic, so run it over a window around the incident, grouped by resource.

Engineering the clock: identities, restarts and size

Process identity. Entries are keyed by process, so a process that restarts and reuses its identifier while starting its counter from zero will issue vectors that look older than messages it already sent. Either persist the counter before sending, or give every incarnation a fresh identifier such as host plus boot id. Fresh identifiers are simpler but grow the vector with every restart, so retire entries of dead incarnations once every live process has seen their final value.

Size. A dense vector for n processes costs n integers on every message and log line. At 50 processes and 8-byte counters that is 400 bytes of header, often larger than the payload. A sparse map that omits zero entries helps when most processes never talk to each other. The Singhal-Kshemkalyani technique sends only the entries that changed since the last message to the same destination, which requires FIFO channels and per-destination bookkeeping. Beyond a few hundred processes, reconsider: causality among thousands of clients is usually tracked per object with version vectors over replicas, not per client.

Propagation through intermediaries. The header must survive every hop: message queues, HTTP gateways, database rows that another service reads. A consumer that reads a value from a table the producer wrote has received a message, even if no socket connects them. If the vector is not stored with the row, that causal edge is invisible, and your analysis will report concurrency where there was a dependency.

Failure modes

• Hold-back queue grows without bound. One message was lost or one sender stalled mid-stream. Alert on queue age, not only length, and make sure the transport retransmits.
• False concurrency. A causal path went through a hop that dropped the header (a cache, a batch file, a human copying an ID). The events look independent. Carry the vector wherever data carries meaning.
• Vectors that go backwards. A process restarted without its counter. Detect it by checking that each process's own entry strictly increases in its log, and fix it with incarnation ids.
• Unbounded membership. Short-lived workers each add an entry. Cap the set of stamping identities, or stamp at the service level rather than the pod level.
• Wrong question. A vector says nothing about real time; concurrent events may be an hour apart. Pair it with a physical or hybrid timestamp when duration matters.

Trade-offs at a glance

For data stores, causal consistency tracks dependencies for you, and CRDTs make concurrency harmless for mergeable types.

What to do next

1. Write down the question you need answered: delivery order, a consistent snapshot, or post-incident diagnosis. Each needs a different amount of machinery.
2. Add a clock layer at the transport boundary, not in business code, and define one header format for it.
3. Log the vector with every significant event, including reads of shared state, and store it alongside rows other services consume.
4. Use incarnation ids or persisted counters so restarts cannot reuse old entries, and add a check that each process's own entry only increases.
5. If you implement causal broadcast, put it on a retransmitting transport and alert on the age of the oldest held-back message.
6. Run the race finder over the logs of your last distributed incident and compare its answer with the conclusion the team reached.