Consensus

Consensus is a problem of agreeing on a value among participants that may fail or communicate slowly. Agreement means correct processes do not decide conflicting values; validity constrains decided values according to the proposal model; termination asks that correct processes eventually decide under the specified assumptions. Different formalizations refine these properties, and not every consensus use case can be reduced to choosing an arbitrary string. In a replicated log, each position carries an agreed command and the protocol must preserve the order of committed entries. Safety is usually required at every moment, including severe partition. Liveness is conditional: protocols may make progress only when a sufficiently connected quorum and favorable timing conditions exist. Distinguish a process deciding from sending a proposal, accepting a tentative entry, or receiving a leadership heartbeat. These stages need separate state variables and logs in a serious test.

A safety proof commonly depends on intersecting quorums plus durable promises. Consider a majority voting protocol with five participants. Every pair of three-member majorities intersects, but the intersection helps only if a member remembers relevant promises or accepted values across failures. A process that grants incompatible acknowledgements after forgetting its previous vote can invalidate the reasoning. Some consensus protocols rely on ballot numbers, phases, and rules for carrying forward previously accepted values; others present equivalent restrictions through term and log matching. A proof must explain why a newly elected leader cannot replace an entry already committed. Assuming that 'a majority exists' without following the actual protocol transitions is not enough.

Imagine a seat-allocation service with a three-voter log. Leader A proposes allocation of seat 9 to client X, and a majority durably replicates it, making the entry committed under the protocol. A crashes before informing the client, so client X times out and retries. New leader B must preserve the committed allocation; it cannot issue another conflicting sale merely because X never received the response. The application must identify retries by operation key and be able to return the already-decided outcome. Consensus protects committed log history, while application-level idempotency protects the client-visible effect of ambiguous requests. They are complementary. The opposite case, a proposal appended only at A before its crash, may be discarded by the new leader; describing it as confirmed would have been premature.

Consensus imposes costs in network communication, persistent writes, leadership management, and membership configuration. A read-only static dataset may not need a consensus group for every request. A shard can keep its own consensus group so independent keys do not serialize through a global coordinator. However a transaction affecting several shards requires another atomicity mechanism if the application promises all-or-nothing behavior. Do not confuse consensus among replicas about one log with database serializability across independent logs. If the consensus group loses its required quorum, a safe implementation may stop accepting authoritative writes; this is expected protocol behavior rather than evidence that fault tolerance failed. Availability claims should state the number and placement of tolerable failures and any network assumptions.

Construct a bounded consensus value chooser where five voters track durable ballot promises and accepted proposals. Learners inject two competing proposers and delay selected messages. The tool distinguishes proposed, accepted, chosen, and learned states, and refuses to advertise a value as chosen until the required voters accept it under coherent ballot rules. Include a deliberate bug mode in which voters erase promises on restart; use the resulting trace to challenge an incorrect safety claim. A second trace isolates two voters and shows how a three-member majority can continue. Students must identify the exact assumption supporting termination after connectivity recovers. This teaching model is not a full Paxos proof and omits reconfiguration, Byzantine faults, and real storage failures.

Raft is a consensus algorithm designed around leader election, log replication, and safety constraints. Each node is commonly a follower, candidate, or leader for a given term. A candidate solicits votes; a leader appends log entries and sends append requests; followers enforce prefix matching and term rules. A client command becomes committed only under the algorithm’s commitment conditions, not merely because the leader appended it locally. A leader must observe the special Raft rule that prevents it from deciding earlier-term entries solely by counting replicas; it commits an entry from its current term using an appropriate majority before relying on commitment of preceding entries. This subtle condition is often omitted from educational shortcuts. Correctness arguments also rely on the voter restriction that a candidate's log is sufficiently up to date relative to voters.

Take three nodes A, B, C. A is leader in term 5 and has appended an entry at index 10 on A and B. The implementation may commit when the defined conditions hold. Now imagine A loses communication before confirming a different entry at index 11. C becomes a candidate in term 6 and requests votes. Voters compare terms and log freshness before granting them; a new leader is not permitted to discard a previously committed entry. During reconciliation, conflicting uncommitted suffixes can be overwritten. The visual distinction between commit index and last log index is essential. A student who interprets the longest log as 'all entries confirmed' will misdiagnose failures. Some log entries are speculative until their commitment conditions hold, and different nodes may temporarily have differing suffixes.

Paxos expresses similar agreement requirements through ballots and durable promises, but its organization differs from Raft's explicit leader-log narrative. In single-decree Paxos, a proposer obtains promises from a quorum, may need to carry forward the highest previously accepted value, and then asks acceptors to accept a proposal. Multi-Paxos applies repeated decisions under a stable leader optimization. Neither description means all implementations are interchangeable: membership, snapshotting, transaction routing, and durability design still matter. Students should compare the two in terms of invariants and information retained across failures, rather than claiming one is inherently faster in every environment. Raft's understandable exposition does not free implementers from verifying real-world variants.

