Logical clocks and causal histories

Prerequisites: Directed graphs, partial orders, and message passing.

Learning objectives

• Construct a happens-before relation.
• Update Lamport clocks across sends and receives.
• Compare vector timestamps to distinguish order from concurrency.

Wall-clock timestamps can differ across machines and can move unexpectedly as clocks are corrected. A distributed algorithm often needs a more precise question: could one event have influenced another? The happens-before relation includes program order within one process, the sending of a message before its receipt, and every ordering implied transitively by those relations. Events with neither direction established are concurrent in this model, even if an outside observer believes one occurred earlier in physical time.

A Lamport clock assigns an integer to each event. Increment the local counter before a local or send event; attach the resulting value to a message. On receiving a message with timestamp t, set the local counter to max(local,t)+1. This guarantees that if event a happens before b, then C(a)<C(b). The converse is false: a smaller logical timestamp does not prove a causal path.

Trace two processes starting at zero. P performs local event a at 1 and sends message m at 2. Q performs an unrelated local event b at 1, then receives m at max(1,2)+1=3. Q sends a reply at 4; P receives it at max(2,4)+1=5. We can prove a precedes the reply receipt. Events a and b remain concurrent because neither process had learned about the other's event when it occurred.

Pairing a Lamport timestamp with a unique process identifier can produce a deterministic total order by breaking ties. That total order extends causality but introduces arbitrary order between concurrent events. It is useful for consistent ordering decisions, yet must not be interpreted as evidence that one concurrent event caused another. A log sorted by these pairs is a chosen serialization of observations, not a perfect physical timeline.

Vector clocks retain one component per participant in a simple fixed-membership model. Increment the local component for an event. On receipt, take the componentwise maximum with the message vector, then increment the receiver's component. Vector x precedes y when every component of x is at most the corresponding component of y and at least one is smaller. Incomparable vectors represent concurrency under the model.

For vectors[2,1] and[1,3], neither dominates: one has more knowledge of the first process and the other of the second. Vector[2,3] includes both histories, but an actual merge operation must still decide how conflicting application updates combine. A clock detects an ordering relationship; it does not choose a correct conflict-resolution policy automatically.

Vector size, changing membership, missing communication channels, and application-level causality complicate deployment. Use a message trace with explicit participants to establish the model first. Then ask which metadata the application needs: causal order, deterministic order, physical-time estimates, or a stronger coordination guarantee.

Practice problem

P and Q start with Lamport clocks 0. P sends m; Q performs two local events, then receives m, then sends a reply; P receives it. Calculate every clock value. Explain whether P’s send and Q’s first local event are causally ordered. Compare vectors[3,1], [2,4], and[3,4], and state what the comparison can establish without choosing a conflict-resolution policy.

Worked solution

P’s send is 1. Q’s local events are 1 and 2; receiving m sets its clock to max(2,1)+1=3, and the reply send is 4. P’s reply receipt becomes max(1,4)+1=5. P’s initial send and Q’s first event are concurrent unless an additional communication edge exists; their equal scalar timestamps prove no order. Vectors[3,1] and[2,4] are incomparable, while both precede[3,4]. The latter records knowledge including both histories under the vector-clock model, but does not say whether two conflicting field updates should be merged, rejected, or resolved by a domain rule. Metadata supports the decision; it does not supply the application semantics.

Check your understanding

Q’s Lamport clock is 5 when it receives a message stamped 3. What is its receive-event timestamp, and does 3<5 prove the send caused Q’s prior event at 5?

• 5; no receive increment is needed.
• 6; no, scalar inequality alone does not prove that causal path.
• 4; yes, all smaller timestamps are causes.
• 8; timestamps are summed on receipt.

Explanation

The update is max(5,3)+1=6. The message send precedes its receipt, but need not precede Q’s earlier event causally.

Compare vectors[4,2], [3,5], and[4,5] in the fixed-participant model. Which statement holds?

• All three are concurrent because no vectors are equal.
• The first precedes the second because 4>3.
• The first two are concurrent; both precede the third.
• The second precedes the first because 2<5.

Explanation

The first pair is incomparable; componentwise comparison puts each below[4,5].

Primary reading

• Time, Clocks, and the Ordering of Events in a Distributed System: Leslie Lamport
• Vector clocks, linearizability, and state machine replication: University of Washington

Open the study and save your work →