Consensus in distributed systems cannot be asynchronous due to the FLP Result: there is no deterministic consensus algorithm that is guaranteed to terminate in an asynchronous crash-stop system model
This holds even if
Similar to tradeoffs made in the CAP Theorem, when under attack, we need to choose between
- safety
- consistency
- liveness/availability
In an async system, a crashed process is indistinguishable from a slow one. If you wait for it, you might wait forever. If you proceed without it, its delayed messages could have changed the outcome.
This can somewhat be abated by weakening any of the assumptions above:
- partial synchrony, any crashed node eventually recovers and becomes timely
- randomized protocols (see: HoneyBadgerBFT, Nakamoto consensus)
- failure detectors