Options
Positive aging admits fast asynchronous plurality consensus
Publikationstyp
Conference Paper
Date Issued
2018-08
Sprache
English
Start Page
385
End Page
394
Citation
39th Symposium on Principles of Distributed Computing, PODC 2020
Contribution to Conference
Publisher DOI
Scopus ID
ArXiv ID
Publisher
Association for Computing Machinery (ACM)
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
DDC Class
004: Informatik