NDLI: Early stopping in Byzantine agreement

Content Provider	ACM Digital Library
Author	Dolev, Danny Reischuk, Ruediger Strong, H. Raymond
Copyright Year	1990
Abstract	Two different kinds of Byzantine Agreement for distributed systems with processor faults are defined and compared. The first is required when coordinated actions may be performed by each participant at different times. This kind is called Simultaneous Byzantine Agreement (SBA).This paper deals with the number of rounds of message exchange required to reach Byzantine Agreement of either kind (BA). If an algorithm allows its participants to reach Byzantine agreement in every execution in which at most $\textit{t}$ participants are faulty, then the algorithm is said to tolerate $\textit{t}$ faults. It is well known that any BA algorithm that tolerates $\textit{t}$ faults (with $\textit{t}$ < $\textit{n}$ - 1 where $\textit{n}$ denotes the total number of processors) must run at least $\textit{t}$ + 1 rounds in some execution. However, it might be supposed that in executions where the number $\textit{f}$ of actual faults is small compared to $\textit{t},$ the number of rounds could be correspondingly small. A corollary of our first result states that (when $\textit{t}$ < $\textit{n}$ - 1) any algorithm for SBA must run $\textit{t}$ + 1 rounds in some execution where there are no faults. For EBA (with $\textit{t}$ < $\textit{n}$ - 1), a lower bound of $min(\textit{t}$ + $1,\textit{f}$ + 2) rounds is proved. Finally, an algorithm for EBA is presented that achieves the lower bound, provided that $\textit{t}$ is on the order of the square root of the total number of processors.
Starting Page	720
Ending Page	741
Page Count	22
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/96559.96565
Journal	Journal of the ACM (JACM)
Volume Number	37
Issue Number	4
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1990-10-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

Bounds on information exchange for Byzantine agreement

Byzantine Agreement in Expected Polynomial Time

On the composition of authenticated Byzantine Agreement

The Weak Byzantine Generals Problem

From immediate agreement to eventual agreement: early stopping agreement protocol for dynamic networks with malicious faulty processors

Reaching Agreement in the Presence of Faults

Reaching approximate agreement in the presence of faults

Self-stabilizing clock synchronization in the presence of Byzantine faults

Breaking the $O(n^{2})$ bit barrier: Scalable byzantine agreement with an adaptive adversary

Early stopping in Byzantine agreement

Similar Documents

Bounds on information exchange for Byzantine agreement

Byzantine Agreement in Expected Polynomial Time

On the composition of authenticated Byzantine Agreement

The Weak Byzantine Generals Problem

From immediate agreement to eventual agreement: early stopping agreement protocol for dynamic networks with malicious faulty processors

Reaching Agreement in the Presence of Faults

Reaching approximate agreement in the presence of faults

Self-stabilizing clock synchronization in the presence of Byzantine faults

Breaking the $O(n^{2})$ bit barrier: Scalable byzantine agreement with an adaptive adversary

Early stopping in Byzantine agreement