Can I read Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States on EtoBox?

Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States by Alistarh, Dan; Gelashvili, Rati is a scholarly article available to read on EtoBox.

What is Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States about?

Population protocols are networks of finite-state agents, interacting randomly, and updating their states using simple rules. Despite their extreme simplicity, these systems have been shown to cooperatively perform complex computational tasks, such as simulating register machines to compute standard arithmetic functions. The election of a unique leader agent is a key requirement in such computational constructions. Yet, the fastest currently known population protocol for electing a leader only has linear stabilization time, and, it has recently been shown that no population protocol using a constant number of states per node may overcome this linear bound. In this paper, we give the first population protocol for leader election with polylogarithmic stabilization time, using polylogarithmic memory states per node. The protocol structure is quite simple: each node has an associated value, and is either a leader (still in contention) or a minion (following some leader). A leader keeps incrementing its value and "defeats" other leaders in one-to-one interactions, and will drop from contention and become a minion if it meets a leader with higher value. Importantly, a leader also drops o

Author

Alistarh, Dan; Gelashvili, Rati

Published

2015

Language

EN