Consensus | Research & Encyclopedia Articles

Consensus

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 that the consensus protocol must, in order to be considered correct, fulfill all of the following conditions:

• Consistency--all non-faulty processes must return the same output value.
• Termination--every non-faulty process must return an output value within some finite time.
• Validity--if every process is given the same input value, then every process must return that very value as output.

The validity condition is essential, as otherwise it is possible to come up with trivial solutions where all processes disregard their inputs and choose some arbitrary fixed output.

It is also possible to show that any protocol for solving consensus on the binary input values 0 and 1 can solve it for an input from an arbitrarily large set. For this reason, it is common to specify that the input be from the set (0, 1), as this results in no loss of generality, and yet sometimes makes reasoning about consensus protocols easier.

In contemporary research literature, the greatest interest lies in consensus protocols that allow processes to communicate through some shared object. A particular desirable requirement for consensus protocols is that they be wait-free, i.e., that every process terminate after a finite number of its own steps, rather than having to wait for other processes that may be arbitrarily slower than it. Synchronization without mutual exclusion is isomorphic to wait-free consensus; any protocol that does the one will do the other.

Likewise, consideration of the consensus problem has shown that having a shared memory between the processes is equivalent to atomic broadcast, i.e., to the availability and use of a broadcast protocol where each process can send a direct message to every other, with every message sent being received either by all processes or by none at all (no case being possible of a message reaching some processes but not others). The atomic broadcast primitive implies a high level of synchronism in a distributed system, and it is relatively easy to achieve consensus given it. The interesting question is what happens when one does not have atomic broadcast, but wishes to achieve consensus nonetheless--what, if anything, can be done then? There were major attempts in the 1980s to come up with protocols to achieve consensus in asynchronous systems while only using weaker primitives, but a seminal 1985 paper by Fischer, Lynch, and Paterson struck a major blow to such efforts by showing that consensus cannot be achieved on a fully asynchronous system even if just one process is faulty. Intuitively, we may understand this result by noting that in a fully asynchronous system, a process may take arbitrarily long to decide its output, or to respond to requests from other processes; there is thus no way to distinguish a crashed process from one that is just arbitrarily slow, and thus any protocol one might suggest would fail in this situation.

A related problem is the use of suitable objects, such as read/write registers, or test-and-swap registers, to achieve consensus among processes. With each such object we may associate a consensus number, which is the number of processes for which the object can be applied in a protocol to solve consensus. An important 1991 paper by Herlihy raised the question: what is the consensus number of such commonly used hardware primitives as read/write registers, and how may we construct objects having a larger consensus numbers, using those with smaller consensus numbers as building blocks? Herlihy also showed in that paper that there are certain universal objects from which one may construct any other consensus objects; however, unfortunately, read/write registers have a consensus number of 1, which means that they can only "solve" consensus in the trivial case where there is only one process to begin with; it is also impossible to construct objects with higher consensus numbers using read/write registers (or from any objects with smaller ones). In other words, commonly used read/write registers cannot be used as shared objects for solving consensus in any useful case.

In some cases, it is useful to look at consensus as a game being played between a group of processes and an adversary. The adversary is a fictional entity introduced into the discussion to simulate the (worst-case) conditions under which the consensus protocol may be required to operate. The powers of the adversary correspond to the difficulties we can or wish to prepare for in the protocol. For example, if it is required for a consensus protocol to be robust against arbitrary changes in processes' speeds, then we speak of an adversary who can delay processes arbitrarily to hold the protocol to the worst possible disadvantage.

Although it is known that consensus cannot be solved deterministically in certain cases, such as using only read/write registers, it turns out that probabilistic algorithms do exist where it can be solved in most cases. The lack of certainty may bother the purist, but in fact, probabilistic algorithms do quite well in practice, and often give a much better average performance than deterministic ones.