The Clock That Ran Away: What Became of Time, Clocks, and the Ordering of Events

The Intellectual Genealogy of Lamport's 1978 Paper

Concept by Carlos Baquero · Execution by Claude agents — August 2026 · PDF edition

Seed paper: Leslie Lamport. “Time, Clocks, and the Ordering of Events in a Distributed System.” Communications of the ACM 21(7), July 1978, pp. 558–565.

## 1 The Original Intervention

Let us set the scene. It is the ARPA-net era, and the Operating Systems section of Communications of the ACM, edited by R. Stockton Gaines, publishes an eight-page paper on what "before" and "after" can possibly mean when computers only communicate by exchanging messages. The author, Leslie Lamport, is at Massachusetts Computer Associates; the address line on the paper reads SRI.

A genealogy usually begins with a birth record, and this paper carries its own, in the acknowledgment: "The use of timestamps to order operations, and the concept of anomalous behavior are due to Paul Johnson and Robert Thomas." That is RFC 677, the 1976 work on maintaining duplicate databases — the same RFC that our previous genealogy (Report 0) traced as the source of the last-writer-wins register. One document from 1976 seeded two lineages that are usually told as separate stories; we will come back to this in the final section.

The generative insight, however, came from physics, and here we have the author's own testimony: "I happen to have a solid, visceral understanding of special relativity...This enabled me to grasp immediately the essence of what they were trying to do." The paper does not hide the debt. "This definition will appear quite natural to the reader familiar with the invariant space-time formulation of special relativity," it says of its central relation, and two of its four references are Schwartz's *Relativity in Illustrations* and Taylor and Wheeler's *Space-Time Physics*. Half of the bibliography of what would become one of the most cited papers in computer science consists of physics textbooks.

The analogy is not decoration; it does real work. In the invariant formulation of special relativity there is no universal present: observers can disagree on the order of distant events, and what all of them agree on is only the causal order, the order that signals could have established. Replace signals with messages and the distributed system is in the same predicament. A node has no way of knowing what "now" means at another node; the only order it can trust is the one that messages could have carried. That is the essence Lamport grasped immediately, and it is why the definition needs no clock to state.

