Distributed consensus, replication, and fault tolerance / personal lessonsLesson 7 of 17
Lesson browserDistributed consensus, replication, and fault tolerance lessonsPrevious: Quorums and the information in an intersectionNext: Raft elections and persistent terms
Distributed systems · Lesson 7

Consensus, safety, and the limits of progress

Understand FLP and CAP through their assumptions and indistinguishable executions.

By the end: Explain what an impossibility result forbids without concluding that real systems cannot work.

Define the decision problem

Consensus asks participants to decide a value subject to agreement, validity, and termination conditions. Agreement forbids incompatible decisions. Validity excludes meaningless solutions such as always deciding an unrelated constant; its exact formulation depends on the problem. Termination demands decisions by the required nonfaulty participants under specified conditions. A replicated log can use repeated decisions about ordered commands, but one decision and a complete storage service are different scopes.

Deciding that a command occupies a log position does not mean the command succeeds at the application level. The agreed command Reserve(12, Bo) can deterministically produce “already owned.” Consensus selects an agreed history in which the application checks its rules. It does not make every client request valid or eliminate application bugs.

Separate a proposed value from a final decision

For a small consensus problem, suppose three processes propose either 0 or 1. Use a validity condition that the decision must be a proposed value. If every process proposes 0, deciding 1 is forbidden. If both values are proposed, either can be valid, but the processes must not decide different values. The problem therefore contains both a choice and a restriction on how later decisions relate to earlier ones.

A proposal is information offered to the algorithm. A decision is a final result that the algorithm may no longer retract. Keeping a tentative local preference is harmless if the protocol can revise it. Reporting that preference as an irrevocable decision changes the safety obligation. A process that decides 0 cannot later say that its earlier result was merely provisional because another process decided 1. The promise made at the decision boundary matters.

Consider A and B proposing 0 while C proposes 1. A majority count makes 0 look natural, but consensus validity does not necessarily require majority preference. A safe algorithm could choose 1 in this mixed-input case. Conversely, counting two local preferences for 0 does not itself establish a safe decision protocol. The counting rule needs restrictions that prevent later participants from forming an incompatible decision from different evidence. The previous lesson separated that protocol obligation from set intersection.

This distinction explains why agreeing on a reservation command is different from approving a reservation. Suppose the agreed order contains Reserve(12, Ada), followed by Reserve(12, Bo). Each replica applies the first command to an empty seat and records Ada as owner. Each then applies the second command to an occupied seat and returns rejection. Both commands belong to the agreed history, but only one reservation succeeds. Application rejection is compatible with successful consensus about the order.

For the impossibility discussion, assume processes execute deterministic rules. Given the same local state and incoming event, a process makes the same transition. Assume messages can take arbitrarily long, and a process may crash without warning. The other processes cannot inspect its memory or directly detect its crash. Reliable communication between nonfaulty processes means messages eventually arrive in the relevant admissible executions. Reliability supplies eventual delivery, not a known deadline for deciding that an absent message will never arrive.

Keep two obligations separate when examining an algorithm. For safety, ask whether any permitted execution can produce incompatible final decisions. For termination, ask whether every execution covered by the claim eventually produces the required decisions. An algorithm that completes a million ordinary runs has evidence about those runs, not a guarantee over every permitted schedule. An algorithm that waits during uncertainty may protect agreement while failing an unconditional termination claim. The next section explains why the asynchronous model makes that distinction unavoidable.

Why waiting cannot always settle uncertainty

The Fischer–Lynch–Paterson result shows that deterministic consensus cannot guarantee termination in every admissible execution of a fully asynchronous message-passing system with even one possible crash. The model permits reliable but arbitrarily delayed messages. The result concerns guaranteed termination, not the impossibility of maintaining safety or of completing most practical executions.

The proof uses states where either decision remains possible and shows how an adversarial schedule can keep the system undecided. This can respect eventual delivery to nonfaulty processes; it is stronger than saying a permanently disconnected system can get stuck. This lesson gives the obstruction, not the full bivalence proof: if an unseen message may change which decision is safe, delay can preserve uncertainty. Real protocols add timing assumptions for progress, randomized choices, or stronger failure information. Raft does not escape by declaring delays impossible. It preserves safety while progress needs a stable leader able to communicate with a majority.

Why an unknown delay cannot become a proof of failure

Work through a separate paper case with processes A, B, and C. A has received B's proposal but nothing from C. One possible execution has C crashed before sending anything. Another has C alive, with its messages delayed. Through this point A has exactly the same received messages in both executions. If A's next action differs between those worlds, some additional source of information must explain the difference. A timeout alone cannot supply it in a model without delay bounds.

