Problem Description
The consensus problem requires agreement among a number of processes for a single data value. Some of the processes may fail or be unreliable in other ways, so consensus protocols must be fault tolerant. The processes must somehow put forth their candidate values, communicate with one another, and agree on a single consensus value.
One approach to generating consensus is for all processes to agree on a majority value. For n processes, a majority value will require at least n/2 + 1 votes to win. However one or more faulty processes may skew the resultant outcome such that consensus may not be reached or reached incorrectly.
Protocols that solve consensus problems are designed to deal with limited numbers of faulty processes. These protocols must satisfy a number of requirements to be useful. For instance a trivial protocol could have all processes output binary value 1. This is not useful and thus the requirement is modified such that the output must somehow depend on the input. That is, the output value of a consensus protocol must be the input value of some process. Another requirement is that a process may decide upon and output a value only once and this decision is irrevocable. A process is called correct in an execution if it does not experience a failure. A consensus protocol tolerating halting failures must satisfy the following properties
- Termination
- Every correct process decides some value.
- Validity
- If all correct processes propose the same value, then all correct processes decide .
- Integrity
- every correct process decides at most one value, and if it decides some value, then must have been proposed by some process.
- Agreement
- Every correct process must agree on the same value.
A protocol that can correctly guarantee consensus amongst n processes of which at most t fail is said to be t-resilient.
In evaluating the performance of consensus protocols two factors of interest are running time and message complexity. Running time is given in Big O notation in the number of rounds of message exchange as a function of some input parameters (typically the number of processes and/or the size of the input domain). Message complexity refers to the amount of message traffic that is generated by the protocol. Other factors may include memory usage and the size of messages.
Read more about this topic: Consensus (computer Science)
Famous quotes containing the words problem and/or description:
“I don’t have any problem with a reporter or a news person who says the President is uninformed on this issue or that issue. I don’t think any of us would challenge that. I do have a problem with the singular focus on this, as if that’s the only standard by which we ought to judge a president. What we learned in the last administration was how little having an encyclopedic grasp of all the facts has to do with governing.”
—David R. Gergen (b. 1942)
“It is possible—indeed possible even according to the old conception of logic—to give in advance a description of all ‘true’ logical propositions. Hence there can never be surprises in logic.”
—Ludwig Wittgenstein (1889–1951)