Now the contents, in the order the paper presents them. First, the definition: *happened-before* is the smallest relation that respects the order of events within each process, orders the sending of each message before its receipt, and is transitive. Events unrelated by it are concurrent — not simultaneous, simply unordered, because no chain of local steps and messages connects them. There is no physical time anywhere in this definition; "before" is reconstructed entirely from what the system itself can observe. Second, the algorithm: logical clocks, counters satisfying the Clock Condition — if a → b then C(a) < C(b) — and maintained by two simple implementation rules, IR1 and IR2. Third, the extension: breaking ties between equal clock values by an arbitrary ordering of processes (the paper's own qualifier is "somewhat arbitrary") turns the partial order into a total one. Fourth, an illustration of what a total order buys: a distributed mutual-exclusion algorithm in five rules. And then, almost as an aside, the passage that would matter most: "The synchronization is specified in terms of a State Machine ... Each process independently simulates the execution of the State Machine." Any service, replicated on every node, by feeding every replica the same totally ordered log of commands. Fault tolerance is explicitly deferred — "the failure of a single process will make it impossible for any other process to execute State Machine commands," and "the problem of failure is a difficult one, and it is beyond the scope of this paper." The conclusion promises: "A future paper will show how this approach can be extended to solve any synchronization problem."

The second half of the paper deals with what it calls anomalous behavior. A person issues a request at computer A, then makes a telephone call, and a second request B is issued elsewhere; the system, knowing nothing of the call, may order B earlier. Causality flowed through a channel the system cannot observe. The example draws the boundary between the causality a system can track and the causality that runs outside it, and everything in the second half follows from taking that boundary seriously. Fixing this requires the Strong Clock Condition, and the remedy is physical clocks kept in synchrony: conditions PC1 and PC2, a rule that clocks are never set back, and a theorem bounding how far the clocks can drift apart, ε ≈ d(2κτ + ξ), proved in an appendix. Of this theorem, and only of this, the paper claims novelty: "we believe this theorem to be a new result."

Read this way, the paper carries its own ranking of its contributions. The definitions are offered as natural; the mutual-exclusion algorithm is an illustration; the state machine is a passing remark; the theorem is the declared contribution. Keep this ranking in mind. History will not.

## 2 The First Descendants

Counting the descendants is less obvious than it looks. The 1978 paper — the seed, as we will call it from here on — was reprinted in a 2019 ACM Books anthology, and the anthology's citation record turns out to be 89% database artifact: 1,759 of its 1,982 recorded citers predate 2019, and a paper cannot cite a reprint that does not yet exist. Merging the cluster recovers 645 distinct works and yields our corpus: 9,110 unique citing works. Anyone doing quantitative history of science on top of raw citation databases should expect surprises of this kind.

The earliest wave, up to 1983, counts 146 works, and its composition is instructive: it is a scatter, not a school. Database concurrency control dominates — Bernstein and Goodman's 1981 survey, multiversion timestamp ordering. Thomas's majority consensus paper of 1979 is there, the sibling from RFC 677. So are security protocols (Merkle, 1980), distributed elections (Garcia-Molina, 1982), deadlock detection, version vectors (Parker, 1983), and distributed estimation (1982). Ricart and Agrawala (1981) optimize the mutual-exclusion algorithm, treating the illustration as the contribution. Five years in, the paper was already being read for many different things — just not, as we will see, for the thing its author considered central.

What was it being read for, exactly? Of the citing works, 5,818 carry citation contexts, roughly 14,000 sentences in all. This is a cap-truncated sample, so the percentages that follow should be read as portraits rather than measurements. The intent labels split into 3,998 background, 1,629 methodology, and only 62 result citations: this is a paper cited for its concepts, almost never for a result. The distinction matters for what follows. A result can be superseded; a concept, once it enters a community's vocabulary, can only be renamed. Much of this genealogy is the story of those renamings. Among the concepts, happened-before (or happens-before) appears in 29.0% of the contexts, logical or Lamport clocks in 19.1%, and the state machine in 6.5%. The author has been keeping score himself: "This is my most often cited paper. Many computer scientists claim to have read it. But I have rarely encountered anyone who was aware that the paper said anything about state machines." And elsewhere: "People seem to think that it is about either the causality relation on events in a distributed system, or the distributed mutual exclusion problem."

The era-by-era numbers refine the picture. The state-machine reading stood at 2.4% of contexts in 1978–89, fell to 1.2% in the 1990s, then rose to 5.8% in the 2000s, 8.1% in the 2010s, and 7.7% in the 2020s — a revival whose cause we will identify in Section 4. Meanwhile the eponym grew without pause: "Lamport clock" appears in 418 contexts and "Lamport timestamp" in 187, terms the paper itself never uses, and the eponym share climbs monotonically from 3.5% to 10.0% across the eras. And the founding physics? Across those fourteen thousand sentences, relativity is mentioned 17 times and space-time 49. In reception, the framing that generated the paper is extinct.

## 3 The Branching

By a branch we mean a sustained line of research that took something from the seed and grew its own canon, venues, and vocabulary around it. A caution before counting: the branches below were assigned at survey depth, from metadata rather than full texts, so the figure of ten should be read as a map, not a census. With that reservation, the descent organizes into ten lines.

1. **Causality theory.** Vector clocks (Fidge and Mattern, 1988–89), preceded by Parker's version vectors (1983); Charron-Bost; the school of Raynal, Garg, and Kshemkalyani. This is the faithful line: both vector-clock papers cite the seed, and even so, 25.0% and 23.7% of their own citers already cite them without it.

2. **Causal broadcast and causal consistency.** ISIS and Birman's protocols; causal memory; a revival in the COPS era. The line carries its own controversy, the 1993 CATOCS critique by Cheriton and Skeen — which cites the seed and gathered 211 citations of its own.

3. **State machine replication and consensus.** Schneider's 1990 tutorial names the origin: "The state machine approach was first described in Lamport [1978a] for environments in which failures could not occur." Then Paxos (1998), PBFT, Raft, HotStuff and Tendermint, ZooKeeper and etcd. The passing remark became an industry.

4. **Mutual exclusion.** The illustration spawned a research line of its own, which matured into the textbooks and closed.

5. **Snapshots and global states.** Chandy–Lamport (1985). The Flink documentation today: "Flink uses a variant of the Chandy-Lamport algorithm known as asynchronous barrier snapshotting." A 1985 abstraction, running in production stream processors.

6. **Virtual time and parallel discrete-event simulation.** Jefferson (1985) and Time Warp; a field of its own, and one that left home early — 87.1% of its citers do not cite the seed, with a median year of 2003.

7. **Clock synchronization engineering.** Byzantine clock synchronization (1985), NTP. Here too, 87.5% cite without the seed; the 1978 theorem lies dormant in the very field it anticipated.

8. **Memory models and race detection.** The relation migrated into programming languages; Section 4 follows it there.

9. **Temporal networks.** The idea returned to physics; Section 4 follows that journey too.

10. **Databases and transactions.** The earliest wave; the ideas were absorbed so quickly that the branch dissolved into the background of the field.

Even at survey depth, one pattern is visible and will recur at close range in what follows: the theoretical lines kept citing the origin, while the engineering lines left home early — and, in time, stopped writing home altogether.

## 4 Migration and Transformation

Concepts do not travel unchanged. Following them across community borders, we can identify seven recurring transformations.

**Eponymization.** Already visible in the reception numbers: the concept acquired its maker's name exactly as it detached from his paper. Like the volt and the hertz, "Lamport clock" and "Lamport timestamp" honor a scientist whom most of their users could not cite — and, as noted above, neither term was coined by the paper, which says "logical clocks" and nothing more. The name travels on its own; the reference stays behind.

**Mutation of tense.** In the paper the relation is *happened-before*: events that had already occurred, somewhere else, once. In programming languages it became *happens-before*: a rule that must hold in every execution of a program. The Java memory model foundation paper (Manson, Pugh, and Adve, POPL 2005) cites the seed. The C++ memory-model paper (Boehm and Adve, PLDI 2008) does not. The Java Language Specification, SE 21, §17.4.5, defines "hb(x, y)" with no attribution anywhere in the chapter. In our contexts, happens-before now sits at parity with happened-before — 1,162 occurrences against 1,164 — with the crossover in the 2010s. The mutated tense marks the migration, from the description of a distributed computation to the specification of a programming language.

**The state-machine revival.** Reception caught up with the author's intent only after 2000, when Paxos and PBFT made fault-tolerant replication practical, and it was Schneider's tutorial that carried the attribution across the gap. The citers who read the 1978 paper as a state-machine paper are exactly the consensus lineage — Paxos, PBFT, Zyzzyva, HotStuff, Tendermint — and they cite the seed and the tutorial together, as a pair. The paper had to wait 22 years for the reader it was written for.

**The physics round-trip.** Reception shed the relativity framing almost immediately, as Section 2 showed. Decades later the idea re-entered physics through a single gateway, Holme and Saramäki's *Temporal networks* (2012), which credits: "the vector [φ...] is called i's vector clock. This framework was introduced by Lamport [90] and further developed by Mattern [104]" — attributing to Lamport the vector construction that belongs to Fidge and Mattern. Of the gateway's 2,654 citers, 99.8% do not cite the seed, and the physics citers in our corpus concentrate in the 2010s. An idea born from special relativity returned to physics carrying the wrong birth certificate.

**Canon substitution.** The intermediaries replace the origin. Of Schneider's citers, 74.8% do not cite the seed; of Paxos's, 78.9%; the median citing years are 2013–16. Hyperledger Fabric, ZooKeeper, and the blockchain surveys cite the canon without the seed. This is how a paper stops being read while its content spreads faster than ever: each generation cites the previous one, and the chain loses its first link. There is nothing improper in it — citing the nearest ancestor is exactly what good scholarly practice recommends. The forgetting is a property of the chain, not a fault of any author in it.

**Recombination.** Spanner (OSDI 2012) orders transactions by synchronized physical clocks with bounded uncertainty; its "external consistency" is exactly the problem the 1978 paper posed with the Strong Clock Condition and the telephone call. Spanner cites 37 works, and the seed is not among them; if there is descent here, it runs through the clock-synchronization engineering literature. Hybrid Logical Clocks (2014), by contrast, cite the seed and set out to fuse the paper's two halves, logical and physical clocks — the two halves that reception had kept apart for decades, reunited by engineering need.

**Dormancy.** And the declared contribution? Among the 5,818 context-bearing citers, 190 use clock-synchronization vocabulary at all, and 19 mention the bound, the drift, or the theorem. Dormant is not quite dead — the concerns of the second half kept resurfacing, as Spanner's engineering shows — but the theorem itself sleeps. The one result the paper believed new is the one part of it that was never taken up.

## 5 The Lost Citation Chain

Languages are full of words whose etymology no speaker carries — we all say "goodbye" without thinking of "God be with ye" — and the words work anyway. Something similar happens at the far ends of this genealogy, and it is worth walking out to the endpoints to see it.

The Java Language Specification is the cleanest case. A language specification consulted by millions of programmers defines "hb(x, y)" — the seed's relation, in mutated tense — and the chapter contains no attribution to anything. This is not carelessness by one author; it is the normal condition of specifications, which state rules rather than histories. The race-detection community shows the mechanism in miniature: FastTrack (PLDI 2009), a canonical paper, cites the seed; the community's leaf tools — Goldilocks, RoadRunner, DPOR — cite Mattern without it. Memory here is two-tiered: the canon remembers, the leaves forget. The physics gateway of Section 4 is the extreme case — a single hop crossed a discipline and lost the ancestor, misattribution included. And Spanner runs a production answer to the paper's second-half problem, under the paper's own problem statement in different words, with a bibliography of 37 entries that does not reach it.

Genealogy also needs boundary discipline, because not every absence is a lost chain. Winskel's event structures (1986) cite the seed: the true-concurrency tradition has documented contact with this lineage, not a broken link. And Bitcoin's longest-chain ordering shares none of this lineage's apparatus; that is a non-case, not an absorption. The genealogist must resist the temptation to find the ancestor everywhere. The claim here is narrower, and better documented: where the concepts demonstrably descend from the seed, the citation usually does not follow them all the way down.

## 6 Convergence, Fusion, and Reinterpretation

Lineages do not only branch; they collide, merge, and quarrel. The causal-systems line had its quarrel in public: the 1993 CATOCS critique, Cheriton and Skeen's argument against causally and totally ordered communication, sits inside the citation graph itself, the critique citing the very seed whose descendants it attacked. Whichever side one takes, the point for the genealogist is that the dispute is traceable: the graph preserves the arguments as well as the doctrine. A genealogy that showed only reverence would not be credible; this one records its disputes.

The most consequential event is a fusion. The seed's total order, Schneider's fault-tolerance framing, and Paxos's algorithm merged into a single canon — state machine replication as one composite idea, with the joints no longer visible. No one who deploys a replicated log today needs to know which of the three parts came from where. The blockchain era consumes this canon as infrastructure, the way a building consumes electricity, and cites accordingly: the canon, not the origin. Hybrid Logical Clocks perform the complementary fusion, reuniting the paper's own two halves that reception had split apart.

By 2013 the fused legacy had a name and a prize. The Turing Award citation — we quote the wording as reproduced by Wikipedia from the ACM text — credits "the invention of concepts such as causality and logical clocks, safety and liveness, replicated state machines, and sequential consistency." Causality and logical clocks; replicated state machines. The preamble and the aside, side by side at the head of the list. The theorem is not mentioned.

## 7 Decline, Survival, or Canonization

Citation curves normally rise, peak, and fade. This one rose and stayed: in 48 years there is no decline on record, with the plateau near 300 citations per year through 2000–2019 and still around 200 per year today. Formal canonization traced the same arc: the first PODC Influential Paper Award in 2000 (the award was later renamed the Dijkstra Prize), the SIGOPS Hall of Fame in 2007, the Turing Award in 2013, the anthology reprint in the ACM Books series in 2019. The theory community, the systems community, and the field at large each canonized the paper in their own house.

But canonization does not preserve a paper whole; it selects. Ranking the parts by their fates: happened-before is universal, at the price of a mutated tense; logical clocks survive under their maker's name rather than the paper's; vector clocks are the faithful heirs, citing and cited; the mutual-exclusion line closed honorably into the textbooks; the theorem is dormant; and the relativity framing is extinct in citation practice, alive only in retrospectives — including the author's own. Each part met a different kind of survival: as vocabulary, as eponym, as textbook material, as dormancy, or as memory. The paper was canonized as a whole; its parts were triaged.

## 8 The Intellectual Legacy

We can now state the inversion in full. The paper's parts met three fates, in reverse order of the paper's own emphasis. The definitional preamble — offered as something that "will appear quite natural" — became a universal concept, present in the working vocabulary of at least five communities. The generalization of the illustration, the state-machine passage presented in passing, became the consensus industry that underlies replicated databases and blockchains. The claimed novelty, the one result introduced with "we believe this theorem to be a new result," went dormant. Whatever a paper says about its own contributions, history reserves the right to re-rank them.

The transmission mechanism is the same in every branch, and we have named it two-tier memory. The canons remember: the Java memory model paper, FastTrack, Schneider, Holme and Saramäki, Hybrid Logical Clocks, and Winskel all cite the seed. The leaves forget: the Java Language Specification, C++11, the race-detection tools, the physics papers, the blockchain systems, and Spanner do not. Attribution survives in the layer that writes surveys and tutorials, and evaporates in the layer that ships software and defines standards. The eclipse also deepens with age: in Report 0's genealogy the intermediaries eclipse their seed at 22–54%; here the range runs from 24% to 99.8%.

There is a lesson here for anyone who measures science by citation counts. The counts see only the layer that remembers; the layer where the ideas do their daily work — specifications, production systems, another discipline's models — is invisible to them. By citation metrics alone, the deepest impact of this paper would be undetectable. Impact and attribution are correlated at the canon and decoupled at the leaves, and the decoupling grows with time.

One more observation, across genealogies rather than within one. RFC 677 fed both this lineage and Report 0's; Dynamo sits in both corpora; the causal-consistency line links them. The genealogies of a field are not separate trees but one interlocking structure, and tracing a second one begins to show the grain of the wood.

The closing fact is the simplest one. This paper has been cited some nine thousand times, and yet its deepest presences in the world — a relation in a language specification, a database's external consistency, a physics field's time-respecting paths — carry no citation at all. A concept has fully succeeded when it no longer needs its reference. The clock ran away from its maker. That, after all, is what good clocks do.

## Provenance note

This essay is built on 23 ledger claims, of which 22 are verified and 1 remains open — the ten-branch synthesis, held at survey depth. Confidence grades: 9 documented, 14 strong. The standing hedges, restated: branch membership was assigned from metadata, so branch counts and boundaries are indicative; the citation-context data (S2) is a cap-truncated sample, so context percentages are portraits, not measurements; and the Turing Award wording is taken from Wikipedia's quotation of the ACM citation.

Intellectual Genealogies · An intellectual genealogy follows ideas through history, not just papers through a citation network