Thumbnail
Access Restriction
Subscribed

Author MostxEfaoui, Achour ♦ Moumen, Hamouma ♦ Raynal, Michel
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2015
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Asynchronous message-passing system ♦ Byzantine process ♦ Broadcast abstraction ♦ Common coin ♦ Consensus ♦ Distributed algorithm ♦ Optimal resilience ♦ Randomized algorithm ♦ Signature-free algorithm ♦ Simplicity
Abstract This article is on broadcast and agreement in asynchronous message-passing systems made up of $\textit{n}$ processes, and where up to $\textit{t}$ processes may have a Byzantine Behavior. Its first contribution is a powerful, yet simple, all-to-all broadcast communication abstraction suited to binary values. This abstraction, which copes with up to $\textit{t}$ < $\textit{n}/3$ Byzantine processes, allows each process to broadcast a binary value, and obtain a set of values such that (1) no value broadcast only by Byzantine processes can belong to the set of a correct process, and (2) if the set obtained by a correct process contains a single value $\textit{v},$ then the set obtained by any correct process contains $\textit{v}.$ The second contribution of this article is a new round-based asynchronous consensus algorithm that copes with up to $\textit{t}$ < $\textit{n}/3$ Byzantine processes. This algorithm is based on the previous binary broadcast abstraction and a weak common coin. In addition to being signature-free and optimal with respect to the value of $\textit{t},$ this consensus algorithm has several noteworthy properties: the expected number of rounds to decide is constant; each round is composed of a constant number of communication steps and involves $\textit{O}(\textit{n}2)$ messages; each message is composed of a round number plus a constant number of bits. Moreover, the algorithm tolerates message reordering by the adversary (i.e., the Byzantine processes).
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 2015-09-11
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 62
Issue Number 4
Page Count 21
Starting Page 1
Ending Page 21


Open content in new tab

   Open content in new tab
Source: ACM Digital Library