Access Restriction

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

   Open content in new tab
Source: ACM Digital Library