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:
“The restlessness that comes upon girls upon summer evenings results in lasting trouble unless it is speedily controlled. The right kind of man does not look for a wife on the streets, and the right kind of girl waits till the man comes to her home for her.”
—Sedalia Times (1900)
“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)
“I’m no good at being noble, but it doesn’t take much to see that the problems of three little people don’t amount to a hill of beans in this crazy world. Someday you’ll understand that.”
—Julius J. Epstein, U.S. screenwriter, Philip Epstein, screenwriter, Howard Koch, screenwriter, and Michael Curtiz. Rick Blaine (Humphrey Bogart)