Consensus is a problem in distributed computing that is of singular importance. It is in some senses an abstraction of the problem of synchronization of distributed resources, and it suffices to demonstrate a protocol that achieves consensus--or to show that consensus cannot be achieved under given conditions by any algorithm--to prove that the distributed system has certain innate characteristics with regard to synchronicity--or lack thereof--that are not simply artifacts of the algorithm used.

Formally, consensus may be described as a decision problem for n processes, some of which may be faulty (usually meaning that they have crashed). Each process starts with an input value that is not known to the other processes, and each process may take its own time in computing its output value, but at the end, every process must return the same output value. In order to rule out trivial solutions and non-solutions, we say...