Where does the FLP impossibility proof depend on allowing a single process failure?

Question

Question

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

Definitions

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.

Approach

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

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:

1. Process $p$ cannot be faulty
2. Process $p$ must have received all messages sent to it
3. 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?

Answer 1

The part of the original paper's proof that requires node failure to prove the impossibility is case 2 of lemma 3. This case assumes that there is a "finite deciding run from C0 in which p takes no steps". p taking no step means it has died/failed.

From case 1 of lemma 3, we know that there exists a pair of messages, called e and e' which affect the decision process, and if they are received by different nodes (p and p') the nodes will decide on different values. This means that these "important messages" must be received by a single node p only.

Case 2 tests this further with the possibility that node p, the recipient of the "important messages", fails (or "takes no steps"). If a "totally correct in spite of one fault" algorithm exists, it needs to tolerate the scenario where node p fails after configuration C0. Of course, p might just not fail, and the algorithm must be correct in both scenarios: p failing and p not failing.

Since the algorithm must decide on some value, if p is failing it has to proceed through some run called sigma and arrive at a deciding configuration A.

The problem here is that if p is actually still functional, it will accept e and e' and decide on its own. As we know from case 1, node p can decide on 0 (e arriving before e') or decide on 1 (e' arriving before e). So node p is making a decision on its own with no regard for what the rest of the nodes (through sigma) are deciding and ultimately there will be a case where the 2 set of nodes decide on different values.

As for your proof, since p takes no steps (it dies after C0), it invalidates your definition of a 0-admissible run.

Answer 2

[Well, I am no expert, but here we go.]

The assumption of at most a single faulty process is used twice.

First, it is used to establish that there is one bivalent starting configuration. (FLP Lemma 2)

[Assume not. Then all starting configurations are monovalent, and by the need to avoid triviality, at least one must be 0-valent and at least one must be 1-valent. This then means that a 0-valent start must be ‘next’ to a 1-valent start. ‘Next’ here means differs only in the input value of one process. For example, with just two processes we might have

p1 input=1 p2 input=1 say… 0-valent

p1 input=1 p2 input=0 say… 1-valent

Now, assume the system is ‘fault tolerant’ and can work with a single faulty process and p2 dies immediately.

So, from the first line

p1 input=1 p2 input=1 p2 dead but supposed to be 0-valent

there must be a schedule (=sequence) of events such that p 1 leads the whole system to a 0-valent configuration. Schedules are produced by processes asking the message buffer for their messages and the buffer firing back a single message, essentially event(process i, message m). Process 2 is dead, we may imagine, so never asks the buffer for anything. So, this schedule, say s, that produces a 0-valent configuration involves only events requested by, and processed by, process 1. The schedule looks like this

< event(process 1, message ?), event(process 1, message ?), event(process 1, 
message ?), etc. >. 

Now, focus attention on the second input configuration

p1 input=1 p2 input=0 say… 1-valent

and apply schedule s to it. Schedule s is perfectly good. It is quite possible for the message buffer to hold the relevant messages, and quite possible for it to produce schedule s (since there is a randomness to what it supplies to process 1 and process 2 in response to their requests). Schedule s will run exactly the same with input

p1 input=1 p2 input=0

as it does with input

p1 input=1 p2 input=1

since all the events go to p1 and all the processing is deterministic. So, the resulting configuration will be 0-valent. But the second configuration is supposed to be 1-valent. So, this is a contradiction.

Notice here, that in the running from the second input configuration, process 2 does not have to be dead. It can be alive and well, but the situation is that no events, or no configuration changing events, go to it.

Second, in case 2, of the ‘bivalent has a later bivalent’ lemma, process death is invoked (or imagined). (FLP Lemma 3 case 2.)

Here we can imagine a horizontal tree, the nodes of the tree are configurations, and the branches are sequences of configurations. Sequences of configurations can be thought of as sequences of events (whose application to previous configurations produce configurations) i.e. the sequences of configurations are schedules. Events can be understood as labels on the branch segments. We are also interested here in partial branches i.e. from root to node but not necessarily out to leaf. These partial branches are also schedules (sequences of events). Now, we are going to hang from each node an additional applicable event, say e, and these hang down vertically like baubles on a Xmas tree. Effectively, e, is appended to every schedule, being a leaf on new branches and longer schedules. We are also going to insist that e did not appear in any schedule in the tree before we added it (so, had it been there we would delay it until it ends up as a leaf). The event e can be called a ‘critical event’. Every leaf in the tree has now been produced by the application of e to the penultimate node in its branch. The root configuration of the tree is bivalent (for that is what we are starting from). In part, this means that one leaf is 0-valent and one leaf is 1-valent. But the question is: are any of the leaves bivalent? [We are trying to prove that at least one is.] Assume not. So, all leaves are monovalent. We will say that one leaf is ‘next’ to another, if the node that the first hangs from is ‘next’ to the node that the second hangs from. And one node (= configuration) is next to another node (= configuration) if the second can be obtained from the first by the application of a single event, say e* i.e. c2= e* (c1) . Now, somewhere in the tree a 0-valent leaf is next to a 1-valent leaf (FLP prove this). So

c2= e* (c1)

l1= e (c1)

l2= e (c2)

l1= 0-valent, say

l2= 1-valent, say

But this turns out to be contradictory. We need to look in more detail at the events and their processes, say

e= event(process1, message?)

e*= event(process*, message*?)

Case 1. process1 and process* are different processes, in which case disjoint schedules (events) involving them commute, so

l2 is 1-valent

l2= e ( e* (c1)) = e* (e (c1)) = e* (l1)

But if l2 is e* (l1) it is a child of l1 and thus is 0-valent

So, l2 is both 0-valent and 1-valent (a contradiction).

Case 2 process1 and process* are the same process, say p1 (FLP Figure 3)

We will want to have a second process, say p2 (the proof holds only for two or more processes)

focus now on the configuration (i.e. node) c1. There will be a schedule, say, s, which both transforms c1 into a determinate state (i.e. 0-valent or 1-valent), say node A, and does not involve the process p1. The system as a whole is assumed to be fault tolerant and so can run to determinate states when a single process say p1 is dead. And also, all configurations have schedules which take them to determinate states. This schedule s is disjoint with the schedule

<e> 

and also with the schedule

<e*, e>, 

this means that it will commute with both of these. (Basically, s runs on p2 and e* and e on p1.)

l1= e (c1)

define E0 to be the configuration

E0= s(l1) so E is 0-valent (it is a child of the first leaf)

E0= s(e (c1))= e (s (c1)) by commutativity

A= s(c1)

E0= e(A)

So E0 is a child of A and so A is 0-valent

But

l2= <e*, e> (c1)

define E1 to be the configuration

E1= s(l2) so E is 1-valent (it is a child of the second leaf)

E1= s(<e*, e> (c1)) = <e*, e>  (s (c1)) by commutativity

A= s(c1)

E1= <e*, e> (A)

So E1 is a child of A and so A is 1-valent

A is both 0-valent and 1-valent, which is a contradiction.

So…. Every bivalent has a later bivalent (assuming asynchronous messaging and a possible single faulty process).

What about the schedule s? It was constructed from fault tolerance and the need to run to determinate states when a single process, say p1 is dead. But having got s, which does not involve p1 at all, p1 can be alive and well and yet the system runs from one bivalent state to another (and then it is possible for the system to do this over and over).

Hope this helps. Sorry for any typos or blunders.

Answer 3

In the PROOF of LEMMA 2:

Now consider some admissible deciding run from $C_0$ in which process p takes no steps, and let u be the associated schedule.

The protocol can become deciding without talking to p. This requires the protocol can tolerate one fault. In other words, if the protocol tolerates no fault, it requires every process to participate to eventually become deciding.