Consensus (computer science)

• 1. Introduction

  ›

  Consensus, in computer science, is the problem of getting a group of computers to agree on a single answer, even when some of them fail. Google's lock service, called Chubby, depends on this problem being solved reliably. It stores lock information in files replicated across machines, running on a fault-tolerant log built on the Paxos algorithm. If even one participating computer crashes, lies, or falls silent at just the wrong moment, an entire system can drift out of agreement. So what actually counts as agreement, when the messengers themselves might be unreliable? What happens when a process does not merely stop working, but actively sends contradictory information to sabotage the outcome? And in a network with no central authority at all, how do total strangers ever manage to agree on anything?

• 2. Defining Agreement

  ›

  A protocol that simply made every process output the binary value 1 would technically finish. But it would be useless, since the result ignores what any process actually proposed. Consensus protocols must instead produce an output that traces back to some process's real input. Once a process decides on that output, the decision can never be revoked.

  Reaching agreement usually starts with a vote, where a majority means at least one more than half of all available votes. One or more faulty processes can skew that count, so the outcome may fail to form or form incorrectly.

  Three formal requirements define a correct consensus protocol: termination, integrity, and agreement. Termination requires that every correct process eventually decides on some value. Integrity states that if every correct process proposed the same value, any correct process that decides must choose that value. Agreement requires that every correct process settles on the same final value. A weaker version of integrity only requires the decided value to match what some correct process proposed, not necessarily all of them. A validity condition appears too, requiring that a message sent by a process must actually be delivered.

  A protocol able to guarantee consensus among n processes, even when as many as t of them fail, is described as t-resilient. Researchers judge these protocols on running time, typically expressed in Big O notation as the number of rounds of message exchange needed. They also weigh message complexity, meaning how much message traffic the protocol generates, along with memory usage and message size.

  None of these properties on their own distinguish between a process that has simply stopped and one that is actively working against the group.

• 3. Crash And Byzantine Failures

  ›

  A process suffering a crash failure abruptly stops and never resumes activity. A Byzantine failure imposes no such limits at all. It might result from the malicious actions of an adversary, sending contradictory or conflicting data to other processes. A process with a Byzantine failure might also sleep and then resume activity only after a lengthy delay. Of the two, Byzantine failures are far more disruptive to a system trying to reach agreement.

  A stronger version of consensus, built to tolerate Byzantine failures, tightens the Integrity requirement: if a correct process decides on a value, that value must have been proposed by some correct process.

  Guarding against this kind of adversary is part of why some systems require every message to carry proof of who really sent it.

• 4. Authentication And Value Types

  ›

  In most consensus models, participants communicate through authenticated channels, so receivers always know which process sent a given message. Some models go further with transferable authentication, where every message carries the sender's digital signature. That way, a receiver learns not just who forwarded a message, but who originally created it. Protocols with this stronger authentication can tolerate more faults. The two variants are called oral communication and written communication models. In an oral model, each step only reveals the immediate source. A written model preserves the entire chain of custody as a message passes along.

  Traditional protocols such as Paxos ask cooperating nodes to agree on one single value, like an integer that might encode a database transaction. Binary consensus narrows that further, restricting the output to a single digit, 0 or 1. On its own this is not very useful, but it often serves as a building block inside larger asynchronous protocols. Multi-valued consensus protocols such as Multi-Paxos and Raft instead agree on a whole growing series of values over time. Running a single-valued protocol repeatedly could achieve the same thing, but dedicated multi-valued protocols add optimizations, including support for reconfiguring the group.

  None of these design choices matter much until you ask whether the whole system can even count on messages arriving on time.

• 5. The Limits Of Asynchronous Systems

  ›

  Real-world networks are inherently asynchronous, but engineers often model consensus protocols as synchronous instead, since asynchronous systems raise far more complications. In a synchronous system, all communication proceeds in fixed rounds. During each round, a process sends every message it needs, then receives all the messages the other processes sent. Nothing from one round can influence the next.

  In 1985, Michael J. Fischer, Nancy Lynch, and Mike Paterson proved that in a fully asynchronous system, no deterministic algorithm can guarantee consensus if even one process might crash. Known as the FLP impossibility result, it was significant enough that the authors were later awarded a Dijkstra Prize. The result has since been mechanically verified to hold even under fairness assumptions. The proof rests on worst-case scheduling scenarios, the kind an intelligent denial-of-service attacker might engineer, rather than situations likely to arise from ordinary randomness in scheduling. FLP does not claim consensus can never be reached. It only shows that no algorithm can always reach it within a bounded amount of time, and in practice that failure is highly unlikely.

  Randomized consensus algorithms sidestep this limit entirely, achieving both safety and correct progress with overwhelming probability, even against the worst-case scheduling the FLP proof relies on.

  That gap between what a system can guarantee and what usually happens in practice matters even more in one particular setting. It's a network with no fixed, trusted list of participants at all.

