Options
Positive aging admits fast asynchronous plurality consensus
Publikationstyp
Conference Paper
Date Issued
2018
Sprache
English
Author(s)
Start Page
385
End Page
394
Citation
PODC ’20 : Proceedings of the 39th Symposium on Principles of Distributed Computing : August 3-7, 2020, Virtual Event, Online. - 385-394 (2018)
Contribution to Conference
Publisher DOI
Scopus ID
ArXiv ID
Publisher
Association for Computing Machinery
ISBN of container
978-1-4503-7582-5
We study distributed plurality consensus among n nodes, each of which initially holds one of k opinions. The goal is to eventually agree on the initially dominant opinion. We consider an asynchronous communication model in which each node is equipped with a random clock. Whenever the clock of a node ticks, it may open communication channels to a constant number of other nodes, chosen uniformly at random or from a list of constantly many addresses acquired in previous steps. The tick rates and the delays for establishing communication
channels (channel delays) follow some probability distribution. Once a channel is established, communication between nodes can be performed instantaneously.
channels (channel delays) follow some probability distribution. Once a channel is established, communication between nodes can be performed instantaneously.
Subjects
asynchronicity
plurality consensus
positive aging
pólya-eggenberger distributions
tail bounds
Computer Science - Distributed; Parallel; and Cluster Computing
Computer Science - Distributed; Parallel; and Cluster Computing
DDC Class
004: Informatik