- Atlas
- Computer Science
- Distributed Algorithms
Distributed Algorithms
Distributed algorithms are procedures carried out by several computers that can each act only on local information and can communicate only by sending messages or reading shared memory.
14 frameworks, from 1965 to today · Algorithms · Computer Science
- Shared-Memory Mutual Exclusion and Synchronization 1965-Present
- Message-Passing Coordination Protocols 1975-1995
- Logical Time and Causal Ordering 1978-Present
- Distributed Complexity and Communication Lower Bounds 1980-Present
- Byzantine Fault Tolerance 1982-Present
- Consensus 1983-Present
- Randomization and Probabilistic Distributed Computing 1983-Present
- Impossibility and Computability Theory of Distributed Systems 1985-Present
- Locality and Distributed Network Algorithms 1987-Present
- Failure Detectors and Partial Synchrony Models 1988-Present
- State machine replication 1988-Present
- CAP and Consistency-Availability Trade-off Frameworks 2000-Present
- Consistency model 2000-Present
- Permissionless and Blockchain Consensus 2008-Present
Overview
Distributed algorithms are procedures carried out by several computers that can each act only on local information and can communicate only by sending messages or reading shared memory. Nobody has a global view; each participant sees a fragment, and the system must still behave as a coherent whole. This is the field's central difficulty and its central subject. A single machine can inspect its entire state before deciding; a distributed system cannot, and yet we ask it to agree, to order events, to tolerate failures, and to keep working while parts of it break or vanish. The history of the field is the history of discovering what such systems can and cannot do, and of building the abstractions—clocks, quorums, replication protocols—that make the possible part practical.
Shared Memory and the Birth of Mutual Exclusion
The field's earliest problem came from hardware. In the 1960s, operating systems and multiprocessors had several processors reading and writing a common memory, and programs needed to keep two of them from entering a critical section—a stretch of code that must run alone—at the same time. Edsger Dijkstra posed the mutual exclusion problem in 1965 and published a solution using only atomic reads and writes of shared variables. The problem was subtle because a correct solution had to guarantee three things at once: at most one process in the critical section, eventual entry for every process that wants it, and no process blocked by one that has halted outside the section.
Dijkstra's algorithm and the refinements that followed (Peterson's 1981 two-process algorithm is the compact classic) established a style of reasoning that became the field's signature: prove safety (nothing bad happens) and liveness (something good eventually happens) separately, and assume the worst about timing. Leslie Lamport's 1974 "bakery algorithm" gave a mutual-exclusion protocol in which processes take numbered tickets, like customers at a bakery, without any central dispenser. The deeper lesson came from impossibility results. In the late 1980s, work by Michael Fischer, Nancy Lynch, and Michael Paterson, and separately by others, showed that even agreement among two processes is impossible with shared memory if processes can crash and the system is fully asynchronous—no bound on relative speeds. This "FLP" result (1985) reframed the field: perfect agreement in the worst case is not a matter of cleverness but of mathematics.
Message Passing and the Ordering of Events
Meanwhile, computers were being wired into networks, and communication happened by messages with unpredictable delays. Lamport's 1978 paper "Time, Clocks, and the Ordering of Events in a Distributed System" supplied the conceptual foundation. Physical clocks cannot be perfectly synchronized, so Lamport defined a logical clock: a counter each process advances on events and attaches to messages, giving a partial order—"happened before"—that captures causality without real time. The paper also introduced the distributed-state snapshot idea and the notion of a distributed system as one in which message delay is unpredictable. Logical time made it possible to reason about concurrent histories, and it underlies vector clocks, used later to detect causal relationships and conflicts.
The 1970s and 1980s also produced the message-passing algorithms that became teaching standards: the "bully" and "ring" leader-election algorithms, in which processes choose a coordinator; distributed termination detection; and routing and spanning-tree construction on networks. These were the field's craft period—many small protocols, each solving a concrete coordination problem.
Consensus, Impossibility, and the Cost of Failure
The agreement problem crystallized as consensus: processes each propose a value, and all must decide the same one, with validity (the decided value was proposed) and termination1. The FLP impossibility result showed that in a fully asynchronous system with even one crash failure, no deterministic consensus algorithm can guarantee termination. The result did not end the field; it defined its terrain. Researchers asked what extra assumptions restore solvability. One answer was randomization: Ben-Or's 1983 algorithm and Rabin's work showed that with random choices, consensus terminates with probability one. Another was failure detection: Chandra and Toueg's 1996 framework classified failure detectors by completeness and accuracy, and showed which classes make consensus solvable—an "eventually perfect" detector suffices. A third was synchrony: with bounds on message delay, consensus is straightforward.
A parallel line of theory, complexity of distributed computation, asked how many messages and rounds a task requires. The 1980s and 1990s produced lower bounds for leader election, broadcast, and consensus, and the notion of round complexity. This is where distributed algorithms connects to the broader algorithmic tradition: the resource being counted is communication, not time on one machine.
Replicated State Machines and Practical Agreement
Theory met practice through state-machine replication2. The idea, articulated by Lamport and others in the late 1970s and 1980s, is that if several replicas start in the same state and execute the same commands in the same order, they stay identical; a failed replica can be replaced and caught up. The hard part is agreeing on the order. Lamport's Paxos, circulated in the late 1980s and published in 1998, became the canonical practical protocol: a leader proposes values, a quorum of acceptors must agree, and safety holds even through leader changes and crashes. Paxos is famously subtle; its later popularization by Google's Chubby system and by the Raft protocol (2014), designed for understandability, made replicated agreement a standard building block of databases and cloud infrastructure.
The practical protocols also forced the field to confront partial synchrony: systems that are asynchronous most of the time but eventually behave with bounds. This model, formalized by Dwork, Lynch, and Stockmeyer in 1988, is where real systems live, and it is why Paxos can be both safe always and live eventually.
Randomization and the Probabilistic Turn
Randomization entered at several points. Beyond breaking FLP, it powered randomized consensus and randomized leader election, and it became central to distributed hash tables and gossip protocols, in which nodes exchange information with random peers and converge on a common view with high probability. The 1980s and 1990s saw randomized algorithms for symmetry breaking, load balancing, and network decomposition. The theme is consistent: randomness buys progress where determinism is blocked, at the price of probabilistic guarantees.
Locality, Networks, and the Shape of Distributed Computation
A distinct tradition studied computation where the network itself is the object: each node knows only its neighbors, and the question is how many rounds of local communication are needed to compute a global function. This locality or distributed network model, developed from the late 1980s onward (with foundational work by Linial and later by Naor and Stockmeyer), produced the field of local algorithms: coloring, maximal independent set, and matching computed in a constant or logarithmic number of rounds. The model's importance is conceptual—it isolates the cost of information propagation from the cost of computation—and it connects distributed algorithms to graph theory and to the study of networks as computational objects.
CAP, Consistency, and the Trade-off Frameworks
As distributed databases spread in the 1990s and 2000s, practitioners needed a vocabulary for the tension between keeping replicas consistent and staying available when the network partitions. Eric Brewer's CAP conjecture (2000) and its formalization by Gilbert and Lynch (2002) stated that a distributed system cannot simultaneously guarantee consistency, availability, and partition tolerance3. The theorem is often misread; its real content is that during a partition you must choose3. The framework, together with the later PACELC refinement (if there is a partition, choose availability or consistency; else choose latency or consistency), shaped how engineers reason about replication34. It also provoked a countercurrent: the "NewSQL" and strongly consistent systems of the 2010s argued that the trade-off is narrower than the slogan suggests, and that careful protocols can offer strong guarantees at acceptable cost.
Permissionless and Byzantine Consensus
Classical consensus assumed known participants and crash failures. Byzantine fault tolerance, introduced by Lamport, Shostak, and Pease in 1982, assumed participants could lie or send conflicting messages, and showed that agreement requires more than two-thirds of participants to be honest. For decades this was theory with few deployments. Then Bitcoin (2008) introduced permissionless consensus: an open network with no membership list, where participants ("miners") compete to extend a chain of blocks, and the longest chain wins by proof of work. The protocol, analyzed by Garay, Kiayias, and Leonardos in 2015, achieves agreement with high probability under assumptions about hashing power and network delay. This reopened the field: how do you do consensus when anyone can join, identities are free, and adversaries can create many fake participants (the Sybil problem)? Proof of stake, Byzantine fault-tolerant consensus in open networks, and the study of blockchain protocols became a major research area in the 2010s and 2020s, connecting distributed algorithms to cryptography and economics.
The Present
Today the field spans several living traditions. Shared-memory synchronization remains foundational, now studied through the lens of linearizability and memory models. Consensus theory continues, with work on Byzantine agreement, flexible quorums, and protocols that tolerate partial synchrony. Replicated state machines are the backbone of cloud databases and coordination services. Local and network algorithms remain an active theoretical area, increasingly tied to dynamic and fault-tolerant settings. Permissionless consensus and blockchain protocols are among the fastest-moving fronts, raising open questions about scalability, energy, formal verification, and the boundary between probabilistic and deterministic guarantees. The oldest questions—what can be computed without a global view, and at what cost—are still the ones being asked.
References
- Distributed algorithm (Standard problems), Wikipedia
- Paxos (computer science), Wikipedia
- CAP theorem (introduction, History), Wikipedia
- PACELC design principle, Wikipedia
The frameworks of Distributed Algorithms
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1975-1995
Message-Passing Coordination Protocols
How do processes coordinate by sending messages?
- 1978-Present
Logical Time and Causal Ordering
How can we order events without a global clock?
- 1980-Present
Distributed Complexity and Communication Lower Bounds
How much communication does a distributed task require?
- 1982-Present
Byzantine Fault Tolerance
How can systems agree when some participants lie?
- 1983-Present
- 1983-Present
Randomization and Probabilistic Distributed Computing
How can randomness help solve distributed problems?
- 1985-Present
Impossibility and Computability Theory of Distributed Systems
What distributed problems are impossible to solve?
- 1987-Present
Locality and Distributed Network Algorithms
How many rounds does a local computation need?
- 1988-Present
Failure Detectors and Partial Synchrony Models
What failure assumptions make agreement possible?
- 1988-Present
State machine replication
How can replicas stay identical despite failures?
- 2000-Present
CAP and Consistency-Availability Trade-off Frameworks
What trade-offs arise between consistency and availability?
- 2000-Present
- 2008-Present
Permissionless and Blockchain Consensus
How can open networks agree without trusted participants?
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Logical Time and Causal Ordering influenced by Message-Passing Coordination Protocols
Lamport's logical clocks paper grew out of message-passing systems with unpredictable delays, providing the happened-before relation that made causal ordering precise.
Carried by Leslie Lamport; Time, Clocks, and the Ordering of Events in a Distributed System (1978).
Permissionless and Blockchain Consensus influenced by Byzantine Fault Tolerance
Bitcoin's proof-of-work blockchain adapted Byzantine fault tolerance ideas to permissionless settings, using economic incentives and probabilistic guarantees to achieve agreement without known participants.
Carried by Satoshi Nakamoto.
Impossibility and Computability Theory of Distributed Systems influenced by Consensus
The FLP impossibility result for asynchronous consensus became the founding result of distributed computability theory, defining the terrain of solvable and unsolvable problems.
Carried by Michael Fischer; Nancy Lynch; Michael Paterson.
Failure Detectors and Partial Synchrony Models influenced by Consensus
Chandra and Toueg's failure detector framework was built to characterize which additional assumptions make consensus solvable in asynchronous systems.
Carried by Tushar Deepak Chandra; Sam Toueg.
State machine replication influenced by Consensus
State machine replication required a consensus protocol to agree on the order of commands; Paxos was developed as a practical consensus algorithm for replicated systems.
Carried by Leslie Lamport.
Message-Passing Coordination Protocols influenced by Shared-Memory Mutual Exclusion and Synchronization
The mutual exclusion problem and its safety/liveness proof style shaped early message-passing coordination protocols, which adapted the critical-section and leader-election problems to networks without shared memory.
Carried by Leslie Lamport.
Consensus grew out of Message-Passing Coordination Protocols
Consensus crystallized from message-passing agreement protocols and leader election, with the agreement problem formalized in the early 1980s.
Locality and Distributed Network Algorithms influenced by Distributed Complexity and Communication Lower Bounds
Distributed complexity's focus on communication and round lower bounds influenced the locality model, which isolates the cost of information propagation in networks.
Consensus influenced by Byzantine Fault Tolerance
Byzantine agreement work introduced adversarial failure models and agreement requirements that shaped the general consensus problem.
Carried by Leslie Lamport; Robert Shostak; Marshall Pease.
Randomization and Probabilistic Distributed Computing influenced by Consensus
Ben-Or's randomized consensus algorithm was developed as a response to the need for termination in asynchronous consensus, using randomization to bypass deterministic impossibility.
Carried by Michael Ben-Or.
Permissionless and Blockchain Consensus influenced by Consensus
Blockchain consensus protocols drew on classical consensus concepts such as quorums and agreement, adapting them to open, permissionless networks.
Permissionless and Blockchain Consensus influenced by Randomization and Probabilistic Distributed Computing
Proof-of-work blockchain consensus relies on randomization and probabilistic guarantees, extending the probabilistic turn in distributed computing to permissionless agreement.
Failure Detectors and Partial Synchrony Models influenced by Impossibility and Computability Theory of Distributed Systems
The FLP impossibility result motivated the search for partial synchrony and failure detectors as ways to circumvent the impossibility of deterministic asynchronous consensus.
Carried by Michael Fischer; Nancy Lynch; Michael Paterson.
State machine replication influenced by Failure Detectors and Partial Synchrony Models
The partial synchrony model, formalized by Dwork, Lynch, and Stockmeyer, provided the timing assumptions under which practical replicated state machine protocols like Paxos could be both safe and live.
Carried by Cynthia Dwork; Nancy Lynch; Larry Stockmeyer.
CAP and Consistency-Availability Trade-off Frameworks influenced by State machine replication
Practical experience with replicated state machines and distributed databases motivated Brewer's CAP conjecture about consistency, availability, and partition tolerance.
Carried by Eric Brewer.
Locality and Distributed Network Algorithms influenced by Message-Passing Coordination Protocols
Early message-passing algorithms for leader election and spanning-tree construction on networks provided the problem setting for the later study of locality and local algorithms.
Distributed Complexity and Communication Lower Bounds influenced by Logical Time and Causal Ordering
Logical time and causal ordering provided concepts used in early distributed complexity analyses, such as reasoning about message chains and round complexity.
CAP and Consistency-Availability Trade-off Frameworks influenced by Consensus
CAP formalized a trade-off in replicated systems that rely on consensus protocols, framing the choice between consistency and availability during partitions.
Carried by Eric Brewer.
Beyond the field
Where Distributed Algorithms's ideas came from in other fields, and what they led to there: the strongest 12 of 64 links.
Message-Passing Coordination Protocols influenced Cooperative Teamwork and Distributed Constraint Reasoning in Multiagent Systems
Distributed constraint reasoning and cooperative teamwork frameworks adopted message-passing coordination protocols from distributed algorithms, building contract-net-style and constraint-propagation schemes on that base.
Byzantine Fault Tolerance grew out of Fault-Tolerant Computing in Reliability Fault Tolerance
Byzantine fault tolerance grew directly out of fault-tolerant computing: the Lamport-Shostak-Pease problem generalized earlier work on reliable systems from benign crash failures to arbitrary (Byzantine) failures.
Carried by Leslie Lamport; Robert Shostak; Marshall Pease.
Byzantine Fault Tolerance influenced Software Fault Tolerance at Internet Scale in Reliability Fault Tolerance
Internet-scale fault tolerance adopted Byzantine fault tolerance as its model for handling faulty or malicious nodes, using results such as PBFT and the Lamport-Shostak-Pease bounds. The later systems apply BFT protocols directly.
Carried by Leslie Lamport; Miguel Castro; Barbara Liskov.
Consensus influenced State machine replication in Reliability Fault Tolerance
State machine replication depends on consensus to agree on the order of client commands, and its formulation built directly on the consensus problem defined by Lamport, Shostak and Pease and later solved by Paxos. The replication scheme is defined in terms of a consensus protocol.
Carried by Leslie Lamport; Fred B. Schneider.
Consensus influenced Consensus-Based Replicated State in Distributed Databases
Consensus-based replicated state uses consensus algorithms such as Paxos to agree on the order of operations. Consensus theory provided the agreement primitive on which the replicated state is built.
Carried by Leslie Lamport.
Randomization and Probabilistic Distributed Computing influenced by Probabilistic method and derandomization in Randomized Algorithms
The probabilistic method, developed by Erdős and others from the 1940s, supplied the existence arguments and random-choice techniques that randomized distributed algorithms later adapted to break symmetry and bound expected time. The 1983 randomized consensus and symmetry-breaking work drew directly on these combinatorial tools.
State machine replication grew out of Replication and Consensus in Distributed Systems
Replication and consensus, including the replicated-state-machine approach to fault-tolerant agreement, is the direct source of state machine replication as a named framework. The later formulation generalized the replicated state machine into a general deterministic-service replication method.
Carried by Leslie Lamport; Fred Schneider.
State machine replication led to Consensus-Based Replicated State in Distributed Databases
Consensus-based replicated state is the practical realization of state machine replication, using a consensus protocol to order client commands. The state machine replication model supplied the correctness argument for the approach.
Carried by Leslie Lamport.
CAP and Consistency-Availability Trade-off Frameworks influenced by Distributed databases and CAP in Databases
Distributed databases and their replication and partition problems provided the concrete systems and trade-offs that the CAP theorem formalized. Brewer's conjecture and Gilbert and Lynch's proof were framed directly against distributed database designs.
Carried by Eric Brewer; Seth Gilbert; Nancy Lynch.
Permissionless and Blockchain Consensus led to Proof of stake in Blockchain Crypto Finance
Proof of stake was proposed as an alternative consensus mechanism within the same permissionless blockchain setting, replacing proof-of-work's computational competition with stake-based block production while keeping the longest-chain and fork-choice framework.
Carried by Sunny King; Scott Nadal; Peercoin.
Permissionless and Blockchain Consensus influenced by Replication and Consensus in Distributed Systems
Nakamoto's Bitcoin consensus adapted the classical replication-and-consensus problem to an open network, replacing known participants with proof-of-work to reach agreement.
Carried by Satoshi Nakamoto.
Shared-Memory Mutual Exclusion and Synchronization influenced Cache Coherence and Memory Consistency in Memory Hierarchy
Shared-memory mutual exclusion and synchronization supplied the atomic read-modify-write and synchronization primitives that cache-coherence protocols rely on. The coherence work took these primitives and the shared-memory model from the synchronization literature.

Distributed Algorithms is a planet in Nousfarer
Its city has a tower for each of these 14 frameworks. Land, walk in, and climb one concept at a time.
Land on Distributed AlgorithmsRelated fields
Fields its ideas are linked to
- Distributed Systems 12 links
- Distributed Databases 11 links
- Randomized Algorithms 10 links
- Reliability Fault Tolerance 7 links
- Memory Hierarchy 3 links
- Instruction Set Architecture 2 links
- Blockchain Crypto Finance 2 links
- Network Protocols 2 links
- Computer Systems 2 links
- Complexity Theory 2 links
- Multiagent Systems 1 link
- Algorithms 1 link
More in Algorithms
- Algorithms
- Approximation Algorithms
- Computational Geometry
- Data Structures
- Graph Algorithms
- Online Algorithms
- Parallel Algorithms
- Parameterized Algorithms
- Randomized Algorithms
- Streaming Algorithms
- String Algorithms
See where Distributed Algorithms sits on the Map of Human Knowledge