• 6. Consensus In Practice

  ›

  Leslie Lamport's Paxos algorithm, along with variants such as Raft, runs throughout widely deployed distributed and cloud computing systems today. These protocols are typically synchronous, depend on an elected leader to make progress, and tolerate crashes but not Byzantine failures.

  Other protocols, including one called Cerberus, extend Byzantine fault-tolerant consensus to sharded distributed ledgers and have drawn academic analysis in their own right.

  Garay and Berman's Phase King algorithm solves binary consensus in polynomial time, even against Byzantine failures. It works in a synchronous message-passing system with n processes, tolerating up to f failures as long as n is greater than 4f. The algorithm runs through f plus 1 phases, each with two rounds. In the first round of a phase, every process broadcasts its preferred value and tallies which value the majority favored. In the second round, whichever process's ID matches the current phase number becomes that phase's king, broadcasting the majority value it observed to break ties. A process updates its own preference to the majority value only if that value's count exceeded n over 2 plus f. Otherwise, it defers to the king's choice. After all the phases finish, every process outputs its final preferred value.

  Many peer-to-peer online real-time strategy games rely on a modified lockstep protocol to keep game state consistent among players. Every action broadcasts a state change to all other players along with a hash of the total game state, and each player checks the change by applying it locally and comparing hashes. When the hashes disagree, players vote, and whoever ends up in the minority gets disconnected and removed from the game, a moment known as a desync.

  Every one of these systems assumes the circle of participants is already known and trusted. That is true from Paxos's elected leader down to a strategy game's list of players. That assumption breaks down completely once anyone with an internet connection is allowed to show up uninvited.

• 7. Open Networks And Sybil Attacks

  ›

  Consensus algorithms traditionally assume a fixed, known set of participants, permissioned in advance through some manual or automatic process so members can authenticate one another. Without that kind of closed, authenticated group, an attacker can mount what is called a Sybil attack. By flooding an open consensus group with enough fake virtual participants, the attacker can overwhelm its fault tolerance threshold and defeat even a Byzantine-resilient algorithm.

  A permissionless protocol flips this model, letting anyone join the network dynamically without asking permission first, while imposing some artificial cost as a barrier against Sybil attacks. Bitcoin introduced the first such protocol, using proof of work paired with a difficulty adjustment function. Participants compete to solve cryptographic hash puzzles, and the probability of solving one is proportional to the computing power a participant commits. Because any node can attempt the puzzle, a Sybil attack is infeasible unless an attacker controls more than half of the network's total computing power. Whoever solves the puzzle first gets to add their proposed block of transactions to the ledger, earning a reward for the effort.

  In 2018, bitcoin mining was estimated to consume non-renewable energy at a rate similar to the entire nations of Czech Republic or Jordan. Ethereum, the largest proof-of-stake network, used just under the energy of 205 average US households by comparison. Partly to avoid that high energy cost, later permissionless protocols adopted alternatives such as proof of stake, proof of space, proof of authority, proof of burn, and proof of elapsed time.

  Ripple takes a different approach, using validating nodes to confirm its ledger through a system called the Ripple Protocol Consensus Algorithm, or RPCA. The process runs in rounds: each server first compiles a list of valid candidate transactions, then gathers candidates from its Unique Nodes List and votes on which are genuine. Transactions clearing a minimum threshold move to the next round, and the final round requires 80 percent agreement before anything is confirmed.

  Unlike proof of work or proof of stake, which reward participants in proportion to what they invest, proof of personhood protocols try to give every real human exactly one unit of voting power regardless of wealth. Proposed ways to achieve that one-per-person distribution include physical pseudonym parties, social network verification, pseudonymized government-issued identities, and biometrics.

  None of these open-network solutions apply in one particular setting. That's when multiple processes read and write to the same block of shared memory instead of passing messages over a network.

• 8. Consensus In Shared Memory

  ›

  Solving consensus in a shared-memory system requires concurrent objects: data structures that let multiple processes coordinate by reading and writing shared state. Traditional critical-section implementations risk crashing entirely if a process dies inside the critical section or stalls there for a long time. To address that risk, researchers defined wait-freedom as a guarantee that an algorithm finishes in a finite number of steps.

  Every concurrent object gets a consensus number: the maximum number of processes that can reach consensus using that object in a wait-free way. An object with a given consensus number can implement any object with an equal or lower number, but never one with a higher number. This ranking is known as Herlihy's hierarchy of synchronization objects.

  Ordinary atomic read and write registers sit at the bottom of that hierarchy. They cannot solve consensus even between two processes. Structures like stacks and queues climb a little higher, solving consensus for exactly two processes, but no more. Some objects, though, are universal: they can solve consensus for any number of processes at all, and can simulate any other object through a sequence of operations. That universality is what separates a handful of powerful primitives, like compare-and-swap, from ordinary registers that were never built to referee a crowd.