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:
“I have no doubt that it was a principle they fought for, as much as our ancestors, and not to avoid a three-penny tax on their tea; and the results of this battle will be as important and memorable to those whom it concerns as those of the battle of Bunker Hill, at least.”
—Henry David Thoreau (1817–1862)
“Culture is the tacit agreement to let the means of subsistence disappear behind the purpose of existence. Civilization is the subordination of the latter to the former.”
—Karl Kraus (1874–1936)
“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)