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:
“No one can doubt, that the convention for the distinction of property, and for the stability of possession, is of all circumstances the most necessary to the establishment of human society, and that after the agreement for the fixing and observing of this rule, there remains little or nothing to be done towards settling a perfect harmony and concord.”
—David Hume (1711–1776)
“The question of place and climate is most closely related to the question of nutrition. Nobody is free to live everywhere; and whoever has to solve great problems that challenge all his strength actually has a very restricted choice in this matter. The influence of climate on our metabolism, its retardation, its acceleration, goes so far that a mistaken choice of place and climate can not only estrange a man from his task but can actually keep it from him: he never gets to see it.”
—Friedrich Nietzsche (1844–1900)