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 ideal reasoner,” he remarked, “would, when he had once been shown a single fact in all its bearings, deduce from it not only all the chain of events which led up to it but also all the results which would follow from it.””
—Sir Arthur Conan Doyle (1859–1930)
“The doctrine of those who have denied that certainty could be attained at all, has some agreement with my way of proceeding at the first setting out; but they end in being infinitely separated and opposed. For the holders of that doctrine assert simply that nothing can be known; I also assert that not much can be known in nature by the way which is now in use. But then they go on to destroy the authority of the senses and understanding; whereas I proceed to devise helps for the same.”
—Francis Bacon (1560–1626)
“The three great problems of this century, the degradation of man in the proletariat, the subjection of women through hunger, the atrophy of the child by darkness.”
—Victor Hugo (1802–1885)