Time, clocks, and the ordering of events in a distributed system
1978/07/01 by Leslie Lamport · 129 citations
Computer Science · #Distributed systems and fault tolerance #Parallel Computing and Optimization Techniques #Cellular Automata and Applications
paper · pdf · doi:10.1145/359545.359563
Abstract
The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events. The use of the total ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become.
Cited by
- Collaborative Text Editing with Eg-walker: Better, Faster, Smaller
- Perspectives on the CAP Theorem
- Consensus in the presence of partial synchrony
- Multiparty Asynchronous Session Types
- Poet: Target-System Independent Visualizations of Complex Distributed-Application Executions
- Internet time synchronization: the network time protocol
- Taurus Database: How to be Fast, Available, and Frugal in the Cloud
- Enabling Multi-Dimensional Distributed Trace Comparison with Contrast
- Building Trust in Autonomous Commerce: A Verifiable Global Event Timeline and AI-Ready Fraud Intelligence Layer
- Making Democracy Work: Fixing and Simplifying Egalitarian Paxos (Extended Version)
- FireLedger: A High Throughput Blockchain Consensus Protocol
- Beyond Per-Thread Lock Sets: Multi-Thread Critical Sections and Dynamic Deadlock Prediction
- Approaches to Conflict-free Replicated Data Types
- Tracing the Man in the Middle in Monoidal Categories
- Vector Clocks in Coq: An Experience Report
- Probing the Planck scale with quantum computation
- Buzz: An Extensible Programming Language for Self-Organizing Heterogeneous Robot Swarms
- When Coordination Is Avoidable: A Monotonicity Analysis of Organizational Tasks
- Fast Deterministically Safe Proof-of-Work Consensus
- The hands of time: Moving my body to keep time order in the brain
- Reputation-Based Leader Election under Partial Synchrony: Towards a Protocol-Independent Abstraction with Enhanced Guarantees
- Temporal Windows of Integration for Multisensory Wireless Systems as Enablers of Physical AI
- Flexible Paxos: Quorum intersection revisited
- On the Impact of the Communication Model on Realisability
- Compiling Away the Overhead of Race Detection
- Efficient, Near Complete and Often Sound Hybrid Dynamic Data Race Prediction (extended version)
- ClockTalk software associated with arXiv:2512.01764
- ACIA, not ACID: Conditions, Properties and Challenges
- Impact of Data-Oriented and Object-Oriented Design on Performance and Cache Utilization with Artificial Intelligence Algorithms in Multi-Threaded CPUs
- Formal Specification for Fast ACS: Low-Latency File-Based Ordered Message Delivery at Scale
- LaForge: Always-Correct and Fast Incremental Builds from Simple\n Specifications
- Telex: Principled System Support for Write-Sharing in Collaborative Applications
- Quantifying and Generalizing the CAP Theorem
- Efficient Two-Layered Monitor for Partially Synchronous Distributed Systems (Technical Report)
- YTrace: End-to-end Performance Diagnosis in Large Cloud and Content Providers
- Early Scheduling in Parallel State Machine Replication
- Event-based Program Analysis with DeWiz
- Large Language Models for Agentic NetOps and AIOps: Architectures, Evaluation, and Safety
- On Synchronous and Asynchronous Interaction in Distributed Systems
- Symmetric and Asymmetric Asynchronous Interaction
- Disaggregation and the Application
- On Using Time Without Clocks via Zigzag Causality
- Set Consensus: Captured by a Set of Runs with Ramifications
- Thespis: Actor-Based Middleware for Causal Consistency
- AT2: Asynchronous Trustworthy Transfers
- Efficient Deterministic Replay Using Complete Race Detection
- Designing a commutative replicated data type
- Best-effort Group Service in Dynamic Networks
- System Description for a Scalable, Fault-Tolerant, Distributed Garbage Collector
- Axiomatisation for an asynchronous epistemic logic with sending and receiving messages
- Time Warp on the Go
- Lightweight Asynchronous Snapshots for Distributed Dataflows
- CausalSpartanX: Causal Consistency and Non-Blocking Read-Only Transactions
- Quanta: a Language for Modeling and Manipulating Information Structures
- KompicsTesting - Unit Testing Event Streams
- Checking Behavioral Consistency Constraints for Pervasive Context in Asynchronous Environments
- Preserving Stabilization while Practically Bounding State Space
- Arbitration-Free Consistency is Available (and Vice Versa)
- Subject-Event Ontology Without Global Time: Foundations and Execution Semantics
- Automated Dynamic Concurrency Analysis for Go
- Causal Coverage in Ordered Locales and Spacetimes
- Specification and Verification for Climate Modeling: Formalization Leading to Impactful Tooling
- Beyond Lamport, Towards Probabilistic Fair Ordering
- Fair Kernel-Lock-Free Claim/Release Protocol for Shared Object Access in Cooperatively Scheduled Runtimes
- Fifty Years of Transaction Processing Research (extended)
- Light Cone Consistency: Closure, Ordering, and the Single-Observer Boundary
- Efficient Synchronous Byzantine Consensus
- An Operational Semantic Basis for OpenMP Race Analysis
- Efficient Replication via Timestamp Stability (Extended Version)
- Decoupling Correctness from Policy: A Deterministic Causal Structure for Multi-Agent Systems
- A Time-Bound Signature Scheme for Blockchains
- Execution replay and debugging
- Non-intrusive on-the-fly data race detection using execution replay
- Assertion checker for the C programming language based on computations over event traces
- Mastering Concurrent Computing Through Sequential Thinking: A Half-century Evolution
- ESBT: A Scalable and Deterministic Sequence CRDT for Distributed Collaborative Editing
- Auditing Emergent LLM-Agent Collaboration through Cooperation-Obligation Coupling
- A transformer-based multi-feature fusion method for detecting traffic events using Twitter data
- Gracefully Degrading Consensus and k-Set Agreement in Directed Dynamic\n Networks
- Network Hardware-Accelerated Consensus
- Automated Synthesis of Distributed Controllers
- Que Sera Consensus: Simple Asynchronous Agreement with Private Coins and\n Threshold Logical Clocks
- Angelfish: Consensus with Optimal Throughput and Latency Across the Leader-DAG Spectrum
- Substrate-Timing-Independence for Meta-State Stability of Distributed Robotic Swarms
- Automated Modular Verification for Race-Free Channels with Implicit and Explicit Synchronization
- A Concurrency Problem with Exponential DPLL(T) Proofs
- A Uniqueness Theorem for Distributed Computation under Physical Constraint
- Creek: Low-latency, Mixed-Consistency Transactional Replication Scheme
- Maintaining Consistency of Data on the Web
- Formalizing and Implementing Distributed Ledger Objects
- Reconfigurable State Machine Replication from Non-Reconfigurable Building Blocks
- Merlin: A Language for Provisioning Network Resources
- Revisiting Optimal Resilience of Fast Byzantine Consensus (Extended\n Version)
- CausalMesh: A Formally Verified Causal Cache for Stateful Serverless Computing
- Ring Paxos: High-Throughput Atomic Broadcast
- A Unified Theory of Shared Memory Consistency
- The Performance of Paxos and Fast Paxos
- Abstract unordered and ordered trees CRDT
- Time, Fences and the Ordering of Events in TSO
- Network-Agnostic State Machine Replication
- Necessary and Sufficient Conditions on Partial Orders for Modeling\n Concurrent Computations
- Consistency in Non-Transactional Distributed Storage Systems
- Update Consistency for Wait-free Concurrent Objects
- Graffiti: Enabling an Ecosystem of Personalized and Interoperable Social Applications
- Consistent Updates for Scalable Microservices
- Predicting All Data Race Pairs for a Specific Schedule (extended version)
- Verifying PRAM Consistency over Read/Write Traces of Data Replicas
- Global Stabilization for Causally Consistent Partial Replication
- Enabling functional neural circuit simulations with distributed computing of neuromodulated plasticity. [europepmc]
- HT-Paxos: high throughput state-machine replication protocol for large clustered data centers. [europepmc]
- Data Collection for Mobile Group Consumption: An Asynchronous Distributed Approach. [europepmc]
- Reconciling fault-tolerant distributed algorithms and real-time computing. [europepmc]
- A Robust Approach to TDMA Synchronization in Aerial Networks. [europepmc]
- Pathways to cellular supremacy in biocomputing. [europepmc]
- Para 2 : parameterized path reduction, acceleration, and SMT for reachability in threshold-guarded distributed algorithms. [europepmc]
- From Microbial Communities to Distributed Computing Systems. [europepmc]
- Characterization, Statistical Analysis and Method Selection in the Two-Clocks Synchronization Problem for Pairwise Interconnected Sensors. [europepmc]
- Toward Formal Models and Languages for Verifiable Multi-Robot Systems. [europepmc]
- On Grid Quorums for Erasure Coded Data. [europepmc]
- DSSM: Distributed Streaming Data Sharing Manager. [europepmc]
- Pay attention and you won't lose it: a deep learning approach to sequence imputation. [europepmc]
- Mandrake: multiagent systems as a basis for programming fault-tolerant decentralized applications. [europepmc]
- Toward Trusted IoT by General Proof-of-Work. [europepmc]
- Landauer Principle and Einstein Synchronization of Clocks: Ramsey Approach. [europepmc]
- A Resource Usage Efficient Distributed Allocation Algorithm for 5G Service Function Chains [europepmc]
- Tutorial: Parameterized Verification with Byzantine Model Checker [europepmc]
- Resilient Distributed Collection Through Information Speed Thresholds [europepmc]
- Time-Fluid Field-Based Coordination [europepmc]
- Checking Robustness Between Weak Transactional Consistency Models [europepmc]
Related