Waiting for C would be safe in some designs, but it would never end in the crash execution. Ignoring C may allow progress, but the algorithm must then establish why unseen work involving C cannot conflict with its result. This is where durable promises and quorum rules help safety. They restrict what C and other participants can later approve. They do not establish that a quorum will respond within a finite deadline known to A.

The full FLP argument goes beyond this single uncertain interval. It identifies an initial configuration from which either decision remains reachable, then constructs an execution that keeps such uncertainty unresolved. A configuration includes local process states and undelivered messages, not merely the proposals. The construction can delay decisive events without simply abandoning all delivery forever. This lesson's two-world cases explain the information obstacle, but they are not a replacement for the proof that such a schedule exists for every algorithm in the stated class.

A common attempted fix is a fixed deadline followed by a local decision. Suppose A's deadline expires with only proposal 0 visible, while C's expires with only proposal 1 visible. Deterministic local fallback does not make those two views equal. Increasing the deadline changes which delays cause trouble, but unbounded delay always permits a longer one. A protocol may instead refuse to decide without sufficient evidence. That preserves its agreement obligation at the cost of terminating in fewer executions.

Partial synchrony changes the progress argument. Imagine that after an unknown stabilization point, messages and processing become timely enough for one candidate to gather replies before competing candidates repeatedly interrupt it. Before that point, the protocol must still reject unsafe decisions. Afterward, an appropriate protocol can make progress using those timing conditions. The stabilization point need not be something a server can recognize with certainty. It is an assumption about the execution used to prove eventual progress.

Randomization changes a different assumption. A randomized algorithm can give probabilistic termination guarantees under its specified scheduler and communication model. That does not mean every possible sequence of coin outcomes terminates by a fixed deadline. Raft's randomized election timeouts help separate competing candidates in practice, while its progress still needs adequate communication and processing. Neither random timeouts nor eventual timing bounds authorize discarding durable safety rules when an election takes longer than expected.

Work through the model

Right-side evidenceHidden left-side historyRequired right read after left completion
No incoming messageNo write occurred0
No incoming messageWrite 1 succeeded1
The right side cannot produce both required answers from identical local evidence. Refusal changes availability, not the missing information.

Compare the two register worlds operation by operation

The model table compares identical evidence at the right replica, not identical global histories. To make its timing explicit on paper, let the register begin at 0. In the first world, no client writes anything. A right-side read begins and must return 0. In the second world, a left-side write of 1 finishes before that same right-side read begins. No other write occurs. The real-time precedence requirement now forces the read to return 1.

During the partition, the right replica receives no message that distinguishes these worlds. Its initial state and local request are the same. Returning its stored 0 satisfies the first world and violates the second. Inventing 1 satisfies the second and violates the first. The failure is not that 0 is usually stale or that 1 is statistically unlikely. The same local evidence cannot justify both answers when the object contract requires different results.

The argument depends on the write having completed before the read begins. Change the case so that the left write remains pending while the right read runs. A linearizable ordering may then place the read before the write and allow 0. That alteration does not defeat CAP. It removes the successful left operation used in this particular contradiction. If the left side withholds completion until communication resumes, the design has already stopped satisfying universal successful-operation availability during that partition.

An error response does not implement a successful read of the register. Returning an immediate unavailable error can be a useful operational policy, but it does not satisfy the formal availability condition in this argument. Similarly, accepting a write into a temporary queue is not necessarily completion of the advertised register write. If clients receive only a tentative receipt, the service must not describe it as the final success whose subsequent visibility linearizability constrains.

No finite response-time bound is needed for the basic contradiction. If the partition prevents distinguishing information indefinitely and the right-side nonfailed node must eventually complete the read successfully, waiting a little longer cannot solve it. Production service objectives often count successful responses within a deadline, perhaps over a month. Those uptime and latency measurements are useful, but they are not CAP's quantified requirement for every request to a nonfailed node under the modeled failures.

Use the table to vary one assumption at a time. Permit stale reads explicitly, and 0 becomes legal in the second world under that weaker contract. Require coordination with the left, and the right may stop completing reads during the partition. Supply reliable communication again, and the right can obtain the missing write. Each variation changes a specific premise. None lets an isolated replica preserve the original linearizable contract and universal successful availability without additional information.

Derive the partition conflict

