| 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, 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.
Acknowledgments: many thanks to Kartik Nayak for help with this post!
Your thoughts on twitter.