|Synchrony|| $f<n$ is possible
$f+1$ round executions must exist
|$f \geq n/2$ is impossible|| $f<n/2$ possible with PKI / PoW
$f \geq n/3$ impossible without PKI/PoW
|Partial Synchrony||$f \geq n/2$ is impossible||$f<n/2$ is possible|| $f<n/3$ is possible
$f \geq n/3$ is impossible
|Asynchrony||non terminating executions must exist||$f<n/2$ possible in $O(1)$ expected||$f<n/3$ possible in $O(1)$ expected|
Here $n$ is the number of parties, and $f$ is the number of parties that the adversarial threshold. Recall that Synchrony $\subseteq$ Partial Synchrony $\subseteq$ Asynchrony. Similarly that Crash $\subseteq$ Omission $\subseteq$ Byzantine. Therefore,
- Any upper bound holds if we go down and/or to the left. e.g., the $O(1)$ expected round upper bounds under asynchrony also hold in partial synchrony and synchrony.
- Any lower bound holds if we go up and/or to the right. e.g., the impossibility of $f \geq n/3$ carries 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.