Consensus (computer Science) - Models of Computation

Models of Computation

There are two types of failures a process may undergo, a crash failure, or a Byzantine failure. A crash failure occurs when a process abruptly stops and does not resume. Byzantine failures are failures in which absolutely no conditions are imposed. For example they may occur as a result of the malicious actions of an adversary. A process that experiences a Byzantine failure may send contradictory or conflicting data to other processes, or it may also sleep and then resume activity after a lengthy delay. Of the two types of failures, Byzantine failures are far more disruptive. Thus a consensus protocol tolerating Byzantine failures must be resilient to every possible error that can occur.

A stronger version of consensus tolerating Byzantine failures is given below

Termination

Every correct process decides some value.

Validity

If all correct processes propose the same value v, then all correct processes decide v.

Integrity

If a correct process decides v, then v must have been proposed by some correct process.

Agreement

Every correct process must agree on the same value.

Varying models of computation may define a consensus problem. Some models may deal with fully connected graphs while others may deal with rings and trees. Asynchronous versus synchronous models for message passing may be considered. In some models message authentication is allowed whereas in others processes are completely anonymous. Shared memory models in which processes communicate by accessing objects in shared memory are also an important area of research.

A special case of the consensus problem called binary consensus restricts the input and hence the output domain to a single binary digit {0,1}. When the input domain is large relative to the number of processes, for instance an input set of all the natural numbers, it can be shown that consensus is impossible in a synchronous message passing model.

While real world communications are often inherently asynchronous it is more practical and useful to model synchronous systems. In a fully asynchronous message-passing distributed system in which one process may have a halting failure, it has been proved that consensus is impossible. However, this impossibility result derives from a worst case scenario of a process schedule which is highly unlikely. In reality, process scheduling has a degree of randomness.

In an asynchronous model some forms of failures can be handled by a synchronous consensus protocol. For instance, the loss of a communication link may be modeled as a process which has suffered a Byzantine failure.

In synchronous systems it is assumed that all communications proceed in rounds. In one round a process may send all the messages it requires while receiving all messages from other processes. In this manner no message from one round may influence any messages sent within the same round.