bits.

FREE CONTRIBUTION CHRONOLOGY · 1978–1991

The open distributed world

How do independent machines and communities coordinate without one perfect clock, route, owner, or institution?

The historical question

Logical time preserved causality; spanning trees stabilized local networks; open Web protocols connected global documents; free-software licenses and communities kept systems inspectable, forkable, and extensible.

Open distributed systems require both technical interoperability and institutional rules for change, conflict, stewardship, and exit.

Order, identity, and governance

In a distributed execution, event A sending a message precedes event B receiving it. Local events also have an order within a process. The transitive closure of these relations is a causal partial order. Two events can be concurrent when neither precedes the other; lack of a known order is not evidence that they occurred at exactly the same physical instant.

Lamport clocks assign integers so that causal precedence implies an increasing timestamp. The converse is false: a lower number does not prove causation. A deterministic total ordering can use a process identifier to break ties, but choosing an order is different from discovering a physical or causal fact. This distinction becomes important when protocols rely on ordering.

The Web adds a different form of coordination: shared identifiers and protocols let independently operated systems link and exchange resources. Open-source communities add permissions and procedures for inspecting, modifying, and distributing implementations. Interoperability, licensing, and project governance solve different problems. A protocol can be openly specified yet have a closed implementation; source availability alone does not imply every right to modify and redistribute. Ask which interface, legal permission, and decision process makes each form of participation possible.

What the evidence does not establish

Global history must include builders of regional Internet infrastructure such as Nii Quaynor, not only protocol authors based in the United States and Europe.

Reconstruction exercise

Two independent events receive Lamport timestamps 3 and 8. Can you conclude the first caused the second? Explain what evidence would establish a happens-before relation.

Worked solution

No. The clock condition is one-way: causal precedence implies increasing timestamps, but independent local activity can create different numbers. A chain of local ordering and message-send/receive relations would establish happens-before. Sorting by timestamp chooses a useful total order for some algorithms; it does not turn that chosen order into proof of causality.

Test the limits and transfer the idea

1. Event graph and clock calculation · allow 30 minutes

Trace logical clocks without inventing causality

P and Q start Lamport clocks at zero. P sends message m, then performs local event p2. Q performs local event q1, receives m, then sends reply r. P receives r after p2. Increment before local/send events; on receive set clock=max(local,message)+1. Assign all timestamps. Compare p2 with Q's receive of m: are they causally ordered? Show how a process-ID tie-break can choose an order without proving that relation.

Get a starting hint

Draw arrows only for local order and actual message send/receive pairs.

Compare your reasoning with the worked solution

P's send has timestamp 1 and p2 has 2. Q's q1 has 1, receive(m) has max(1,1)+1=2, and send(r) has 3. P's receive(r) has max(2,3)+1=4. There is no happens-before path from p2 to Q's receive(m), nor in reverse: both follow P's send, and their effects meet later. They are concurrent in this event graph despite sharing timestamp 2. Ordering (timestamp,process ID) can put one first deterministically, but that is an extension of the partial order rather than a discovered causal fact. Lamport's 1978 paper is the primary technical source; the event names and trace are original.

Check your reasoning

  • Assigns clocks 1,2 on P and 1,2,3 on Q before final 4.
  • Uses graph paths to establish concurrency.
  • Distinguishes a deterministic total order from causality.

2. Graph construction and limits · allow 30 minutes

Preserve reachability while removing forwarding cycles

Four bridges form a cycle with links AB, BC, CD and DA, each cost 1. In a simplified tree-selection model, root A has smallest ID; each other bridge chooses a shortest path to A, breaking equal parent choices by smaller parent ID, with B before D. Determine parents and active links. Then AB fails: compute the new tree. Explain why a final tree's correctness does not by itself prove a distributed implementation avoids transient loops during convergence.

Get a starting hint

Root-distance decreases along each selected parent edge; recompute distances after the failure.

Compare your reasoning with the worked solution

Initially B and D choose A at distance 1. C is distance 2 via either B or D, so it chooses B. Active links are AB, AD and BC; CD is blocked for the data-forwarding tree. After AB fails, the surviving path is A-D-C-B, so D chooses A, C chooses D and B chooses C, with distances 1,2,3. Both results span all bridges and contain three edges without a cycle. During a distributed transition, bridges can temporarily hold different generations of information; proving the final graph is a tree does not prove safe transitions or bounded recovery. Perlman's 1985 primary paper addresses distributed bridge coordination. The simplified graph exercise omits its detailed protocol states and must not be represented as the full algorithm.

Check your reasoning

  • Finds both parent maps and active edge sets.
  • Explains reachability and absence of cycles in each final tree.
  • Identifies convergence as a separate protocol proof obligation.

Check your understanding

What follows from L(A) < L(B) alone?

  • A physically occurred earlier everywhere
  • A necessarily caused B
  • No causal relation is established by that inequality alone
Explanation

No. The clock condition is one-way: causal precedence implies increasing timestamps, but independent local activity can create different numbers. A chain of local ordering and message-send/receive relations would establish happens-before. Sorting by timestamp chooses a useful total order for some algorithms; it does not turn that chosen order into proof of causality.

Sources and further reading