Time, Clocks, and the Ordering of Events in a Distributed System

How to read the original

1. Read The Partial Ordering and draw the three rules as edges.
2. Read Logical Clocks and reconstruct why every causal edge increases its timestamp.
3. Read Ordering the Events Totally, then distinguish that extension from causal knowledge.

What counts as earlier?

Lamport separates an observable causal relation from a convenient numerical ordering. Process order, message transmission, and transitivity define happened-before. A logical clock must respect that relation. The converse is not promised: a smaller scalar timestamp does not establish that one event influenced another. Read the paper with those two implications written separately, because confusing them changes the meaning of every subsequent coordination claim.

Original reconstruction: three processes and two messages

Use processes A, B, and C, each starting its integer counter at zero. Increment before a local event or send. Attach the resulting count to a message. On receiving a message stamped t, set the local counter to max(local,t)+1 and assign that value to the receive event. These concrete conventions are one implementation of the clock condition.

A first performs local event a1, stamped 1, then sends message m at a2, stamped 2. Independently, B performs b1 and b2, stamped 1 and 2. B receives m at b3, obtaining max(2,2)+1=3. B then sends n at b4, stamped 4. C performs local event c1, stamped 1, and receives n at c2, obtaining max(1,4)+1=5.

The chain a2→b3→b4→c2 establishes that a2 happened before c2. The local edge a1→a2 extends the chain. By contrast, the model contains no message or process path connecting a1 to b1. They are concurrent in the happened-before relation even if a wall-clock observer happened to see one physically first. Concurrency here means absence of a modeled causal path, not necessarily equal physical time.

Now compare b2, stamped 2, with c1, stamped 1. Numerical order places c1 first, but the graph supplies no causal relationship. This is the smallest useful counterexample to treating timestamps as a complete causal history. Equal timestamps likewise cannot occur on a strict happened-before path under this clock rule, but different timestamps can still belong to concurrent events.

Extend the order without inventing evidence

To sort a log deterministically, compare pairs (timestamp,process_id), using A<B<C for ties. Events a1, b1, and c1 now have an unambiguous order. Every causal edge remains respected, while some previously unordered pairs acquire an arbitrary ordering. The tie breaker is a coordination convention, not a newly discovered physical fact.

A timestamp also does not tell a receiver that no earlier message is still in flight. Imagine C has seen a timestamp of 5 while a message stamped 2 is delayed elsewhere. Sorting currently available records does not establish that the final prefix is complete. A protocol needs acknowledgements, membership rules, delivery assumptions, or another mechanism before acting on a supposedly finished prefix.

What to test and what to avoid claiming

Build a table of events with process, local predecessor, sent message, received message, and assigned clock. Check every local edge and every send-to-receive edge for a strict increase, then compute reachability to distinguish causality from sorted order. Remove a message edge and observe which conclusions disappear. Do not infer elapsed duration from logical-clock differences: a jump from 1 to 100 may come from receiving one message rather than ninety-nine local operations.

The model depends on which interactions are represented. If a person phones another person and triggers a request, that external communication is absent unless the system models it. Physical-clock reasoning requires separate drift and communication assumptions. This distinction makes the paper useful for diagnosing what a trace establishes, rather than merely teaching how to number events.

Reconstruction exercise

Three processes start at zero. A sends x as its first event. B performs two local events, receives x, then sends y. C receives y as its first event. Assign timestamps using the stated rule. Identify one pair whose numeric ordering does not establish causality. Explain why receiving y does not prove that every smaller-timestamped event has been collected in C’s log.

Worked solution

A’s send has timestamp 1. B’s local events receive 1 and 2; receiving x gives max(2,1)+1=3; sending y gives 4. C’s receive gives max(0,4)+1=5. A’s send causally precedes B’s receive and C’s receive through message and local edges. B’s first local event and A’s send are concurrent despite sharing timestamp 1. B’s second local event, stamped 2, is also not proved causally after A’s send merely by the numerical comparison: neither has a path to the other before the receive. C knows that the send of y and its causal predecessors happened before its receive, but it does not possess a complete system history. Other processes may have performed low-numbered concurrent events whose records are delayed or never transmitted to C. Completeness needs a collection protocol and assumptions beyond monotonic clocks.

Test the limits and transfer the idea

1. Event trace and partial order · allow 45 minutes

Compute clocks without inventing causality

Three processes start logical clocks at zero. Increment on each local or send event; on receive set the clock to max(local,message)+1. Local event order is A: a1 sends m, a2 receives r; B: b1 local, b2 receives m, b3 sends n; C: c1 local, c2 receives n, c3 sends r.

Compute all timestamps. Draw the local-order and send-receive edges, then find every unordered pair of concurrent events. Give one pair with different timestamps that is still concurrent. Produce two legal total orders extending happened-before and explain why a particular clock-plus-process-id order is only one extension.

