FLP Impossibility and Failure Detectors

By the end of this lesson, you will be able to...

• State the FLP result with its assumptions instead of reducing it to “consensus is impossible.”

• Use indistinguishable executions and bivalence to explain why a deterministic protocol can remain undecided.

• Distinguish failure-detector suspicion from proof and trace how suspicion can support progress without carrying the safety argument.

Idea in one sentence: FLP identifies an execution in which asynchronous timing can keep a safe deterministic consensus protocol undecided, so practical systems add progress assumptions while keeping correctness independent of perfect failure detection.

Core Insight

One Missing Reply, Two Possible Worlds

Continue with the three-replica membership service from the previous lesson. Replica A is coordinating the next configuration command. Replica B has sent A a message and is waiting for a reply.

At local time t, B has received nothing. Two executions fit everything B has observed:

If the model places no upper bound on process speed or message delay, waiting longer does not separate the executions. The slow reply may always be a little later.

That is the pressure behind FLP. The protocol must stay safe in both worlds, yet a rule that waits forever for A cannot guarantee progress in the crash execution. A rule that acts after a timeout may improve progress, but the timeout does not turn the slow execution into the crash execution.

The initial model—“wait long enough and silence becomes proof”—works only when the system has a trustworthy timing bound. Full asynchrony removes that bound.

The Formal Claim and Its Boundaries

FLP studies a deterministic consensus protocol in an asynchronous message-passing system. Its core model includes:

• no bound on relative process speeds;
• no bound on message-delivery time;
• deterministic process steps;
• reliable delivery to processes that continue taking steps, although delivery may be delayed arbitrarily and reordered;
• the possibility that one process stops taking steps.

The consensus task requires three ideas:

• Agreement: correct processes do not decide different values.
• Validity: the protocol cannot decide an unrelated fixed value regardless of the inputs.
• Termination: correct processes eventually decide.

Under those assumptions, FLP proves that every deterministic consensus protocol has a possible admissible execution that never reaches a decision, even though at most one process may crash.

The word possible does important work. FLP does not say:

• every execution fails to decide;
• messages are always lost;
• practical consensus systems never work;
• safety must be abandoned;
• a crashed process actually appears in every nondeciding execution.

The original result uses a particularly strong counterexample: the constructed nondeciding run can keep processes taking steps and eventually deliver messages while still avoiding the event that forces one decision. The environment only needs the freedom to delay the right event at the right time.

So the compact statement is:

deterministic consensus
+ full asynchrony
+ the possibility of one crash
+ agreement, validity, and guaranteed termination in every admissible run
= impossible combination

FLP is a liveness boundary. A protocol may preserve agreement by remaining undecided.

Bivalence Makes the Boundary Inspectable

The proof uses a small vocabulary for global configurations. A configuration includes every process's local state and all messages waiting to be delivered.

• A 0-valent configuration can lead only to decision 0.
• A 1-valent configuration can lead only to decision 1.
• A bivalent configuration still has an execution leading to 0 and another leading to 1.

Think of bivalence as “the decision has not yet become inevitable.”

Use a simplified binary membership decision:

0 = keep configuration {A, B, C}
1 = move to a proposed replacement configuration

Suppose the current configuration C is bivalent. Somewhere in every deciding execution, one event must move the system from bivalent to univalent:

C --deliver message m to B--> a decision becomes inevitable

Call m a critical event for the teaching example. An asynchronous scheduler may delay m and deliver other independent messages first. The FLP proof shows, more carefully than this sketch, that from a bivalent state the scheduler can select a finite sequence of other events and then handle the pending event while ending in another bivalent state.

The scheduler repeats that move:

bivalent C0
  -> allowed steps that preserve bivalence
bivalent C1
  -> allowed steps that preserve bivalence
bivalent C2
  -> ...

No process has decided because every reached configuration still permits both outcomes. Yet the constructed schedule remains admissible: processes continue, and messages to nonfaulty processes are eventually delivered. The scheduler does not postpone one fixed message forever. It keeps finding the next event whose timing can preserve uncertainty.

This is not a full proof, but it exposes the mechanism of the impossibility result:

1. some valid starting state is bivalent;
2. deciding requires crossing from bivalent to univalent;
3. asynchronous scheduling can keep avoiding that crossing;
4. therefore termination cannot be guaranteed for every admissible execution.

The result does not tell an operator that today's stalled cluster is “an FLP incident.” It tells a protocol designer which universal promise cannot be made without another assumption.

A Timeout Changes Policy, Not History

Return to B, which is waiting for A. A timeout can produce this local event:

at t = 300 ms:
  suspect A
  start a newer attempt

The 300 ms value is illustrative. It reflects an operational policy, not an observed upper bound supplied by the asynchronous model.

After the timeout, B knows that its waiting policy expired. It still does not know whether A crashed. The next message from A could arrive at 301 ms.

This distinction divides responsibilities:

• Suspicion machinery decides when to try a recovery action.
• Consensus safety rules decide which votes, ballots, terms, or log evidence may become authoritative.

If B falsely suspects A, there may be overlapping leaders or proposers for a while. That must be safe. The newer attempt may interrupt the older one, but neither attempt may bypass the evidence rules learned in lesson 001.

Failure Detectors Describe Useful Suspicion

A failure detector is an abstract component that supplies each process with a changing set of suspected processes. It may be wrong.

Chandra and Toueg classify unreliable failure detectors along two axes:

• Completeness constrains whether crashed processes are eventually suspected.
• Accuracy constrains false suspicion of correct processes.

There are strong, weak, and eventual variants. This lesson does not need the full hierarchy. The durable model is that completeness helps a protocol stop waiting for a process that really crashed, while the relevant accuracy property limits false suspicion. In a consensus algorithm that uses a suitable detector, sufficient accuracy can leave a correct coordinator trusted long enough to finish useful work.

The paper's important correction is that a failure detector need not provide perfect truth. Some classes can make mistakes—potentially many mistakes—and still provide enough structure for consensus under their stated process assumptions.

Practical heartbeat and timeout mechanisms are implementations built under additional timing and operational assumptions. The formal failure detector is the property contract consumed by the algorithm. Those two levels should not be blurred.

Worked Trace: A Safe but Noisy Election

The following teaching trace uses simplified rounds rather than a complete Raft or Chandra–Toueg algorithm.

Starting state:

A coordinates round 7
B and C follow
no value is committed in round 7

Step 1: A false suspicion

A pauses for 450 ms. The illustrative election timeout at B is 300 ms.

The detector was inaccurate about the crash: A was alive. Starting a newer round may hurt liveness by causing contention, but a correct protocol does not let false suspicion create two committed values.

Step 2: Repeated churn

Suppose variable pauses cause A, then B, then C to be suspected. The cluster enters rounds 8, 9, and 10 without giving one coordinator enough stable communication time to complete.

round 8: B suspected before completion
round 9: C suspected before completion
round 10: A suspected before completion

Safety may still hold. Liveness is poor because the suspicion pattern keeps changing the progress path.

Step 3: A useful stable period

Now message delays and process pauses remain below the operating policy long enough for B to communicate with a quorum. The detector stops suspecting B during the needed interval. B completes the protocol's evidence-gathering steps and the cluster decides.

The stable period did not prove that failures had become impossible. It supplied enough useful accuracy for one coordinator path to finish. If another coordinator had crashed, completeness would help correct processes eventually stop waiting for it.

So far, the stronger model is:

safety comes from protocol evidence
progress comes when the environment and suspicion contract
allow one valid path to finish

Trade-offs and Boundaries

Acting quickly on suspicion can reduce recovery time after a real crash. It can also create false elections, abandoned rounds, extra traffic, and longer commit latency during pauses or congestion.

Waiting longer reduces false suspicion under the measured workload. It increases the time before recovery begins when a coordinator actually fails.

This is a situated trade-off, not a universal timeout formula. The relevant constraints include latency distribution, pause behavior, failure domain, quorum placement, and the cost of an unnecessary election. Useful signals include election or ballot rate, detector suspicion changes, heartbeat latency, quorum availability, and time since the last commit.

FLP and failure detectors also leave important boundaries:

• FLP does not diagnose the cause of one production stall.
• A timeout does not certify a crash.
• A failure detector does not replace quorum or ballot safety rules.
• Partial synchrony does not mean every message is fast; it means the progress argument eventually receives enough bounded behavior.
• Randomized consensus follows another route: it weakens deterministic termination to a probabilistic guarantee. That route is outside this lesson.

Check Your Understanding

Check: A deterministic consensus run decides normally after 40 ms. Does that contradict FLP?

Think first, then reveal.

Answer: No. FLP says some admissible execution can avoid decision; it does not say every execution is nonterminating.

Check: B times out while waiting for A. Which claim is justified?

Think first, then reveal.

Answer: B may say that its timeout policy expired and act on suspicion. It may not conclude from silence alone that A crashed.

Practice: Separate Safety from Progress

A three-process protocol is in a bivalent configuration. The coordinator A pauses. B suspects A, starts a newer round, and later receives a delayed message from A.

Explain:

1. why the timeout cannot distinguish a pause from a crash;
2. which part of the design may use the suspicion;
3. which part must reject stale or conflicting authority;
4. what environmental change could allow progress;
5. which observation would reveal churn rather than a safety violation.

A good answer should mention:

• the two executions have the same local history at B until another event distinguishes them;
• the progress policy may use suspicion to start a newer attempt;
• ballot, term, voting, and quorum rules—not the timeout—must protect safety;
• a stable interval in which one valid coordinator communicates with a quorum can permit termination;
• repeated elections or increasing rounds with no conflicting commits indicate liveness trouble, while two conflicting committed decisions would indicate a safety failure.

Resources

• [PAPER] Impossibility of Distributed Consensus with One Faulty Process — Focus: The asynchronous model, bivalent configurations, and the admissible nondeciding run.
• [PAPER] Unreliable Failure Detectors for Reliable Distributed Systems — Focus: Completeness, accuracy, and consensus with detectors that may make mistakes.
• [PAPER] Paxos Made Simple — Focus: How safety survives delayed messages while progress requires a distinguished proposer to communicate with a majority.

Key Takeaways

• FLP rules out guaranteed termination for every admissible execution under a specific deterministic asynchronous model; it does not say consensus never terminates.
• Bivalence makes the nontermination mechanism visible: scheduling can keep the next decision from becoming inevitable.
• A timeout changes the recovery policy, not the facts about whether another process crashed.
• Failure detectors describe useful but potentially mistaken suspicion through completeness and accuracy properties.
• Consensus safety must survive wrong suspicion; progress resumes when the stated environmental assumptions let one valid path finish.