Connectivity requirements for Byzantine Agreement under restricted types of failures

Vassos Hadzilacos

We investigate the problem of reaching Byzantine Agreement in arbitrary networks where both processors and communication links are subject to omission or stopping faults. For the case of deterministic, synchronous algorithms we give a necessary and sufficient condition relating the solvability of the problem to the connectivity of the network. In particular, we show that an algorithm resilient to at most $t$ faulty processors and $k$ faulty links subject to omission or stopping faults exists, if and only if the network has a connectivity pair $(t',k') > (t,k)$. For arbitrary faults, the condition becomes $(t',k') > (2t,2k)$.