Thumbnail
Access Restriction
Subscribed

Author Bracha, Gabriel ♦ Toueg, Sam
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 A consensus protocol enables a system of $\textit{n}$ asynchronous processes, some of which are faulty, to reach agreement. There are two kinds of faulty processes: fail-stop processes that can only die and malicious processes that can also send false messages. The class of asynchronous systems with fair schedulers is defined, and consensus protocols that terminate with probability 1 for these systems are investigated. With fail-stop processes, it is shown that $⌈(\textit{n}$ + 1)/2⌉ correct processes are necessary and sufficient to reach agreement. In the malicious case, it is shown that $⌈(2\textit{n}$ + 1)/3⌉ correct processes are necessary and sufficient to reach agreement. This is contrasted with an earlier result, stating that there is no consensus protocol for the fail-stop case that always terminates within a bounded number of steps, even if only one process can fail. The possibility of reliable broadcast (Byzantine Agreement) in asynchronous systems is also investigated. Asynchronous Byzantine Agreement is defined, and it is shown that $⌈(2\textit{n}$ + 1)/3⌉ correct processes are necessary and sufficient to achieve it.
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-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 32
Issue Number 4
Page Count 17
Starting Page 824
Ending Page 840


Open content in new tab

   Open content in new tab
Source: ACM Digital Library