Get a starting hint

Compute along message paths, not by the order in which process lists are printed. Two events are concurrent when neither is reachable from the other in the event graph.

Compare your reasoning with the worked solution

The timestamps are a1=1, b1=1, b2=2, b3=3, c1=1, c2=4, c3=5, and a2=6. For example c2 receives timestamp 3 while C's local clock is 1, so it becomes 4. The final receive at A takes max(1,5)+1=6.

Local edges are a1→a2; b1→b2→b3; c1→c2→c3. Message edges are a1→b2, b3→c2, and c3→a2. Taking transitive closure yields exactly five concurrent unordered pairs: {a1,b1}, {a1,c1}, {b1,c1}, {b2,c1}, and {b3,c1}. In particular c1 has timestamp 1 and b3 has timestamp 3, yet neither can reach the other. Numeric clock order alone does not prove happened-before.

Two legal total orders are a1,b1,c1,b2,b3,c2,c3,a2 and c1,b1,a1,b2,b3,c2,c3,a2. Every graph edge points forward in both. With process tie-break A<B<C, sorting the computed pairs (timestamp,process) selects the first order. A different tie-break can select another. The graph itself does not require an order among concurrent events.

The exercise uses the paper's logical-clock condition and a new event graph. It does not reconstruct physical times or infer that a smaller timestamp means a message could have influenced a later-numbered event. Reachability establishes causality in this model; the total order supplies a deterministic extension useful to an algorithm.

Check your reasoning

• Computes all eight timestamps and exactly five concurrent pairs.
• Uses graph reachability to refute the converse of the clock condition.
• Gives two valid total extensions and explains the tie-break choice.

2. Protocol counterexample · allow 55 minutes

Break mutual exclusion by removing an assumption

Study the paper's request-queue mutual-exclusion algorithm after the initial holder has released and all queues are empty. Use two processes A<B and clocks initially zero for this teaching trace. Each requests at timestamp 1. A request is locally grantable when it is first in that process's timestamp-ordered queue and the process has received a later-timestamped message from every peer. Receiving a request queues it and sends an acknowledgment.

Remove only FIFO delivery on A→B. Deliver B's request to A, then deliver A's later acknowledgment to B before A's earlier request. Construct a complete trace in which both enter the critical section without either releasing. Show precisely where FIFO would block it. Assume reliable eventual delivery and that a process continues handling messages while in its critical section.

Get a starting hint

B can mistake a later acknowledgment for evidence that no earlier A request remains in flight. After B enters, deliver A's delayed request and let B acknowledge it.

Compare your reasoning with the worked solution

Both queues initially contain only their own request, (1,A) or (1,B). A receives B's request, advances its clock to 2, queues (1,B) behind (1,A), and sends an acknowledgment timestamped 2 as part of that receive action. Hold A's earlier request in transit, but deliver this acknowledgment to B. B's clock becomes 3. Its queue still contains only (1,B), and it has a message from A timestamped later than its request. B therefore enters; count that local event at clock 4 if entry itself is modeled as an event.

Now deliver A's delayed request (1,A) to B. B advances to 5, queues A before B, and sends an acknowledgment timestamped 5. The algorithm does not retroactively revoke B's ongoing critical section. A receives that acknowledgment and advances to 6. A's queue has A first, and it now has a later-timestamped message from B, so A also enters before B releases. Mutual exclusion is violated.

FIFO on A→B would require B to receive A's request before the acknowledgment sent later on that same channel. B would then see (1,A) ahead of its own request and could not enter first. The counterexample therefore violates an explicit assumption of the simplified protocol; it is not a counterexample to its proof under that assumption. The paper notes that message numbering and acknowledgment protocols can supply the necessary ordering when the transport does not. Logical timestamps alone cannot reveal an earlier message still hidden in transit.

Check your reasoning

• Constructs both local grants with correct queue contents and later-message evidence.
• Identifies the reordered A request and acknowledgment as the decisive FIFO violation.
• Distinguishes a removed-assumption counterexample from a failure of the stated theorem.

Check your understanding

A has timestamp 4 and B has timestamp 9, with no known causal path. What follows?

• A physically occurred first.
• A caused B.
• The clock values alone do not establish causality.
• B must have received a message directly from A.

Explanation

Scalar clocks preserve causal order in one direction; their numerical order is not its converse.

A receiver has local clock 7 and receives a message stamped 12. What is its receive timestamp under this lesson’s rule?

• 13
• 8
• 12
• 19

Explanation

The update is max(7,12)+1=13, preserving both local and message ordering.

Original paper and sources

Leslie Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM, 1978.

Read the original paper →

Read the primary paper: Leslie Lamport

• Time, Clocks, and the Ordering of Events in a Distributed System: Leslie Lamport