Search IconIcon to open search

33% Impossibility Result

Last updated Jul 3, 2022 Edit Source

In general (assuming a partially-synchronous system model), a protocol can achieve safety all the time and additionally liveness in synchronous conditions if and only if $n \geq 3f + 1$ (equivalently, $f < \frac n 3$)

This result holds despite the assumption of PKI (unlike the PSL-FLM result), so this bound must be driven by the possibility of unbounded message delays.


  1. We can’t wait indefinitely for all nodes to respond (one valid strategy for Byzantine nodes is to never respond, even after GST) so realistically we can only wait to hear from $n - f$ nodes before deciding on the next possible action
  2. But we can’t say for certain the $f$ nodes are actually Byzantine (they could be honest nodes that are congested), thus of the $n - f$ nodes, more than half should be honest, $f < \frac 1 2 (n -f)$ or equivalently $f < \frac n 3$

Interactive Graph