On the message complexity of binary Byzantine Agreement under crash failures

Eugene S. Amdur, Samuel M. Weber and Vassos Hadzilacos

The binary Byzantine Agreement problem requires $n-1$ receivers to agree on the binary value broadcast by a sender even when some of these $n$ processes may be faulty. We investigate the message complexity of protocols that solve this problem in the case of crash failures. In particular, we derive matching upper and lower bounds on the total, worst and average case number of messages needed in the failure-free executions of such protocols. More specifically, we prove that any protocol that tolerates up to $t$ faulty processes requires a total of at least $n+t-1$ messages in its failure-free executions --- and, therefore, at least $\lceil (n+t-1)/2\rceil$ messages in the worst case and $\min(P_0,P_1)\cdot(n+t-1)$ messages in the average case, where $P_v$ is the probability that the value of the bit that the sender wants to broadcast is $v$. We also give protocols that solve the problem using only the minimum number of messages for these three complexity measures. These protocols can be implemented by using 1-bit messages. Since a lower bound on the number of messages is also a lower bound on the number of message bits, this means that the above tight bounds on the number of messages are also tight bounds on the number of message bits.