Loading field map
Distributed algorithms are procedures designed to run on a collection of independent computing nodes that communicate only by passing messages over a network. Unlike a classical sequential algorithm, which assumes a single processor with direct access to a shared memory, a distributed algorithm must cope with the fact that no node has a complete, up-to-date picture of the global state. Each node acts on local information, and the system as a whole must still achieve a coherent outcome. The field studies what can be computed under these constraints, at what cost, and under what assumptions about the underlying network and the behavior of its components.
The central difficulty in distributed computing is that nodes must coordinate their actions despite lacking a shared clock, a shared memory, or a reliable communication medium. Three intertwined challenges define the field.
First, partial failure: any node may crash at any moment, and the rest of the system may not be able to distinguish a crashed node from one that is merely slow. This makes even simple tasks—like agreeing on a single value—surprisingly hard. Second, communication delay: messages take time to travel, and that time is unpredictable, so a node cannot know whether its latest message has been received before it acts on its own conclusions. Third, concurrency: nodes act simultaneously, so the order of events is not globally defined; two nodes may each believe they have completed the same task first, leading to inconsistent states.
These challenges are not engineering annoyances but fundamental limits. The most famous result in the field, the FLP impossibility theorem (named after its authors Fischer, Lynch, and Paterson, 1981), states that in an asynchronous system—where there is no bound on message delay or relative processing speed—no deterministic algorithm can guarantee that a group of nodes will reach consensus if even one node may crash. This is not a statement about a particular algorithm but about the very possibility of solving the problem. The result forced the field to distinguish carefully between different models of synchrony and to design algorithms that work under weaker guarantees, such as probabilistic termination or the assumption that only a minority of nodes fail.
Because the difficulty of a distributed problem depends so heavily on what the algorithm is allowed to assume, the field is organized around explicit models. The most important distinction is the synchrony model. In a synchronous system, nodes operate in lockstep rounds: in each round, every node sends messages, receives messages, and computes, and all messages sent in a round arrive before the next round begins. This model is clean and allows strong guarantees, but it is rarely realistic. In an asynchronous system, there is no bound on message delay or processing time; a message may take arbitrarily long to arrive, and a node may pause arbitrarily long between steps. Most real networks are asynchronous in this sense, but many algorithms are designed for the synchronous model because it is tractable and because results there often illuminate what is possible.
A middle ground is the partially synchronous model, which assumes that there is some bound on delay but that the bound is unknown to the algorithm. This model captures the intuition that real systems are not truly unbounded but also cannot rely on a known upper bound. Many practical consensus algorithms, such as Paxos and Raft, are designed for partial synchrony: they guarantee safety (no two nodes decide different values) under all conditions, but liveness (eventual progress) only after some unknown time when the system becomes synchronous.
Another key axis is the failure model. The simplest is crash failure: a node stops executing and never resumes. More severe is Byzantine failure, in which a node may behave arbitrarily—sending conflicting or malicious messages. Byzantine fault tolerance is much harder than crash tolerance and is relevant in settings where nodes may be compromised, such as blockchain systems. The number of failures an algorithm can tolerate is a central parameter; for crash failures, consensus is possible only if fewer than half the nodes fail, while for Byzantine failures, the bound is fewer than one-third.
Finally, the communication model matters. In the message-passing model, nodes communicate only by sending messages over point-to-point links. In the shared-memory model, nodes communicate by reading and writing to a common memory, which is an abstraction that simplifies reasoning but is rarely directly available in distributed systems. Most theoretical work uses message passing, but shared-memory abstractions are useful for reasoning about distributed data structures.
The field is not divided into rival schools but rather into complementary research programmes that address different aspects of the same underlying problem. Three traditions stand out.
This tradition asks: given a distributed problem, how many rounds of communication are necessary and sufficient to solve it? It treats the network as a graph, with nodes as vertices and communication links as edges, and studies the local complexity of problems—how far information must travel. A central concept is the locality of a problem: whether a node can decide its output based only on information within a constant number of hops, or whether it must learn about the entire network.
The classic example is the maximal independent set problem: given a graph, find a set of vertices no two of which are adjacent, such that every vertex not in the set has a neighbor in it. In a sequential setting, this is trivial. In a distributed setting, the question is how many rounds are needed. The celebrated result of Linial (1987) showed that on a cycle, a deterministic algorithm requires at least a logarithmic number of rounds, even though a randomized algorithm can do it in a constant expected number. This line of work has produced a rich theory of round complexity, with tight bounds for many problems, and has revealed a deep connection between distributed computation and the structure of the underlying graph.
This tradition focuses on the problem of agreement: how can nodes that may fail still reach a common decision? It grew out of the need to build reliable systems from unreliable components, and its central results are impossibility theorems and algorithms that work under minimal assumptions. The FLP theorem is the foundational negative result, but the tradition also produced positive results: algorithms like Paxos (Lamport, 1989) and Raft (Ongaro and Ousterhout, 2014) that are used in real distributed databases and coordination services. These algorithms are designed for the partially synchronous model and tolerate crash failures, and they are the backbone of modern replicated state machines, where a group of servers maintains a consistent log of operations.
The Byzantine variant of this tradition, initiated by the Byzantine Generals Problem (Lamport, Shostak, and Pease, 1982), asks how to achieve agreement when some nodes are actively malicious. This work has found new relevance in blockchain protocols, where the nodes are not trusted and the network is open. The practical algorithms in this tradition are often complex, and much of the research effort goes into proving their correctness under precise assumptions.
A third tradition studies how to implement abstract data structures—registers, queues, counters, snapshots—in a distributed setting. This work often uses the shared-memory model as an abstraction, even when the underlying system is message-passing, because it isolates the problem of coordination from the problem of communication. The central question is linearizability: whether the history of operations on a distributed object is equivalent to some sequential history that respects the real-time order of non-overlapping operations. This tradition has produced a deep theory of wait-free and lock-free algorithms, which guarantee that a node never waits indefinitely for another node to make progress, even if that other node crashes.
This tradition is closely related to the study of distributed transactions and replicated data types. A key concept is the conflict-free replicated data type (CRDT), a data structure that can be updated concurrently on multiple nodes and that automatically converges to a consistent state without requiring coordination. CRDTs are used in collaborative editing systems and distributed databases, and they represent a different design philosophy from consensus-based approaches: instead of forcing all nodes to agree on a single order of operations, they allow divergent histories that are guaranteed to merge.
These traditions are not competitors but rather different lenses on the same phenomena. The complexity-theoretic tradition assumes a reliable network and asks how fast a computation can be; the fault-tolerance tradition assumes failures and asks whether a computation is possible at all; the data-structure tradition assumes a shared abstraction and asks how to implement it efficiently. In practice, a real distributed system must address all three: it must tolerate failures, it must communicate efficiently, and it must present a coherent interface to its users.
The relationship between the traditions is also visible in the way results transfer. For example, the FLP impossibility theorem applies to the shared-memory model as well as to message passing, because the two models are equivalent under certain conditions. Similarly, lower bounds on round complexity in the synchronous model often imply lower bounds in weaker models, because a synchronous algorithm can be simulated in an asynchronous one. The field is unified by a common set of mathematical tools—graph theory, information theory, and the theory of automata—and by a shared commitment to proving guarantees rather than relying on empirical testing.
The field today is shaped by two forces: the maturation of its theoretical core and the pressure of new applications. On the theoretical side, the past decades have produced a fairly complete picture of the round complexity of many fundamental problems, and the focus has shifted to understanding the trade-offs between time, message complexity, and failure tolerance. There is also active work on distributed verification, where the question is not how to compute a solution but how to check that a solution is correct with minimal communication.
On the applied side, the rise of large-scale cloud computing, blockchain systems, and the Internet of Things has made distributed algorithms more relevant than ever. Consensus algorithms are now deployed in every major distributed database, and Byzantine fault tolerance has moved from a theoretical curiosity to a practical requirement for permissionless blockchains. The field has responded by developing algorithms that are more efficient in practice, such as partially synchronous consensus protocols that avoid the high communication costs of fully asynchronous ones, and by studying new models that capture the constraints of real networks, such as dynamic networks where the topology changes over time.
A notable recent development is the study of distributed algorithms for machine learning, where the challenge is to coordinate the training of a model across many nodes without centralizing the data. This work borrows techniques from both the fault-tolerance and complexity traditions, but it also introduces new questions, such as how to handle heterogeneous data and how to bound the communication cost of gradient updates. This is an active area where the field is extending its methods to new problems rather than settling into a fixed canon.
The field remains open in several directions. The gap between theory and practice is still wide: many theoretical results assume models that are cleaner than any real network, and many practical systems rely on heuristics that lack formal guarantees. Bridging this gap—by developing models that are both tractable and realistic, and by designing algorithms that are both provably correct and practically efficient—is the ongoing challenge of distributed algorithms.