Interval Tree Clocks and Membership Change

A vector clock indexes its entries by process identity. The identity of a process is assumed to be stable for the lifetime of the execution, and the vector is assumed to have a slot for every process that exists. Both assumptions fail in a system where processes are created, destroyed, and restarted, and where a client can spawn workers without a global registry. Interval tree clocks replace the fixed slot with a position in a tree, so that a new participant can be given a disjoint interval of the existing space rather than a new slot in a growing array.

Why renumbering breaks the vector

Suppose a vector clock has entries for processes A, B, C. Process D joins and process B leaves. The vector now needs entries for A, C, D, and the entries previously written by B are either dropped or must be reinterpreted. Dropping them loses the knowledge that B’s events are in the causal past of the surviving replicas; reinterpreting them requires a mapping from old index to new index, which every participant must agree on, which is a coordination problem in itself.

The deeper problem is that the vector’s meaning is a function of the index assignment. A timestamp produced before a renumbering is not comparable with one produced after, unless the entire history is re-encoded. Systems that avoid the issue do so by fixing the replica set, which is exactly what dynamic membership forbids. The fixed-slot construction itself is described in Vector Clocks and the Detection of Concurrency, and the constraint it imposes on membership is the one this article is about.

An alternative is to keep identifiers stable and tolerate gaps, so the vector grows forever and never shrinks. That works for correctness and fails for size: a system that has seen ten thousand short-lived workers carries ten thousand entries, and every message carries the whole vector.

The identifier as a tree node

Interval tree clocks take a different route. The identifier of a process is a node in a binary tree, and the set of nodes forms a partition of the unit interval [0,1). A node at depth d owns an interval of length 2^-d; the root owns the whole interval, and its two children split it in half. The clock’s timestamp is a pair: an event component (a vector-like map from nodes to counters) and an identity component (the tree of intervals currently assigned).

The fork operation creates a new identity from an existing one. A process holding node n with interval [l, r) can split it into a left child [l, (l+r)/2) and a right child [(l+r)/2, r), keeping one and transferring the other to the new process. The two resulting identifiers are disjoint, so events stamped under them are always concurrent unless a message connects them. No other process needs to learn about the split, and no existing timestamp changes meaning.

The join operation does the reverse: two sibling identities can be merged back into the parent when their event components do not overlap, meaning no leaf of the tree is non-zero on both sides. The condition is what makes the merge sound; if both sides carry a counter for the same region, they have observed different events there, and merging them into one counter would lose the distinction between two concurrent histories.

Comparing under a tree

Comparison generalizes the componentwise test. A timestamp (E, I) has an event map E that assigns a counter to each leaf of the identity tree I. To decide whether timestamp a precedes timestamp b, the algorithm walks the two trees together:

• For each interval in a’s tree, find the corresponding region in b’s tree. A region of b may be split where a is not, so one a node can map to several b nodes.
• Compare the counter values for each mapped region, using the a node’s value against the sum of the b values over the region, since b may have split its counters across children.
• If every region’s a value is less than or equal to the corresponding b value, with strict inequality somewhere, then a → b. If the relation holds in neither direction, the two are concurrent.

The sum over a region is the key detail. The two identity trees partition the same interval at different granularities, so one side’s node can cover several of the other’s leaves. The comparison therefore has to combine the values over the covered region before it means anything, and its cost is proportional to the number of nodes in the two trees rather than to a fixed vector length.

# Sketch of the aggregate step: compare a leaf of a with the region of b
# that covers it. b's region may be a subtree, so sum its leaves.
def region_sum(b_node, lo, hi):
    if b_node.interval == (lo, hi):
        return b_node.counter
    if b_node.is_leaf:
        return 0                      # no overlap with this leaf
    mid = (b_node.interval[0] + b_node.interval[1]) / 2
    total = 0
    if lo < mid:
        total += region_sum(b_node.left, lo, min(hi, mid))
    if hi > mid:
        total += region_sum(b_node.right, max(lo, mid), hi)
    return total

What the tree costs and saves

The saving is that membership change is local. A fork touches one node and produces one new identity; no global renumbering, no growth of a fixed-length vector, and no need for a registry of participants. A process that leaves simply stops forking and stops appearing in new timestamps. If its interval is never joined back, it remains as a hole in the identity tree, which costs some space but preserves the meaning of every timestamp that referenced it.

The cost is in the comparison. A vector clock comparison is O(n) in the number of processes; an interval tree clock comparison is proportional to the number of nodes in the two trees, which grows with the number of forks and joins, not with the number of currently live processes. In a system with heavy churn the trees accumulate depth, and that depth bounds the cost of the recursive comparison. The only way to keep the depth down is to join intervals back when the histories allow it, which is why the join rule’s narrowness matters: a deployment that forks faster than it joins grows trees without bound.

The event map also has to be maintained. Every local event increments the counter at the process’s own node, and every received message merges the sender’s map into the receiver’s. The merge is a componentwise maximum over the union of the two trees’ leaves, which requires the trees to be intersected. The intersection of two interval trees can produce a tree with as many leaves as the sum of the inputs, so a merge is more expensive than a vector merge and can be repeated on every message.

When a join is legal

The join rule is narrower than the fork rule. Two sibling identities can be merged only if neither side’s event component carries a counter for any identity belonging to the other side, which is the condition for the two histories never having communicated. Once a message has passed between them, each side’s event map records the other’s identity, and the merge is refused.

The refusal is the right behaviour rather than a limitation. A pair that has exchanged messages is causally ordered, and collapsing their identities would erase the distinction between “these events happened independently” and “one happened after the other”. The event component is the record of that distinction, and the join condition protects it.

What this means in practice is that joins are useful for reclaiming intervals whose holders did no independent work: a worker that forked, performed nothing but reads, and returned. A pair of replicas that have each accepted writes and replicated them to each other cannot be joined, and their intervals stay separate for the life of the deployment.

Where it sits in the family

Interval tree clocks are the general solution to causal timestamping under churn; vector clocks are the special case where the participant set is fixed and known. The scalar clock described in Happens-Before and the Scalar Logical Clock is the other extreme, collapsing every participant into a single counter. Systems with a fixed replica set should use version vectors, which are simpler, cheaper to compare, and easier to explain to a person reading a conflict. Systems where the set of writers is open should either restrict the set of writers per object, or accept the tree’s comparison cost.

The mechanism is also the clearest demonstration of a general principle in this cluster: causal metadata is expensive in proportion to the number of independent sources of events it must distinguish, and every representation is a choice about which of those sources to collapse. Scalar clocks collapse all of them, vectors keep them separate, and trees keep them separate while allowing the set to change shape.