Causal order: what a logical clock can and cannot tell you

First principles

Distributed programs often need to answer whether one event could have influenced another. Physical timestamps are an imperfect proxy: machines can disagree about time, clocks can be corrected, and two independent events can receive the same timestamp. Causality instead begins with observable relationships. Events in one process have a local order; sending a message happens before receiving that message; and the happens-before relation is the transitive closure of those rules.

A Lamport clock assigns an integer to each event. A process increments its counter before local events and before sending; when it receives a message timestamped t, it sets its counter to at least t and increments. This preserves an important direction: if event a causally precedes event b, then the Lamport value of a is less than the value of b. The converse is false. Two unrelated events can have values 4 and 9 simply because one process performed more local work. A Lamport clock creates a consistent ordering when combined with a tie-breaker, but that total order should not be mistaken for causality.

A vector clock stores one counter per participant in a known set. A process increments its own component for each event. On receipt, it takes the component-wise maximum of its local vector and the incoming vector, then increments its own component. For vectors A and B, A < B when every component of A is less than or equal to its corresponding component in B and at least one is strictly less. If neither vector is less than the other, the represented events are concurrent according to that model.

The word “according” matters. A vector clock assumes a stable definition of participants and reliable propagation of the metadata. Membership changes require a policy for new components, removed nodes, and old histories. Some systems use dotted version vectors, epochs, or other compact summaries. A vector-clock comparison is not a consensus decision, does not order every pair of events, and cannot establish that two physical clocks were synchronized.

Runnable example

This small Python example compares two version vectors. Component names are stable replica identifiers; missing components count as zero only because this example uses a fixed, shared identity space. Run with Python 3.10 or newer.

def compare(left, right):
    replicas = set(left) | set(right)
    less = any(left.get(replica, 0) < right.get(replica, 0) for replica in replicas)
    greater = any(left.get(replica, 0) > right.get(replica, 0) for replica in replicas)
    if not less and not greater:
        return "equal"
    if less and not greater:
        return "before"
    if greater and not less:
        return "after"
    return "concurrent"


print(compare({"east": 3, "west": 1}, {"east": 2, "west": 2}))
print(compare({"east": 3, "west": 1}, {"east": 4, "west": 2}))

The output is concurrent and then before. In the first comparison, one history has more east events while the other has more west events; neither contains all the causal knowledge of the other. In the second, every component is no smaller in the right vector, so the left history is represented as preceding the right one. A production implementation should validate counter types and bounds, define what unknown replica IDs mean, and avoid treating malformed or truncated metadata as authoritative.

Contextual failure case

A team sorts events by Lamport timestamp and then reports that the sorted list is the actual order in which users performed actions. The tie-breaker makes the list deterministic, which is useful for display and replay. It does not prove that the lower-numbered event caused the higher-numbered event. Two independent users may have acted without observing each other's work. A downstream conflict resolver that treats the display order as truth can silently discard a valid update.

Vector clocks provide more information but have costs. Their metadata can grow with the number of independent writers, and replicas need consistent identity across restarts. If a replica ID is reused after losing its state, it can make new events appear to belong to an old history. If clients omit vectors, merge operations may not be able to distinguish missing knowledge from concurrency. A version vector is evidence about propagation under stated assumptions, not a general-purpose timestamp.

Use causal metadata when the product needs to preserve concurrent edits, explain why one value supersedes another, or let users merge conflicting branches. If the only requirement is stable pagination or display, a unique database ordering key may be simpler. If the requirement is one globally chosen leader or one total order of writes, use a protocol designed for that guarantee rather than sorting logical counters after the fact.

Verification

Test equal vectors, strict precedence, reverse precedence, and incomparability. Then test message propagation: a sender increments its component, includes the vector in a message, and a receiver merges by component-wise maximum before incrementing itself. Assert that the receiver's event compares after the send event. Add a concurrent local event on another replica and verify neither vector precedes the other.

For production telemetry, record the protocol's event ID and causal metadata with bounded cardinality and an explicit schema version. Do not use wall-clock timestamps as the only proof of causality. When debugging a trace, separate the event's physical time from the logical relation and understand which events were actually observed. Delivery semantics covers the different question of when a consumer considers a message handled.

Exercise

Create three replicas and write a trace with a local update at A, a message from A to B, and an independent update at C. Compute the vectors by hand, then have B receive A's message and create a later update. Identify which pairs are ordered and which are concurrent. Finally, restart C with a fresh process identity and explain why reusing its old identifier without its durable counter would corrupt the comparison.

Safety and caveats

Logical clocks do not measure elapsed time, prove real-world event order, or prevent conflicting writes. Vector-clock semantics depend on identity management, metadata preservation, and a correct merge rule. Implementations often use optimized variants whose behavior is not identical to this teaching example. Apply the protocol documented by the system you operate; do not add ad hoc vector metadata to an existing event format and assume every consumer will preserve it.