NDLI: Bounds on information exchange for Byzantine agreement

Content Provider	ACM Digital Library
Author	Dolev, Danny Reischuk, Rdiger
Copyright Year	1985
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.
Starting Page	191
Ending Page	204
Page Count	14
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2455.214112
Journal	Journal of the ACM (JACM)
Volume Number	32
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1985-01-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the composition of authenticated Byzantine Agreement

Early stopping in Byzantine agreement

Byzantine Agreement in Expected Polynomial Time

Bounds on Storage for Consecutive Retrieval

The Weak Byzantine Generals Problem

Lower Bounds on Merging Networks

Capacity Bounds for Multiresource Queues

On Some Error Bounds of Givens

Bounds for the String Editing Problem

Bounds on information exchange for Byzantine agreement

Similar Documents

On the composition of authenticated Byzantine Agreement

Early stopping in Byzantine agreement

Byzantine Agreement in Expected Polynomial Time

Bounds on Storage for Consecutive Retrieval

The Weak Byzantine Generals Problem

Lower Bounds on Merging Networks

Capacity Bounds for Multiresource Queues

On Some Error Bounds of Givens

Bounds for the String Editing Problem

Bounds on information exchange for Byzantine agreement