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

01 Claim ledger

What the paper is allowed to say

Each row is a sentence already in the study. The status is the same on every row: a model claim, not a live measurement.

1. Claim 01 · Paper model

   The defect

   A distributed system has no shared clock. 'Happened before' still has to be a partial order if you want to talk about causality.

2. Claim 02 · Paper model

   The proposal

   Lamport clocks number events so that if A happened before B, A's number is smaller. The converse is not true. That one direction is the whole idea.

3. Claim 03 · Paper model

   The relation is potential causality, not wall time.

   A total order can be built by breaking ties with process identities.

4. Claim 04 · Paper model

   The bound

   Equal numbers do not mean the events were concurrent. The converse failure is the point.

02 Three cuts

Observation, model, falsifier

A desk does not stop at the summary. Each claim is cut three ways, using only this study's own assumptions and checks. Nothing here is a new figure.

1. 01 The defect

   Observation

   What the study says

   A distributed system has no shared clock. 'Happened before' still has to be a partial order if you want to talk about causality.

   Model

   What has to hold

   Physical clock synchronisation in the second half is a different construction.

   Falsifier

   What would retire it

   Is a total order required, or is the partial order enough?

2. 02 The proposal

   Observation

   What the study says

   Lamport clocks number events so that if A happened before B, A's number is smaller. The converse is not true. That one direction is the whole idea.

   Model

   What has to hold

   Equal numbers do not mean the events were concurrent. The converse failure is the point.

   Falsifier

   What would retire it

   Can two events have the same number?

3. 03 The relation is potential causality, not wall time.

   Observation

   What the study says

   A total order can be built by breaking ties with process identities.

   Model

   What has to hold

   Physical clock synchronisation in the second half is a different construction.

   Falsifier

   What would retire it

   Is a total order required, or is the partial order enough?

4. 04 The bound

   Observation

   What the study says

   Equal numbers do not mean the events were concurrent. The converse failure is the point.

   Model

   What has to hold

   Equal numbers do not mean the events were concurrent. The converse failure is the point.

   Falsifier

   What would retire it

   Can two events have the same number?

03 Sequence

One action, as an operating tape

1. 01Each process increments a counter on its own events.
2. 02On a message, the receiver jumps ahead of the timestamp it received.
3. 03Comparing numbers respects sends-before-receives.
4. 04Can two events have the same number?

04 Load-bearing

The argument, and where a pitch drops it

1. What the paper is for

   The cut

   A protocol that says 'we timestamp it' should say whether the timestamp respects happened-before or only records a wall clock.

   Why it carries weight

   If this cut is skipped, the paper's name is being used without the mechanism that makes the name mean anything.

   Where it is dropped

   Physical clock synchronisation in the second half is a different construction.

2. What happened after

   The cut

   Vector clocks, consensus logs and every chain's notion of causal history sit downstream of this paper.

   Why it carries weight

   If this cut is skipped, the paper's name is being used without the mechanism that makes the name mean anything.

   Where it is dropped

   The paper does not elect a leader.

05 Register

What has to be true

• Model · Not re-measured

  Equal numbers do not mean the events were concurrent. The converse failure is the point.

• Model · Not re-measured

  The paper does not elect a leader.

• Network · Not re-measured

  Physical clock synchronisation in the second half is a different construction.

06 Divergence

What happened after the paper

Vector clocks, consensus logs and every chain's notion of causal history sit downstream of this paper.

A later client, parameter set, or reward formula is a different object. Cite this paper for the mechanism. Cite a primary release for the network. This desk has not re-run the proof.

07 Pre-mortem

What to check before you use the idea

1. Kill test 1Does the clock respect send before receive?
2. Kill test 2Can two events have the same number?
3. Kill test 3Is a total order required, or is the partial order enough?
4. 0 of 3 marked on this browser. A mark is a reading note, not a pass, a rating, or a recommendation.

08 Anatomy

The paper, in the order a builder needs

09 Lexicon

Terms, opened into the record

Happened-before

The partial order of events that could have influenced each other.

Logical clock

A counter that tracks that order, not a wristwatch.

10 Repository

Every linked record on this page

Underlined words open a page that already exists: a concept, a protocol profile, a failure record, or another paper. If a word is not underlined, this desk does not have a record for it.

11 Related

The next papers, as theses

• Paxos · 1998

  The Part-Time Parliament

  A value is chosen only when a majority has accepted it in some ballot, and every higher ballot must honour a value that majority might already have chosen.

• Raft · 2014

  In Search of an Understandable Consensus Algorithm

  A strong leader accepts entries, replicates them in order, and commits only when a majority of the current term has stored them.