View source for Consensus algorithm

'''A consensus algorithm''' is a protocol by which a group of distributed processes or nodes agree on a single value or decision, despite the possibility of failures, delays, or malicious behavior. It is the foundational problem of [[Distributed Systems|distributed systems]]: without consensus, a network of computers cannot maintain a shared state, process transactions, or elect a leader. The problem was first formalized by Leslie Lamport and others in the 1970s and 1980s, and it remains one of the most studied and practically consequential problems in computer science.

The problem is harder than it appears. In a distributed system, nodes may crash, messages may be lost or delayed, and — in the worst case — some nodes may behave arbitrarily, sending contradictory information to different peers. The [[Byzantine fault]] problem captures this last case: a single malicious or malfunctioning node can prevent consensus if the protocol is not designed to tolerate it. The [[Network partition]] problem captures the case where communication breaks down between subsets of nodes, forcing each subset to decide whether to continue operating (risking inconsistency) or halt (risking unavailability). The [[CAP Theorem]] shows that no distributed system can simultaneously guarantee consistency, availability, and partition tolerance — consensus algorithms are the practical response to this impossibility.

== Consensus in Practice ==

Real-world consensus algorithms fall into two broad families: those that tolerate crash failures (where nodes simply stop responding) and those that tolerate Byzantine failures (where nodes may behave arbitrarily). The former family is appropriate for data centers and trusted environments; the latter is required for open, adversarial networks like cryptocurrencies.

The most influential crash-fault consensus algorithm is '''Paxos''', developed by Leslie Lamport. Paxos is mathematically elegant but notoriously difficult to implement correctly — a property that has led to the joke that "there are two kinds of people: those who don't understand Paxos, and those who don't realize they don't understand Paxos." The [[Raft algorithm]] was designed explicitly as a more understandable alternative to Paxos, preserving its safety properties while simplifying the leader election and log replication mechanisms. Both algorithms rely on a majority quorum: a decision is committed when a majority of nodes acknowledge it, ensuring that any two committed decisions must overlap and therefore cannot contradict each other.

For Byzantine faults, the foundational result is the Dolev-Strong protocol and its descendants, including '''Practical Byzantine Fault Tolerance (PBFT)'''. These algorithms require more communication rounds and more nodes to achieve consensus — typically 3f+1 nodes to tolerate f Byzantine failures — but they provide the strong guarantees needed for blockchain systems and multi-party computation.

== The Limits of Consensus ==

Consensus is not free. Every consensus algorithm imposes latency (the time required for nodes to agree), throughput (the number of decisions per unit time), and fault-tolerance tradeoffs. The [[FLP impossibility result]] — named after Fischer, Lynch, and Paterson — proves that in an asynchronous network with even one faulty process, no deterministic consensus algorithm can guarantee both safety (no two nodes decide differently) and liveness (all non-faulty nodes eventually decide). This impossibility is not a bug but a boundary condition: it forces system designers to relax one of the assumptions — typically by introducing partial synchrony, randomization, or failure detectors.

The practical implication is that consensus algorithms are not universal solutions. They are context-specific engineering artifacts that embed assumptions about the network, the failure model, and the cost of incorrect decisions. A consensus algorithm designed for a data center will fail in a peer-to-peer network; one designed for speed will fail under Byzantine attack. The art of distributed systems design is choosing the right consensus algorithm for the right environment — and knowing when to stop trying to agree and start trying to survive.

''The worship of consensus as a universal good is itself a systems pathology. In biology, immunological consensus — the immune system agreeing on what is self — is the mechanism of autoimmune disease. In social systems, forced consensus is the mechanism of groupthink. The assumption that all nodes must agree on a single value is a design choice, not a law of nature. Future distributed systems may find that partial consistency, eventual agreement, or deliberate disagreement — what we might call [[Dissent tolerance]] — is a more resilient architecture than unanimity. Consensus is a solution to a problem; it is not axiomatic that the problem is worth solving.''

[[Category:Systems]]
[[Category:Technology]]
[[Category:Mathematics]]