| Crash | Omission | Byzantine | |
|---|---|---|---|
| Synchrony |  $f<n$ is possible  $f+1$ round executions must exist |
 $f \geq n/2$ is impossible |
$f<n/2$ possible with PKI / possible with PoW FLM: $f \geq n/3$ impossible without PKI/PoW |
| Partial Synchrony | CAP: $f\geq n/2$ is impossible |
Paxos: $f<n/2$ is possible |
$f<n/3$ is possible DLS: $f \geq n/3$ is impossible |
| Asynchrony | FLP: non-terminating executions must exist |
$f<n/2$ possible in $O(1)$ expected rounds |
$f<n/3$ possible in $O(1)$ expected rounds |
Here $n$ is the number of parties, and $f$ is the number of parties that the adversary can corrupt. Recall that Synchrony $\subseteq$ Partial Synchrony $\subseteq$ Asynchrony. Similarly, recall that Crash $\subseteq$ Omission $\subseteq$ Byzantine. Therefore,
- Any upper bound holds if you go up and/or to the left in the table. e.g., the $O(1)$ expected round upper bounds under asynchrony also hold in partial synchrony and in synchrony.
- Any lower bound holds if you go down and/or to the right in the table. e.g., the impossibility of $f \geq n/3$ with Byzantine adversaries in partial synchrony carries over to asynchrony, and the $t+1$ round lower bound carries over from crash to omission and Byzantine.
Where is Dolev-Strong in this table?
The lower bounds in this table assume State Machine Replication, which requires uniform agreement under omission and provable agreement under Byzantine failures. If we relax these requirements, stronger resilience is achievable: with non-uniform omission $f<n$ is possible, and with non-provable Byzantine agreement (as in Dolev–Strong) $f<n$ is also possible.
Acknowledgments: many thanks to Kartik Nayak for help with this post!
Your thoughts on twitter.