I'm reading Fischer et al.'s Impossibility of Distributed Consensus with One Faulty Process, and I don't quite follow 2 points:

The first is in the proof of Lemma 3, pg. 378:

Otherwise, $e$ was applied in reaching $E_i$, and so there exists $F_i ∈ \mathscr{D}$ from which $E_i$ is reachable.

Why does there exist $F_i ∈ \mathscr{D}$ from which $E_i$ is reachable?

The second is more general: what does having at most one faulty process have to do with the theorem that "no consensus protocol is totally correct in spite of one fault"? In the part where

We now show that it is always possible to run the system in a way that avoids such steps, leading to an admissible nondeciding run.

I don't see anything depending on having at most one faulty process. In fact, what would change if no process was faulty?


1 Answer 1


Adding context:

If $E_i\in\mathscr C$, let $F_i = e(E_i)\in\mathscr D$. Otherwise, $e$ was applied in reaching $E_i$, and so there exists $F_i \in \mathscr D$ from which $E_i$ is reachable.

Of course, without the definitions of $E_i$, $e$, $\mathscr C$, and $\mathscr D$, this isn't much use either. We're given a configuration $C$. $e$ is by assumption an event applicable to $C$. $\mathscr C$ is the set of all configurations reachable from a given configuration $C$ where event $e$ has not been applied. $\mathscr D$ is all the configurations you get when you apply $e$ to the configurations in $\mathscr C$. $E_i$ is a(n $i$-valent) configuration reachable from $C$.

The first paragraph of the lemma shows that $e$ is applicable to all configurations in $\mathscr C$. Given this, if $E_i\notin \mathscr C$, then, by definition of $\mathscr C$ and the fact that $E_i$ is reachable from $C$, $E_i$ must be reachable via some configuration that applies $e$. Any run from $C$ to $E_i$ must have a first time where $e$ is applied. Any configuration before that is in $\mathscr C$ by definition. The configuration at the point $e$ is applied is in $\mathscr D$ by definition and the fact that $e$ is applicable to all configurations in $\mathscr C$. That configuration is $F_i$.

Again, your second quote lacks context. The "such steps" mentioned in it are the steps from a bivalent configuration to a univalent configuration. Avoiding "such steps" is only relevant if we must start from a bivalent initial configuration, which is what Lemma 2 establishes. Lemma 2 critically depends on allowing up to one faulty process. If the protocol did not have to work correctly in the face of up to one faulty process, then Lemma 2 would not apply.

The idea of Lemma 2 is that if we have two configurations that differ only in how the input register is set for a single process, then if they can both reach a decision without ever executing that process (i.e. that process is faulty), then they must reach the same decision, since, once we remove that process, they have the same set of processes with the same initial state receiving the same messages. If we assume there are no bivalent initial configurations (for contradiction), then by partial correctness it is necessarily the case that there are two configurations that would make different decisions, but differ from each other only by a single process' input. Thus a contradiction.

It's trivial to make a consensus protocol when no processes are faulty. Simply pick one process (via setting its initial state appropriately) to be the Decider. It copies its input to its output. All other processes do nothing. Clearly this scheme won't work if the Decider is faulty.

  • $\begingroup$ Ah, OK, I get the first part now. For the second part, is the point that if there's no faulty process, there need not be a bivalent initial configuration? $\endgroup$ Jun 1, 2018 at 5:33
  • $\begingroup$ Not quite. It's not that some process has to be faulty in any run, the point is that we are only considering (hypothetical) protocols that will work if at most process is faulty. The protocol I described in the last paragraph does not have the property that a bivalent initial configuration exists, but it also doesn't meet the authors' definition of "totally correct in spite of one fault" because there is an admissible run that is not deciding, namely the one where the Decider process takes no steps. $\endgroup$ Jun 1, 2018 at 5:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.