Access Restriction

Author Georgiou, Chryssis ♦ Gilbert, Seth ♦ Guerraoui, Rachid ♦ Kowalski, Dariusz R.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2013
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Gossip ♦ Adaptive versus oblivious adversary ♦ Asynchrony ♦ Complexity ♦ Consensus ♦ Epidemic ♦ Randomization
Abstract We study the complexity of $\textit{gossip}$ in an asynchronous, message-passing fault-prone distributed system. We show that an $\textit{adaptive}$ adversary can significantly hamper the spreading of a rumor, while an $\textit{oblivious}$ adversary cannot. The algorithmic techniques proposed in this article can be used for improving the message complexity of distributed algorithms that rely on an all-to-all message exchange paradigm and are designed for an asynchronous environment. As an example, we show how to improve the message complexity of asynchronous randomized consensus.
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 2013-05-03
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 60
Issue Number 2
Page Count 42
Starting Page 1
Ending Page 42

Open content in new tab

   Open content in new tab
Source: ACM Digital Library