Byzantine agreement with a minimum number of messages both in the faultless and worst case
Birgit Baum-Waidner · 2002
A known lower bound for the number of messages in the worst case for all synchronous authenticated Byzantine agreement protocols (BAPs) for any t < m is /spl Omega/(m + t/sup 2/). A BAP is given for any t < m which achieves this bound and minimizes the number of messages for the faultless case to m-1. This shows that minimizing the number of messages in the faultless ase can be achieved without an additional amount of messages. If the faultless case is the usual case, a high number of messages will no longer be a counterargument against the employment of BAPs in practice.