### Bounds on information exchange for Byzantine agreementBounds on information exchange for Byzantine agreement

Access Restriction
Subscribed

 Author Dolev, Danny ♦ Reischuk, Rdiger Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1985 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract Byzantine Agreement has become increasingly important in establishing distributed properties when errors may exist in the systems. Recent polynomial algorithms for reaching Byzantine Agreement provide us with feasible solutions for obtaining coordination and synchronization in distributed systems. In this paper the amount of information exchange necessary to ensure Byzantine Agreement is studied. This is measured by the total number of messages the participating processors have to send in the worst case. In algorithms that use a signature scheme, the number of signatures appended to messages are also counted.First it is shown that $&OHgr;(\textit{nt})$ is a lower bound for the number of signatures for any algorithm using authentication, where $\textit{n}$ denotes the number of processors and $\textit{t}$ the upper bound on the number of faults the algorithm is supposed to handle. For algorithms that reach Byzantine Agreement without using authentication this is even a lower bound for the total number of messages. If $\textit{n}$ is large compared to $\textit{t},$ these bounds match the upper bounds from previously known algorithms. For the number of messages in the authenticated case we prove the lower bound $&OHgr;(\textit{n}$ + $\textit{t}2).$ Finally algorithms that achieve this bound are presented. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1985-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 32 Issue Number 1 Page Count 14 Starting Page 191 Ending Page 204

#### Open content in new tab

Source: ACM Digital Library