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:
“It would be easy ... to regard the whole of world 3 as timeless, as Plato suggested of his world of Forms or Ideas.... I propose a different view—one which, I have found, is surprisingly fruitful. I regard world 3 as being essentially the product of the human mind.... More precisely, I regard the world 3 of problems, theories, and critical arguments as one of the results of the evolution of human language, and as acting back on this evolution.”
—Karl Popper (1902–1994)
“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)
“Hats have never at all been one of the vexing problems of my life, but, indifferent as I am, these render me speechless. I should think a well-taught and tasteful American milliner would go mad in England, and eventually hang herself with bolts of green and scarlet ribbon—the favorite colour combination in Liverpool.”
—Willa Cather (1876–1947)