Consensus is a problem ^[1] in distributed computing that encapsulates the task of group agreement in the presence of faults.^[2] In particular, any process in the group may crash at any time. Consensus is fundamental to core techniques in fault tolerance, such as state machine replication. Distributed computing is a programming paradigm focusing on designing distributed, open, scalable, transparent, fault tolerant systems. ... In computing, a process is a running instance of a program, including all variables and other states. ... In computer science, Fault-tolerance is the property of a computer system to continue operation at an acceptable quality, despite the unexpected occurrence of hardware or software failures. ...

Problem Description

A process is called "correct" if it does not fail at any point during its execution. Unlike Terminating Reliable Broadcast, the typical Consensus problem does not label any single process as a "sender". Every process "proposes" a value; the goal of the protocol is for all correct processes to choose a single value from among those proposed. A process may perform many I/O operations during protocol execution, but must eventually "decide" a value by passing it to the application on that process that invoked the Consensus protocol. For the economic use of the term, see Input-output model. ...

Valid consensus protocols must provide important guarantees to all processes involved. All correct processes must eventually decide the same value, for example, and that value must be one of those proposed. A correct process is therefore guaranteed that the value it decides was also decided by all other correct processes, and can act on that value accordingly.

More precisely, a Consensus protocol must satisfy the four formal properties below.

• Termination: every correct process decides some value.
• Validity: if all processes propose the same value v, then every correct process decides v.
• Integrity: every correct process decides at most one value, and if it decides some value v, then v must have been proposed by some process.
• Agreement: if a correct process decides v, then every correct process decides v.

The possibility of faults in the system makes these properties more difficult to satisfy. A simple but invalid Consensus protocol might have every process broadcast its proposal to all others, and have a process decide on the smallest value received. Such a protocol, as described, does not satisfy Agreement if faults can occur: if a process crashes after sending its proposal to some processes, but before sending it to others, then the two sets of processes may decide different values.

Impossibility

Please help improve this article by expanding this section. Further information might be found on the talk page or at requests for expansion. Please remove this message once the section has been expanded.

Image File history File links Wiki_letter_w. ...

Important Consensus Protocols

Please help improve this article by expanding this section. Further information might be found on the talk page or at requests for expansion. Please remove this message once the section has been expanded.

Image File history File links Wiki_letter_w. ...

Context in Distributed Computing

Please help improve this article by expanding this section. Further information might be found on the talk page or at requests for expansion. Please remove this message once the section has been expanded.

Image File history File links Wiki_letter_w. ...

References

1. ^ Olfati-Saber, Reza (2004). Consensus Problems in Networks of Agents with Switching Topology and Time-Delays. Retrieved on 2004-09-01.
2. ^ Alvisi, Lorenzo (2006). Consensus and Reliable Broadcast. Retrieved on 2006-05-21.