FLP86's famous proof regarding impossibility of async distributed processes with a single fault assumes in the proof of the third lemma the existence of an event $e'$ such that the neighbor configurations $C_0$ and $C_1$ can be related as

$C_1 = e'(C_0)$.

I don't get how this is possible, as it seems to me like $e'$ carries out a state transition from a 0-valent configuration to a 1-valent configuration. In addition to this being counter intuitive the proof of case 1 of lemma 3 clearly states that any successor of a 0-valent configuration has to be a 0-valent configuration. What am I missing here?


1 Answer 1


At least in this part of the article, the character C is used for bivalent configurations. The index $0$ for the bivalent $C_0$ was chosen simply because $e(C_0)$ is 0-valent and the index $1$ in $C_1$ was chosen because $e(C_1)$ is 1-valent, even though $C_0$ and $C_1$ are bivalent neighbors (when applying $e'$).


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.