I'm reading the FLP impossibility paper. I think I understand the idea of the proof, and I don't have questions about it.
However, it seems like the assumption of having at most, a single faulty process is not used in the proof. Put another way, if we remove this assumption and forbid process failure, the proof still seems to hold.
This can't be correct, because then it wouldn't be possible to construct a protocol that succeeds with no faulty processes. However, it is possible, and a protocol meeting this criterion is supplied in section 4.
My question is therefore: which part of the proof relies on the condition that one process can fail?
My best effort at an answer
For reference, the assumption in question appears in the definition below:
A run is admissible provided that at most one process is faulty and that all messages sent to nonfaulty processes are eventually received.
Also relevant is the definition of a deciding run:
A run is a deciding run provided that some process reaches a decision state in that run.
I'll also use my own definition, below:
A run is 0-admissible provided that no processes are faulty and that all messages sent to nonfaulty processes are eventually received.
I want to show that, by changing the definition of admissible to that of 0-admissible, the proof is no longer correct. Therefore, it would rely on the at most one failure part of the admissible assumption.
Lemma 2 ("P has a bivalent initial configuration") references this assumption. In particular:
$C_0$ and $C_1$ are $0$-valent and $1$-valent initial configurations, respectively. They differ only in the initial value $x_p$, of a single process $p$.
Now consider some admissible deciding run from $C_O$ in which process $p$ takes no steps, and let $\sigma$ be the associated schedule.
Then $\sigma$ can be applied to $C_1$, also, and corresponding configurations in the two runs are identical except for the internal state of process $p$. It is easily shown that both runs eventually reach the same decision value. If the value is $1$, then $C_0$ is bivalent; otherwise, $C_1$ is bivalent.
Both cases above being a contradiction, proving the lemma.
Replacing admissible with 0-admissible in Lemma 2
I'd hoped that replacing admissible with 0-admissible would show the proof no longer works.
For simplicity, I'll only consider the case where $N = 2$.
Now consider the (modified) line of the proof:
Now consider some 0-admissible deciding run from $C_O$ in which process $p$ takes no steps.
0-admissibility implies the following:
- Process $p$ cannot be faulty
- Process $p$ must have received all messages sent to it
- A decision state is reached
By non-triviality, the schedule $\sigma$ must not initially be in a deciding state.
Now, we know from (1) and (2) that no messages can have been sent to process $p$: Either it would have taken steps to receive them (violates assumptions), or it didn't receive them (violates 0-admissibility).
Therefore, we can ignore process $p$ and focus on the remaining process. I had assumed that it being deterministic implies the configuration must be univalent, but I can see a problem.
Namely, the deterministic process can introduce nondeterminism by sending a message to itself, and measuring the time taken to receive it. This effectively generates a random integer, which can be used to randomly choose an answer.
Even if it were right, this seems like a very complex answer to a simple question - have I missed something obvious? Is there another part of the proof where the assumption of faultiness is required more explicitly?