Operationally, a three-voter group can tolerate one voting-node crash for continued progress when communication between the remaining two is sufficient. A five-voter group can tolerate two, but each write may interact with a larger set of hosts. Learners should not mistake higher replica count for linearly improved durability when all replicas share a faulty storage domain. Observer replicas can serve reads or backups depending on the system but do not count as voters unless configured as such. Monitoring should expose leader term, commit index, applied index, replication lag, and rejected stale requests. An election followed by a prolonged apply backlog is different from an election that cannot find a majority. Both may appear as slow client writes if only front-end response time is measured.

Build a simplified Raft log explorer with three voters and an explicit current-term commit rule. Controls allow append command, deliver follower acknowledgement, simulate crash, start election, and reconcile logs. Draw three distinct marks for appended, majority replicated, and committed. Attempt to construct two different committed values at the same log index; a correct test harness should reject every such trace under its specified transitions. Add an incorrectly implemented follower that forgets its persisted vote after restart; the lab can then display the violated assumption. Separately compare message counts during stable leadership and during repeated elections. State visibly that the model excludes joint configuration changes, log compaction, disk torn writes, and adversarial scheduling that is beyond the finite traces exercised.

A failure detector reports suspicions, not omniscient facts. In a network with unpredictable delays, a healthy node that responds late can look identical to a crashed node. Detector properties are often described using completeness, concerning whether failed processes are eventually suspected, and accuracy, concerning whether correct processes are wrongly suspected. Strong accuracy guarantees are difficult without timing assumptions. Practical detectors use periodic heartbeats, peer probes, recent latency distributions, or lease deadlines. An eventually accurate detector may initially make mistakes but stabilize once the network behaves favorably. This helps explain why many leader-based protocols separate the timeless safety rule from progress that depends on eventual timing stability. An operational detector is a sensor with false positives and false negatives; it is not a consensus algorithm by itself.

For an adaptive detector, let recent heartbeat intervals have a distribution. A suspicion threshold might be based on the probability that an observed delay would occur if the node were healthy, but that probability depends heavily on the quality and stationarity of the sample. Heavy-tailed delays, coordinated garbage collection, CPU throttling, and regional network congestion produce surprises. A fixed heartbeat timeout of 300 milliseconds may work in a quiet laboratory but fail under a noisy container scheduler. An adaptive threshold may reduce false positives while increasing time to recognize real crashes. The right objective is usually the service's end-to-end availability and safety, not maximizing a detector's raw sensitivity. Measurement should distinguish process heartbeat generation from network arrival, and should tag known maintenance windows.

Consider an image-processing service whose workers heartbeat every second. Under sustained load, one worker pauses its event loop for three seconds while draining a memory heap. A detector configured to suspect after two missed heartbeats removes the worker and reallocates its tasks. The original worker later resumes and may still attempt to publish completed results. If publication is guarded only by 'I was assigned this task earlier', duplicate work or stale writes can occur. A lease with fencing tokens or a transaction on the result record can keep effects safe despite false suspicion. The detector then influences efficiency and reassignment latency, while the resource-level protocol enforces correctness. This separation is central to realistic distributed design: failure detection need not be perfect when authority transfer is constructed safely.

A control plane should not blindly amplify a detector's mistakes. If hundreds of hosts report elevated RTT simultaneously, the likely cause may be a shared network issue rather than hundreds of independent crashes. Bulk rescheduling can overload the healthy remainder, increasing RTT and causing a cascade. Rate limit replacements, cap concurrent elections, and retain enough observability to diagnose correlated failures. During partitions, process-health checks and service-reachability checks may disagree; both measurements are useful when labeled accurately. Avoid using a single health status to decide all traffic routing, data authority, and operator alerts. The health rule for an HTTP replica may only ask whether it can serve stale reads, while the rule for accepting linearizable writes asks whether it belongs to a writable quorum.

Model heartbeat arrival as a configurable sequence of delays, drops, and process pauses. The learner chooses heartbeat interval, suspicion threshold, and recovery rule, then labels each false suspicion and actual missed failure. For deterministic input traces, compare the detector's confusion matrix and median time-to-suspicion, but do not treat those as universal reliability guarantees. Next feed its suspicion events into a toy reassignment service: contrast an unguarded worker that can publish after reassignment with one whose result sink enforces monotonically increasing epochs. Include a real crash and a long pause that are observationally equivalent up to the timeout. The exercise should teach why health detection and write authorization are different mechanisms.

The Fischer–Lynch–Paterson impossibility result addresses deterministic consensus in a completely asynchronous message-passing system when even one process can crash. Under that model, no algorithm can guarantee both the relevant correctness properties and termination in all admissible executions. The result does not claim that agreement can never occur, that distributed databases are useless, or that consensus implementations cannot be safe. It identifies an execution in which an adversarial schedule can keep the protocol from deciding. Practical systems obtain progress through additional assumptions or mechanisms, such as eventual synchrony, randomized choices, or failure-detector conditions. The distinction between guaranteed safety and conditional liveness is the main design insight. Students should resist simplistic slogans that 'FLP means consensus is impossible' without naming the model and guarantee.

