Fischer-Lynch-Paterson Impossibility Result

The paper proves that any consensus protocol that tolerates one process failure under the reliable (completely) asynchronous message system, in which all messages are eventually delivered with arbitrary delay and out of order, fails to reach consensus when messages are delivered in inappropriate timing.

The proof goes, quite elegantly, by showing a message delivery strategy which keeps consensus protocols forever indecisive.

Crucial assumption of the proof is complete asynchrony: no assumption about the relative speeds of processes or the delay time in delivering messages. In particular, processes do not have access to synchronized clocks.

Terminology

A configuration is a state of the system, which consists of states of all the processes and a state of the message system. Accessible configurations are configurations that are reachable from an initial state.

A step (p,m) takes one configuration to another, and consists of a single process p receiving a message m (from the message system, which may send the special “no-message” message), entering a new state and sending a finite set of messages to other processes (via the message system).

A process is nonfaulty if it takes infinitely many steps, and it is faulty otherwise.

A process decides on a value in {0, 1}, and decision cannot be changed or reversed.

A run is a finite or infinite sequence of steps. A run is admissible if at most one process is faulty and all messages sent to nonfaulty processes are eventually received (with arbitrary delay and possibly out of order). Therefore, we assume the message system is reliable – it delivers all messages correctly and exactly once. Moreover, an atomic broadcast capability is assumed – a process can send the same message in one step to all other processes.

A run is deciding if some process reaches a decision state.

A consensus protocol is partially correct if

1. No accessible configuration has more than one decision value.
2. For each v in {0, 1}, some accessible configuration has decision value v. (This is to eliminate the trivial solution, in which, say, 0 is always chosen.)

Main result

Any partially correct consensus protocol admits an (infinite) admissible run which is not deciding.

Proof

By contradiction: assume a partially correct consensus protocol, for which every run is deciding.

A configuration C is bivalent if, for i = 0, 1, i-decided configuration is reachable from an initial configuration. A configuration is 0-valent (resp. 1-valent) if any decided configuration reachable from an initial state has decided on 0 (resp. 1). By definition, a 0-decided (resp. 1-decided) configuration is 0-valent (resp. 1-valent). A configuration is univalent if it is either 0-valent or 1-valent.

The crux is to prove a lemma, which states that, for any bivalent configuration C and any step (p, m) that is applicable to C, there is a run from C to a bivalent configuration, whose last step is (p,m).

By repeatedly applying this lemma, we can construct an (infinite) admissible run which is not deciding, by sending out every message eventually while staying bivalent.

Proof of the lemma.

Let S be the set of configurations reachable from C by (finite) runs whose last step is (p,m).

We prove by contradiction that S contains a bivalent configuration. So, assume S only contains univalent configurations.

Since C is bivalent, S must contain both 0-valent and 1-valent configurations.

Without the loss of generality, we assume (p,m)(C) is 0-valent.

By induction, we obtain a configuration C₀ such that (p,m)(C₀) is 0-valent and (p,m)(p’,m’)(C₀) is 1-valent for some (p’,m’).

If p != p’, then (p’,m’)(p,m)(C₀) = (p,m)(p’,m’)(C₀). Contradiction, since a 0-valent configuration cannot be a 1-valent at the same time.

So, assume p = p’. Consider any (finite) deciding run σ from C₀ in which p takes no steps. By our assumption, (p,m)σ(C₀) = σ(p,m)(C₀) is 0-valent, but (p,m)(p, m’)σ(C₀) = σ(p,m)(p’,m’)(C₀) is 1-valent. However, since σ is a deciding run, σ(C₀) must be univalent. Contradiction. ∎

References

Impossibility of Distributed Consensus with One Faulty Process, Journal of the ACM, 1985