Byzantine Agreement with a Minimum Nm Both in the Faultless and Worst Case
Birgit Baum-Waidner · 1993
Abslrars It is known that all synchronous authenticated Byzantine agreement protocols need am+$) messages in the worst case (where m is the number of nodes and t the maximum number of fau@ nodes). Most known protocols kep low the worst case number of phes and, as a consequence, need such message overhead even in the faultless case. However, a high number of messages, even in the faultless case, is the main obstacle for practical application of most previous protocols. If fmlts occur very rarely, protocols which minimize the faultless case are required so that messages for tolerating faults will not be sent in the faultless case. For the first time, a protocol is presented for any tem which minimizes the faultless case number of messages to m-I and nevertheless the worst case to the known bound of o(m+?) messages, at the expense of 0(m+2') phases. so not only the faultless case but also the worst case each manage with the minimum possible number of messages, respectively.