Solvability Results For Some Agreement Problems
There is a t-resilient anonymous synchronous protocol which solves the Byzantine Generals problem, problem iff t/n < 1/3 and the Weak Byzantine Generals case where t is the number of failures and n is the number of processes.
For a system of 3 processors with one of them Byzantine, there is no solution for the consensus problem in a synchronous message passing model with binary inputs.
In a fully asynchronous system there is no consensus solution that can tolerate one or more crash failures even when only requiring the non triviality property . This result is sometimes called the FLP impossibility proof. The authors Michael J. Fischer, Nancy Lynch, and Mike Paterson were awarded a Dijkstra Prize for this significant work. The FLP result does not state that consensus can never be reached: merely that under the model's assumptions, no algorithm can always reach consensus in bounded time. In practice it is highly unlikely to occur.
Read more about this topic: Consensus (computer Science)
Famous quotes containing the words results, agreement and/or problems:
“Being a parent is unlike any previous job—the results of any one action are not clearly visible for a long time, if at all.”
—Anonymous Mother. As quoted in Between Generations by Ellen Galinsky, ch. 2 (1981)
“A marriage based on full confidence, based on complete and unqualified frankness on both sides; they are not keeping anything back; there’s no deception underneath it all. If I might so put it, it’s an agreement for the mutual forgiveness of sin.”
—Henrik Ibsen (1828–1906)
“I rarely speak about God. To God, yes. I protest against Him. I shout at Him. But to open a discourse about the qualities of God, about the problems that God imposes, theodicy, no. And yet He is there, in silence, in filigree.”
—Elie Wiesel (b. 1928)