Distributed consensus, replication, and fault tolerance / personal lessonsLesson 3 of 17
Distributed systems · Lesson 3

Causality and logical clocks

Distinguish message order, wall-clock time, and concurrent events.

By the end: Use message dependencies and vector comparisons without confusing numerical order with causation.

Build an order from evidence

Within one sequential process, an earlier event precedes a later one. Sending a message precedes receiving that message. These relationships compose: if a precedes b and b precedes c, a precedes c. Their transitive closure is the happened-before relation. Two events are concurrent when neither precedes the other in this relation. Concurrent does not mean their physical timestamps are identical.

Suppose Ada posts a question and Bo reads it before posting an answer. The answer depends on the question through messages and local computation. Another user can change a profile without observing either event. There need not be a causal order between that independent change and the answer. Causal consistency will require a reader who sees the answer to see its prerequisite question, but need not impose a single order on unrelated changes.

Construct causal paths one event at a time

An event is a particular occurrence, such as a local update, a message send, or a message receive. Give occurrences distinct names even when they carry identical data. Sending the same bytes twice creates two sends; receiving a duplicate creates another receive. For a sequential process, its execution supplies a local order. A message adds a directed relationship from its particular send to its receive. Combining these relationships produces happened-before. The relation describes possible information flow under the model, not proof that one event psychologically motivated another person's action.

Work through a separate paper conversation involving three processes. A creates a document at event a, then sends its identifier to B at event b. B receives it at c, adds a comment at d, and sends the comment to C at e. C receives at f and displays the comment at g. Local order gives a before b, c before d before e, and f before g. The two messages give b before c and e before f. Following the connected path establishes a before g even though A never sent a message directly to C.

Suppose C also changes its local theme at event h before receiving the comment. We know h precedes f at C, but that does not put h before a or a before h. Both a and h may be predecessors of g without being ordered relative to one another. Sharing a later observer does not mean earlier independent events communicated. On paper, trace paths in their allowed direction. You cannot travel backward from f to e and then forward along some other branch to invent a dependency. Transitivity only joins relationships that point forward throughout.

This gives a partial order, an ordering in which some pairs remain incomparable. A total order compares every distinct pair. A system can extend a partial order by arbitrarily ordering previously incomparable events, but the added relationships do not become discoveries about message flow. For example, sorting two unrelated updates by actor name can be a consistent presentation convention. It does not prove that the alphabetically first actor acted earlier in physical time or that either actor observed the other's update.

Concurrency therefore depends on the event model and the dependencies it records. If processes communicate through shared storage, those observations may need representation too; ignoring a real communication path can make dependent events look independent. If one server has concurrent threads, a single sequential line is an abstraction that needs justification or additional local synchronization relationships. This course's clock examples use sequential participants and explicit messages. Within that scope, concurrent means neither event has a happened-before path to the other, even if their physical executions occurred at noticeably different times.

A scalar logical clock preserves one direction

A Lamport clock is an integer. Increment it before each local event or send. Attach its value to outgoing messages. On receiving a message stamped m, set the local clock to max(local, m)+1 for that receive event. The resulting values increase along every happened-before path. If a happened before b, its timestamp is smaller.

The converse is false. Independent processes can produce timestamps 2 and 7 without communicating. Sorting by timestamp and then process identity gives a total order consistent with known causal edges, but some of that order is an arbitrary tie-breaking convention. It does not reveal physical time or deliver missing messages. Clock labels alone do not make a replicated log agree on which commands exist.

Calculate scalar timestamps without inventing causality

Start a paper calculation with all Lamport counters at zero. A's first local event increments A to 1. Its next event sends a message stamped 2. Meanwhile B performs four independent local events and reaches 4. When B receives A's message, it compares local 4 with incoming 2, chooses 4, and increments to 5. Its next send carries 6. If C was at zero when that message arrived, C's receive becomes 7. The chain of sends and receives increases, while B's earlier work explains why the labels are not simply a count of network hops.

