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

still a working view ended · each leads to its entry below

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

  1. Distributed algorithm (Standard problems), Wikipedia
  2. Paxos (computer science), Wikipedia
  3. CAP theorem (introduction, History), Wikipedia
  4. 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.

  1. 1965-Present
  2. 1975-1995

    Message-Passing Coordination Protocols

    How do processes coordinate by sending messages?

    Fly to its tower in Nousfarer

  3. 1978-Present

    Logical Time and Causal Ordering

    How can we order events without a global clock?

    Fly to its tower in Nousfarer

  4. 1980-Present

    Distributed Complexity and Communication Lower Bounds

    How much communication does a distributed task require?

    Fly to its tower in Nousfarer

  5. 1982-Present

    Byzantine Fault Tolerance

    How can systems agree when some participants lie?

    Fly to its tower in Nousfarer

  6. 1983-Present

    Consensus

    How can processes all agree on a single value?

    Fly to its tower in Nousfarer

  7. 1983-Present
  8. 1985-Present
  9. 1987-Present
  10. 1988-Present
  11. 1988-Present

    State machine replication

    How can replicas stay identical despite failures?

    Fly to its tower in Nousfarer

  12. 2000-Present

    CAP and Consistency-Availability Trade-off Frameworks

    What trade-offs arise between consistency and availability?

    Fly to its tower in Nousfarer

  13. 2000-Present
  14. 2008-Present

    Permissionless and Blockchain Consensus

    How can open networks agree without trusted participants?

    Fly to its tower in Nousfarer

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.

Shared-Memory Mutual Exclusion and Sy…Message-Passing Coordination ProtocolsLogical Time and Causal OrderingDistributed Complexity and Communicat…Byzantine Fault ToleranceConsensusRandomization and Probabilistic Distr…Impossibility and Computability Theor…Locality and Distributed Network Algo…Failure Detectors and Partial Synchro…State machine replicationCAP and Consistency-Availability Trad…Consistency modelPermissionless and Blockchain Consens…

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.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

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 Algorithms

Related fields

Fields its ideas are linked to

More in Algorithms

See where Distributed Algorithms sits on the Map of Human Knowledge