Consensus (computer science) - Core Consensus Foundations

Understanding the Consensus Problem What is Consensus? In distributed computing, consensus is a fundamental problem where multiple independent processes must coordinate to agree on a single data value. Each process starts with its own proposed input value, and the challenge is to design a protocol that makes them all reach agreement despite the inherent difficulties of distributed systems: process failures, unreliable communication, and the lack of a global clock. Think of it like a committee where members are located in different cities and need to decide on a single proposal. Each member starts with a preference, but they must eventually all agree on the same final decision, even if some members fail or act deceptively. The Three Core Requirements A valid consensus protocol must satisfy three essential properties: Non-triviality. The agreed-upon output value must be the input of at least one correct process. This prevents the trivial solution where all processes simply output a default value like "0" without actually considering anyone's input. The protocol must meaningfully reflect the participants' inputs. Agreement and Irrevocability. Each process may decide on an output value only once, and once a decision is made, it cannot be changed or reversed. This "irrevocable" property is crucial: processes cannot change their mind after deciding, which prevents flip-flopping and ensures stability in the final result. From this requirement, we also get that all correct processes must decide on the same value. Termination. All correct processes must eventually reach a decision and output their chosen value. A protocol that runs forever without concluding, or that leaves some processes waiting indefinitely, does not solve consensus. Termination is particularly challenging when failures can occur, since the protocol must complete even when some processes crash or behave unpredictably. Understanding Fault Models Before a consensus protocol can be evaluated, we must define what kinds of failures can occur. Different fault models lead to different problem difficulties and protocol designs. Crash Failures. A process experiencing a crash failure stops executing permanently and never resumes. Once a process crashes, it simply disappears from the computation—it stops sending and receiving messages, ceases processing, and takes no further action. This is the more optimistic failure model because a crashed process becomes predictable: we know it will do nothing. Other processes can eventually recognize that it has crashed through timeout mechanisms. Byzantine Failures. A Byzantine failure is far more severe. A process experiencing this type of failure can behave completely arbitrarily: it might send conflicting messages to different processes, delay messages, send invalid data, ignore its protocol, or coordinate with other faulty processes. The term "Byzantine" comes from the famous Byzantine Generals Problem, where the challenge is reaching agreement even when some generals are traitors who actively try to disrupt the consensus. Byzantine failures are much harder to handle because faulty processes appear unpredictable and can actively work against the agreement goal. The key insight: crash failures are passive (bad things stop happening), while Byzantine failures are active (adversarial behaviors continue happening). Two Types of Validity Conditions Consensus protocols differ in exactly what values are "valid" to output. Two formal definitions capture different security levels: Weak Validity. Under weak validity, the output of each correct process must equal the input value of some correct process (not necessarily the same correct process for all agreeing parties). This condition is weaker because it allows flexibility—as long as the agreed value came from at least one correct process, it is valid. However, it permits scenarios where correct processes might output the input of one correct process even if most processes proposed different values. Strong Validity. Under strong validity, if all correct processes start with the same input value, then they must output that exact value. This is a much stronger guarantee: consensus cannot "flip" to a different value if everyone was already in agreement. Strong validity prevents protocols from ignoring unanimous agreement among correct processes. Every consensus protocol satisfying weak validity does not automatically satisfy strong validity—strong validity is an additional constraint that excludes certain protocol designs. Example: Suppose all correct processes propose the value "Yes". A protocol with only weak validity might still output "No" (because a Byzantine process proposed "No"), which seems wrong when everyone agreed. A protocol with strong validity must output "Yes" in this case, respecting the unanimous input. Resilience and Fault Tolerance Bounds Once we define what kinds of failures can occur, we can measure a protocol's robustness using the concept of resilience. A protocol is called t-resilient (or tolerates t faults) if it correctly solves the consensus problem despite the simultaneous failure of up to t processes. Here, t is the maximum number of faulty processes the protocol can handle while still satisfying all three requirements (non-triviality, agreement, and termination). The value of t is crucial because it determines the practical applicability of a protocol. For example: A protocol that is 1-resilient can handle one crashed or Byzantine process A protocol that is 5-resilient can handle up to five failures simultaneously A protocol that requires $n$ correct processes (where $n$ is the total) to reach agreement is 0-resilient—it fails if even one process fails The challenge lies in understanding the fundamental limits: given n total processes, what is the maximum t for which consensus is solvable? For crash failures, consensus is solvable when $t < n/2$, but for Byzantine failures, the requirement is even stricter: $t < n/3$. These limits come from impossibility results that prove no protocol can do better.