Equivalency of Agreement Problems
Three agreement problems of interest are as follows.
- Terminating Reliable Broadcast
(Also known as The General's Problem) A collection of n processes, numbered from 0 to n - 1, communicate by sending messages to one another. Process 0 must transmit a value v to all processes such that
- If Process 0 is correct then every correct process receives v
- For any two correct processes, each process receives the same value
- Consensus
Formal requirements for a consensus protocol may include
Agreement - All correct processes must agree on the same value.
Weak Validity - If all correct processes receive the same input value, then they must all output that value.
Strong Validity - For each correct process, its output must be the input of some correct process.
Termination - All processes must eventually decide on an output value
- Weak Interactive Consistency
For n processes in a partially synchronous system (the system alternates between good and bad periods of synchrony), each process chooses a private value. The processes communicate with each other by rounds to determine a public value and generate a consensus vector with the following requirements
- If a correct process sends v, then all correct processes receive either v or nothing (integrity property)
- All messages sent in a round by a correct process are received in the same round by all correct processes (consistency property).
It can be shown that variations of these problems are equivalent in that the solution for a problem in one type of model may be the solution for another problem in another type of model. For example, a solution to the Weak Byzantine General problem in a synchronous authenticated message passing model leads to a solution for Weak Interactive Consistency. An interactive consistency algorithm can solve the consensus problem by having each process choose the majority value in its consensus vector as its consensus value.
Read more about this topic: Consensus (computer Science)
Famous quotes containing the words agreement and/or problems:
“The methodological advice to interpret in a way that optimizes agreement should not be conceived as resting on a charitable assumption about human intelligence that might turn out to be false. If we cannot find a way to interpret the utterances and other behaviour of a creature as revealing a set of beliefs largely consistent and true by our standards, we have no reason to count that creature as rational, as having beliefs, or as saying anything.”
—Donald Davidson (b. 1917)
““What we know, is a point to what we do not know.” Open any recent journal of science, and weigh the problems suggested concerning Light, Heat, Electricity, Magnetism, Physiology, Geology, and judge whether the interest of natural science is likely to be soon exhausted.”
—Ralph Waldo Emerson (1803–1882)