Hacker News new | past | comments | ask | show | jobs | submit login
Impossibility of Distributed Consensus with One Faulty Process (1985) [pdf] (csail.mit.edu)
16 points by ipnon 15 days ago | hide | past | favorite | 4 comments

The theorem only applies to perfectly asynchronous systems, which assume that algorithms are deterministic and have no clocks. We must introduce imperfect heuristics like timeouts in order to conclude nodes have crashed by deduction and be able to reach consensus in concrete distributed systems.

This paper is referenced in chapter 9 (Consistency and Consensus) of "Designing Data-Intensive Applications" by Martin Kleppmann.

I'm not sure what exactly were you trying to argue against. Pretty much all real world distributed systems are perfectly asynchronous, don't have perfect clocks perfectly synchronized to rely on them, don't have bug-free real-time algorithms, OS and hardware, etc. So real world is exactly where the paper applies, i.e. it is impossible to guarantee consensus in bounded time. Sure, with large enough bound and large enough quorums you can get very high probability of achieving it in bounded time, but never 100%.

This is what I was trying to say, thanks.

I wrote a piece about this paper a few years back.


Tldr: Romeo and Juliet was a much earlier distributed system impossibility result.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact