Time, Clocks, and the Ordering of Events in a Distributed System
Communications of the ACM, 1978 · paper · Computer science
Examines the "happened before" relation among events in a distributed system, showing it gives only a partial ordering. It gives an algorithm for logical clocks that totally orders events, then adapts it to physical clocks and bounds how far they can drift apart.
Checked: PDF from lamport.azurewebsites.net, fetched 4 Oct 2026. Page numbers are those of that PDF.
0 findings
None that passed a second check.
2 minor (typos and the like; most checked by the judge only)
Wording The lower side of (11), "Cq(t1) + (t − t1) − κd(τ + ν) − dξ ≤ Ci(t)", omits the μ/(1−κ) term. Deriving it from (10) requires −κ(t − t1) ≥ −κ[d(τ + ν) + μ/(1 − κ)], as on the upper side.
- p. 8 Appendix, inequality (11)
Cq(tl) + (t - tl) - xd(r + p) - d~ -< Ci(t)
Judge's note: Checked against the page 8 crop. (10) gives a lower bound of Cq(t1) + (1−κ)(t−t1) − dξ, and the stated range is d(τ+ν) ≤ t−t1 ≤ d(τ+ν) + μ/(1−κ). Bounding −κ(t−t1) from below needs the upper end of that range, which gives −κ[d(τ+ν) + μ/(1−κ)]. The printed −κd(τ+ν) uses the lower end, which goes the wrong way. The upper side of (11) correctly carries the full term. The omission vanishes in the approximate inequality (12) and in the theorem's bound. It does matter for the later remark that (11) yields an exact upper bound on |Ci − Cj|.
Second check: another model agreed
Report a problem with this finding
Typo The message clock is defined as "Cm(t) = tm and Cm(t') = tm + μm" with a lowercase italic t_m. The later step "= Tm [by definition of Cm]" relies on Cm starting at the timestamp Tm.
- p. 7 Appendix, definition of C_m
C,~(t) = tm and Cm(t') = tm +/~m
- p. 7 Appendix, chain of inequalities
=Tm [by definition of Cm]
Judge's note: The page 7 crop shows a lowercase italic t_m in the definition, so this is not an extraction artefact. Tm (uppercase) is used in the preceding sentence, "message timestamped Tm", and in the chain of inequalities. Lowercase t_m is never defined. The evident fix is Cm(t) = Tm and Cm(t') = Tm + μm.
Second check: none (judge only)