The maximum operation matters when a receiver is behind. If C instead kept its own counter and incremented zero to 1 on receiving B's stamp 6, the send would have label 6 and the receive label 1. That would violate the property we need. Setting the receiver to one more than the greater value ensures it exceeds both its own preceding event and the incoming send. Local increments protect local edges; the receive rule protects message edges. Transitivity then makes labels increase along every longer causal path as well.

A large label does not measure work done at that process. C can jump from zero to 7 after just one receive because it has learned a timestamp from elsewhere. Nor does subtracting labels estimate elapsed time. The gap between 2 and 6 can reflect independent local events, message propagation of a larger value, or several dependencies. No rate in events per second follows from the numbering rule. The clock measures an ordering constraint, and even that constraint works in only one direction when you infer causality from scalar numbers.

For a counterexample, let independent process D execute its first event with label 1 while C later executes an unrelated event with label 8. The inequality 1 less than 8 holds without any path from D to C. Distinct processes can also produce equal labels. A tie-breaking rule can compare pairs consisting of a Lamport label and a stable process identifier. Compare labels first and identifiers only when labels tie. This gives a total ordering consistent with happened-before, provided every event has a unique position under the naming scheme.

That sorting convention is not an agreement or delivery protocol. Two replicas can apply the same comparison rule but possess different event sets because a message is delayed. The replica holding only a later-sorting event does not automatically know whether some missing earlier-sorting event will arrive. Likewise, a timestamp cannot prove that no competing command exists. Later consensus lessons add evidence and obligations that scalar labels alone do not supply. Use logical timestamps to preserve known order, and ask separately how a system determines which commands belong in the authoritative history.

Work through the model

ABCsend, L=2receive, L=6local L=5independent event, L=3
Horizontal position is illustrative, not synchronized wall time. On receive, B sets its logical clock to max(5,2)+1=6. The number 3 on C does not prove that A's event caused C's event.
VersionA events knownB events knownRelation to [2,0]
[2,0]20Equal
[2,1]21After
[1,1]11Concurrent
Compare every component. A larger sum is not a causal ordering rule.

Interpret the causal drawing and vector comparison separately

The drawing above fixes B's local Lamport value at 5 before it receives A's message stamped 2. B's receive therefore has label 6. The arrow establishes the send-to-receive dependency. C's independent event has label 3, but there is no arrow path from A's send to that event or from it to B's receive. Numerical placement between 2 and 6 does not insert C into the message chain. Horizontal positions are schematic. They do not establish synchronized physical times or quantify how long the message spent traveling.

The nearby evidence table introduces a vector, a list of counters with one slot per tracked actor. Unlike one scalar label, it preserves which actor's progress is known. In these two-actor examples, the first component always belongs to A and the second always belongs to B. Relative to [2,0], vector [2,1] contains at least as much information in both slots and strictly more in B's slot. Vector [1,1] has less A information and more B information, so neither vector dominates the other. Adding their components would discard which actor supplied the information. The sums of [2,0] and [1,1] both equal two even though the histories differ.

Derive those relations with a separate two-actor paper trace. Begin at [0,0] on both actors. A has a local event and becomes [1,0]. B independently has a local event and becomes [0,1]. A then sends a message as its next event and stamps [2,0]. B merges that incoming vector with [0,1] by taking the maximum in each slot, obtaining [2,1], and increments its own B slot for the receive, obtaining [2,2]. The send precedes the receive because every send component is no greater and B's component increases.

Notice the intermediate [2,1] in that calculation. It is the merge result before the receive increment, not the receive event's final timestamp under this convention. This distinction prevents mixing conventions when checking a worked trace. Implementations that timestamp versions rather than every program event may increment at different semantic boundaries. Their metadata needs its own definition. The static table's vectors illustrate comparison; they do not assert that every listed vector is a timestamp from one particular complete execution of the drawing.

To explore the comparison rule, copy [2,0] and [1,1] onto paper. Raising only the second vector's A component to 2 produces [2,1], which now follows [2,0]. Raising only the first vector's A component to 3 leaves it incomparable with [1,1]. Neither larger sums nor larger first components decide the relationship alone. The page's drawing and table do not let you enter arbitrary events or animate these changes. These additional cases are manual calculations using the stated rules, not hidden capabilities of an interactive clock simulator.

