HNHacker News
TopNewBestAskShowJobs

HenryR

602 karma · joined August 13, 2008

submissionscomments
HenryR··on Tour of 1985 formal proof of a limit on asynchronous processes (won Dijkstra award)
The impossibility proof actually stands if you require only one processor to decide (this is mentioned explicitly in the paper). So X out of N is just as hard as N out of N.

Some methods for ensuring a total ordering on message delivery require a round of consensus. Google's chubby lock service requires five servers out of five to achieve consensus. Database commit requires (at least) majority consensus if you're using quorums.

You're right to argue that practically this result doesn't really affect anything in the sense that you can fake synchrony with sufficiently large timeouts, but at the same time systems that are using hard core distributed algorithms such as Paxos are highly critical and it makes a lot of sense to be aware of what is possible and what is not.

HenryR··on Tour of 1985 formal proof of a limit on asynchronous processes (won Dijkstra award)
That's arguable - you certainly need all nodes to agree in lots of applications. And if you add a maximum time for computation, where do you set the line? Especially in mobile networks, computations can take a wildly varying length of time.
← PreviousPage 3 of 3