proomt

Search

Search posts, papers, and topics

Hall of Fame

Hall of FameLeslie Lamport197836 min readpaperadvanced

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

Read on azurewebsites.netHN 20·2 comments

Summary

Lamport's paper defines the "happened before" partial ordering of events in a distributed system. It introduces logical clocks and an algorithm to extend this to a consistent total ordering, which can be used to solve synchronization problems.

  • The "happened before" relation (a -> b) defines a partial ordering of events in a distributed system.
  • Two events are concurrent if neither can causally affect the other (a -/-> b and b -/-> a).
  • Logical clocks assign numbers to events, satisfying C1 (events in a process are ordered) and C2 (message send < message receipt).
  • These logical clocks provide a consistent total ordering of events, useful for distributed synchronization.

This foundational paper is essential for anyone designing or debugging distributed systems, as it clarifies the fundamental challenges of event ordering and provides a robust framework for reasoning about time.

10/10
distributed systemsconcurrencyalgorithmstheoryclock synchronizationlamport clocks

Related reading

  1. Paxos Made Simple

    Lamport’s “Paxos Made Simple” formalizes the classic Paxos consensus algorithm, detailing its two‑phase prepare/accept protocol and the invariants that guarantee safety under an asynchronous crash‑failure model. It shows how majority quorums, monotonically increasing proposal numbers, and persistent acceptor state ensure a single value is chosen and learned.

    Hall of Fameazurewebsites.net20 minpaperHN657

  3. A Note on Distributed Computing

    The paper argues that treating remote objects the same as local ones is fundamentally flawed because distributed systems introduce latency, partial failures, and different memory semantics. It outlines a three‑phase development approach that acknowledges distribution concerns early rather than hiding them.

    Hall of Famearchive.org38 minpaper

  4. Metastable Failures in Distributed Systems

    This paper introduces and formalizes "metastable failures" in distributed systems, a class of outages where a trigger pushes a system into a bad state that persists due to a sustaining effect, even after the trigger is removed. These failures often stem from features designed for efficiency or reliability and require significant external intervention to resolve.

    Hall of Famesigops.org25 minpaperHN16112

  5. Impossibility of Distributed Consensus with One Faulty Process

    The FLP paper proves that in an asynchronous distributed system, it's impossible to reach consensus if even one process can crash, assuming no synchronized clocks or reliable failure detection. This fundamental impossibility result means any practical consensus protocol must relax one of these assumptions.

    Hall of Famemit.edu20 minpaperHN164

  6. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging

    ARIES is a transaction recovery method using write-ahead logging (WAL) that supports fine-granularity locking and partial rollbacks. It introduces the "repeating history" paradigm to redo all missing updates before performing rollbacks of loser transactions during system restart, using Log Sequence Numbers (LSNs) on pages.

    Hall of Famestanford.edu155 minpaper