Vectors retain more information

A vector clock keeps one counter per tracked participant. Increment your own component for a new event. When receiving a vector, merge componentwise maxima and increment your component. One vector precedes another if every component is no greater and at least one is smaller. If each vector exceeds the other in some component, they are incomparable and represent concurrent histories in this model.

For example [2,0] precedes [2,1], but [2,0] and [1,1] are incomparable. Version vectors in storage systems use related ideas to track versions rather than every program event; actor identity, pruning, and membership require care. A vector can expose a conflict but cannot decide whether two reservations should both stand. Physical clocks can support useful time bounds, but skew, drift, and process pauses must appear in any safety argument that depends on them.

Preserve actor identity and separate order from policy

A vector component summarizes a particular actor's ordered events. In the two-actor trace, A's count 2 includes its earlier count 1 because A produced both sequentially. B can retain the maximum A count when combining information because a greater count for that same actor includes its earlier prefix. This reasoning needs stable actor identity and counters that do not silently go backward. The vector length alone is not enough; every participant must agree which actor owns each slot and what that counter summarizes.

Suppose A previously reached counter 7, then restarts with empty memory and reuses the same identity starting at 1. A new event can receive metadata that other replicas interpret as older than already-known A events. A concurrent replacement using the same identity is worse: two independent histories can claim the same counter values. Taking a maximum then loses the distinction. Persisting the counter or assigning a properly distinguished new actor incarnation can avoid that particular error, but changing membership and retiring old metadata needs a larger protocol. The fixed-actor examples do not implement those procedures.

Version metadata also does not resolve application meaning. Suppose two document versions have vectors [4,1] and [2,3]. The metadata identifies neither as containing the other. A text editor may retain both for user reconciliation, or apply a separately defined merge procedure. A reservation service cannot simply keep two exclusive owners and call the conflict resolved. Ordering information can tell a system that a conflict exists without telling it which business promise is acceptable. A merge that converges everywhere may still discard a valid update or violate an invariant.

Equal vectors deserve a similarly narrow reading. In a correctly maintained event-clock model, equal metadata represents the same tracked causal progress. It does not validate arbitrary payload bytes or establish that a sender is honest. A corrupted or dishonest process can attach incorrect metadata. Even authenticated messages establish who supplied a claim rather than proving that its counter accurately summarizes prior events. The course's ordinary clock examples assume participants follow their rules. The later Byzantine lesson changes that assumption and explains why signatures alone cannot replace behavioral protocol restrictions.

Physical clocks answer a different question. An event stamped 10:00 on A and another stamped 09:59 on B may appear reversed because the clocks disagree. Even synchronized clocks with a stated error bound leave close events uncertain, and a timestamp earlier in physical time does not itself prove a message dependency. Logical clocks avoid requiring synchronized wall time for their causal property. They do not establish lease expiration, current leadership, or the freshness of applied state. Later read protocols must prove current authority and application through a safe prefix. Causal metadata can support dependencies while leaving those separate obligations unresolved.

Exercises

Infer the right direction

Event x has Lamport time 4 and event y has time 9. Does x necessarily cause y?

Hint

What evidence did the logical-clock rule preserve, and what did it discard?

Worked answer
EvidencePermitted inference
x happened before yL(x) < L(y)
L(x) < L(y)Causality remains unknown
The implication cannot be reversed.

No. A causal path would require increasing timestamps, but increasing timestamps do not establish a path. Independent processes can generate those values. Inspect local order and actual message dependencies, or suitable vector metadata.

Compare concurrent edits

A cart version has vector [3,1] and another has [2,2]. Can either be discarded as causally older using only these vectors?

Hint

Compare A and B components separately.

Worked answer
ComponentFirst versionSecond version
A3, greater2
B12, greater
Each history contains information the other lacks.

No. The first knows more A events; the second knows more B events. They are concurrent under this metadata. Retain or merge the conflicting versions according to the data type’s semantics. Picking the larger component sum would not resolve the causal question.

Sources and further reading

The explanations and worked answers above stand alone. These references provide the original algorithms, assumptions, and deeper proofs; they are not required downloads.