# {B}yzantine Agreement Given Partial Broadcast

## Jeffrey Considine and Matthias Fitzi and Matthew Franklin and Leonid A. Levin and Ueli Maurer and David Metcalf

```
```This paper considers unconditionally secure protocols for reliable
broadcast among a set of $n$ players, where up to $t$ of the players
can be corrupted by a (Byzantine) adversary but the remaining
$h=n-t$ players remain honest. In the standard model with a
complete, synchronous network of bilateral authenticated
communication channels among the players, broadcast is achievable if
and only if $2n/h<3$.
We show that, by extending this model by the existence of partial
broadcast channels among subsets of $b$ players, global broadcast
can be achieved if and only if the number $h$ of honest players
satisfies $2n/h<b+1$. Achievability is demonstrated by protocols
with communication and computation complexities polynomial in the
size of the network, i.e., in the number of partial broadcast
channels. A respective characterization for the related consensus
problem is also given.