Impossibility of Consensus: the FLP's Result
The ideas of the proof
The proof of this result relies on the tagging the execution graph of a given protocol that claims
solving the binary consensus problem. The binary consensus problem is a restriction of the more
generic consensus problem, where one assumes that potential initial values are restricted to
the set {0,1}. Each node of the graph is tagged with a set called its valence. The valence of a node
is the set of values that can be decided starting from this node (global state). Thus, by definition
of the consensus problem, this set is a non empty subset of the set {0,1}. The entire tagging of the
graph exhibits nice properties that can be exploited to derive a contradiction, showing that
no deterministic protocol can solve binary consensus, and by extension consensus.
Going into the details
I have written some slides that describe in a detail way the proof of FLP. These slides have been presented
for a lecture to the Lasid's members at the Federal University of Bahia
(Brazil)
Frédéric Tronel
Last modified: Fri Oct 12 10:56:33 MEST 2001
