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

http://hnr.dnsalias.net/wordpress/?p=49

by 13ren • 18 years ago

4 5 18 years ago

hnr.dnsalias.net

Retric2• 18 years ago

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.

HenryR2• 18 years ago

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.

Retric2• 18 years ago

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.

Hexstream• 18 years ago

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.

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

Related Stories