A thought experiment compares two indistinguishable worlds for a process waiting on a peer. In world one, the peer crashed immediately. In world two, the peer is alive but its message has been delayed indefinitely so far. At every finite observation point the waiting process has the same evidence. If it must decide immediately in one world and wait safely in the other, a purely deterministic protocol cannot infer which world is real from silence. The formal FLP proof develops a more precise adversarial construction using bivalent configurations; the informal indistinguishability story illustrates only part of the intuition. Do not present it as a complete proof. The mathematically honest lesson is to state how the chosen production protocol achieves progress under a weaker guarantee, for example eventual favorable network behavior, rather than assuming a timeout measures truth.

CAP is a related but separate statement about replicated service under partition. For a network partition that blocks communication between relevant components, a service cannot guarantee both linearizable behavior and availability of every request in all components. A practical design may choose to reject some writes, allow only restricted operations, or permit divergent updates with later reconciliation. It may support different consistency models for different data types. This is not a claim that a service must choose one of three virtues permanently, nor that every network packet loss constitutes an unending partition. Coordinated reads and writes also trade latency for stronger guarantees when the network is healthy. Present CAP as a failure-mode boundary and explain the API contract chosen when communication is interrupted.

A design review of a two-region account ledger illustrates the boundary. If two regions are isolated and both must continue confirming balance-decreasing withdrawals against the same account, the system cannot guarantee an arbitrary global overdraft invariant without restricting which operations each region may authorize. One option is a leader region whose loss makes withdrawals temporarily unavailable elsewhere. Another is distributing bounded spending rights in advance and allowing only operations within each region's local allowance. The second changes the operational contract rather than violating impossibility results. It is important not to conflate a preallocated escrow system with unrestricted globally linearizable withdrawals. Both approaches deserve evaluation against latency, regulatory, recovery, and user experience requirements. The impossibility result directs architectural choices; it does not choose the business invariant for the architect.

Conduct an impossibility workshop with two browser-visible worlds sharing an identical prefix of message observations. At time t, one peer has crashed; the other is merely delayed beyond t. Ask the student what a local process can infer from the prefix and require explicit statements of model assumptions. Then let time advance and show the worlds diverge only after a message arrives; in the crashed world it never does. Compare a protocol that always waits for proof with one that relies on an eventual-synchrony timeout. Students should classify what is safety and what is progress in each trace. This is an intuition builder, not a mechanical proof of FLP or a randomized adversary model.

Design a replicated metadata log for a three-region science data portal. The log records which storage shard owns a dataset identifier, which model version is active, and which researchers have publishing permission. Contradictory authoritative metadata could route a write to the wrong owner or expose a publication before review. Place one voter in each region for the first design and document which regional failures the configuration is expected to tolerate. With three voters, two are required for a majority. A partition isolating one region leaves the other two able to form a quorum if their links and processes are healthy, while the isolated voter cannot establish new authoritative decisions. The system may still answer explicitly stale metadata queries from cache, but it must not pretend those are fresh authority checks.

A log proposal is distinct from a committed update. Let term 12 leader A append 'owner(dataset-7)=shard-X' at index 120 to itself and one follower. If the actual protocol's current-term quorum commit conditions hold, the entry becomes committed. A can crash before notifying the client, creating an ambiguous response, but a future legitimate leader must retain the entry. The test harness should record each node's term, vote, log prefix, commit index, and applied index to reconstruct the outcome. The next leader might have a longer local uncommitted suffix, yet voting restrictions ensure it does not undermine committed history. Do not assert safety solely from leader identity or the highest numerical term. The log matching and commitment rules establish which history is authoritative.

Now create an adversarial schedule in which two candidates start elections almost simultaneously. Delay their requests so votes split and neither reaches a majority. After randomized election backoff and eventually stable communication, one can usually become leader and restore progress. Under a fully asynchronous scheduler with unlimited delay there is no guaranteed termination for deterministic consensus with a possible crash. The capstone should therefore state safety as unconditional under its model and progress as depending on eventual favorable conditions. Students need to observe that a failed election is not itself a safety violation. A temporary period without a leader may be the correct price for refusing contradictory updates.

The design changes when a fourth region is added. A new host should not be made a voter by editing one local configuration file at a time; incompatible configurations may create unsafe quorum interpretations. The service needs a rigorous reconfiguration protocol that transitions ownership of voting authority safely. Read-only learners can be added with a different risk profile, because they are not automatically part of the commit quorum. For administrators, document how to remove a dead voter without creating overlapping membership histories. The maintenance runbook should show an authorized reconfiguration path and a recovery route from operator mistakes. Even perfect consensus code can fail its organizational objective if the only operator with control-plane permissions is unreachable during an outage.

A verification plan combines trace exploration with observable effects. Enumerate partitions, crash points, message reorderings, restarts, and delayed acknowledgements. For each trace test whether two different values were committed at the same index, whether any committed entry disappeared after election, and whether clients were told 'confirmed' before the commit condition held. Inspect liveness only for traces in which the required majority eventually communicates. Add state-machine commands that carry stable operation IDs so retrying an ambiguous metadata update cannot create a second logical action. This does not prove all possible executions; model checking a bounded state space can give stronger evidence for selected safety properties. The report should say exactly which failure modes were excluded, such as Byzantine voters or torn disk writes.