Tour of 1985 formal proof of a limit on asynchronous processes (won Dijkstra award) | Hacker News Reader

Tour of 1985 formal proof of a limit on asynchronous processes (won Dijkstra award)

hnr.dnsalias.net

4 points13ren5 comments

Interesting but useless add a maximum time for computation or not requiring all nodes to agree and it's trivial. The logic is still somewhat interesting so feel free to read it but don't forget it's a meaningless result for the real world.

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.

Such as?

Note: There are some interesting cryto systems such that X out of N nodes need to agree to do something. So you can send off the blackmail if 8 out of 10 people think you died etc. Because of this you can add a lot redundancy to most systems without causing problems.

Edit: Maximum time might be 50% longer than 80% of your nodes took it does not need to be a fixed number.

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.

I'm not someone who overemphasises the value of credentials but I wouldn't dismiss this result so eagerly if it won a serious award and is considered an important result by more knowledgeable people than me.

Reply on news.ycombinator.com