Consider an initially zero register with replicas on two disconnected sides. A write of 1 completes on the left. A later read reaches the right, which has heard nothing about that write. From the right’s perspective this execution is indistinguishable from one where no write occurred. Returning 0 violates linearizability in the first execution; returning 1 without evidence is wrong in the second. Waiting or refusing can preserve consistency, but sacrifices the required successful response.

CAP formalizes an incompatibility between linearizable consistency and availability for every request at nonfailed nodes in the presence of partitions, under its model. An error response is not the successful object operation that would satisfy this availability condition. “Pick any two” is misleading: a partition is a failure condition to handle, not a useful feature to disable. Without a partition, there are still latency and coordination tradeoffs. FLP and CAP address different statements; neither proves that all distributed databases are unreliable.

State a useful progress guarantee with its conditions

A useful service specification does not need to promise progress under every imaginable failure. For a crash-tolerant majority protocol, it might promise eventual decisions when a majority retains its durable state, those members can exchange messages, processing continues, and leadership becomes stable enough. This is conditional liveness. The safety claim can remain broader, covering long delays and temporary isolation without allowing incompatible committed histories. The exact conditions belong to the protocol, rather than to majority arithmetic alone.

Consider five replicas with three on one side of a partition and two on the other. The larger side has enough identities for a majority action. It may still need to complete an election, recover storage, and exchange the required messages. The smaller side cannot create a majority by repeatedly retrying the same two peers. Saying that the majority side can continue means the partition has not removed the necessary quorum. It does not promise that every request immediately succeeds.

Now change the partition to groups of two, two, and one. All processes might be running, yet no group can exchange enough messages for a three-member quorum. Safety can remain intact while new decisions stop everywhere. This is not equivalent to losing all data. Already committed state may remain durably stored across several machines. The unavailable capability is authorization of new decisions under the normal rules, not necessarily access to every byte or knowledge of every earlier result.

A separate paper policy comparison clarifies which operations need that authorization. A confirmed seat reservation promises exclusivity, so two isolated sides cannot independently finalize competing owners. A display of yesterday's seat map can tolerate stale information if its API says so. A local note that has no exclusive ownership constraint may accept independent updates and reconcile later under a suitable merge contract. These are different objects or guarantees. CAP does not force one availability policy on every feature in an application.

When a team proposes a workaround, translate it into changed premises. A bounded-delay network changes the timing model. A stale-read endpoint weakens the read contract. A request rejected on the minority side gives up successful availability there. A trusted failure oracle adds information that ordinary timeouts do not provide. Naming the change prevents an engineering tradeoff from being mistaken for a contradiction of an impossibility theorem. It also reveals which new assumption needs operational support.

The following Raft lessons show how a concrete protocol preserves safety without relying on timeout accuracy. A timeout starts an attempt to acquire authority; durable votes and log rules determine whether that attempt succeeds. Later, safe reads require evidence of current authority and an applied committed prefix, not confidence that the network is usually fast. FLP explains why unconditional deterministic progress is unavailable under its assumptions. CAP explains why a particular partitioned object contract cannot also promise successful operations everywhere. Those are separate limits with separate premises.

Exercises

Does a timeout defeat FLP?

A developer guarantees consensus by choosing the local value after five seconds without replies. Which property is at risk?

Hint

Different machines can time out with different local proposals.

Worked answer
ParticipantOnly observed proposalTimeout decision
A00
B11
Independent timeout decisions do not constitute consensus.

Agreement can fail. Two isolated participants can decide different values. The timeout supplies no proof that a conflicting decision is impossible elsewhere. A correct protocol may instead stop deciding until it has sufficient evidence, giving up unconditional termination rather than safety.

Rejecting writes during a partition

A minority partition rejects writes while a majority continues. Is that necessarily an implementation failure?

Hint

Distinguish the selected safety contract from universal availability.

Worked answer
SideCan form majority?Write policy
A alone of threeNoReject or wait
B and CYesMay proceed under protocol rules
Availability depends on reachability and protocol state, not merely whether the process is running.

No. Rejection can be the intended way to protect a single authoritative history. Clients on the minority lose successful write availability. This is a stated tradeoff, not satisfaction of CAP availability through returning an error. Whether the policy is suitable depends on the operation’s requirements.

Sources and further reading

The explanations and worked answers above stand alone. These references provide the original algorithms, assumptions, and deeper proofs; they are not required downloads.

Lesson browserDistributed consensus, replication, and fault tolerance lessonsPrevious: Quorums and the information in an intersectionNext: Raft elections and persistent terms