English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Population protocols are networks of finite-state agents, interactingrandomly, and updating their states using simple rules. Despite their extremesimplicity, these systems have been shown to cooperatively perform complexcomputational tasks, such as simulating register machines to compute standardarithmetic functions. The election of a unique leader agent is a keyrequirement in such computational constructions. Yet, the fastest currentlyknown population protocol for electing a leader only has linear stabilizationtime, and, it has recently been shown that no population protocol using aconstant number of states per node may overcome this linear bound.  In this paper, we give the first population protocol for leader election withpolylogarithmic stabilization time, using polylogarithmic memory states pernode. The protocol structure is quite simple: each node has an associatedvalue, and is either a leader (still in contention) or a minion (following someleader). A leader keeps incrementing its value and "defeats" other leaders inone-to-one interactions, and will drop from contention and become a minion ifit meets a leader with higher value. Importantly, a leader also drops out if itmeets a minion with higher absolute value. While these rules are quite simple,the proof that this algorithm achieves polylogarithmic stabilization time isnon-trivial. In particular, the argument combines careful use of concentrationinequalities with anti-concentration bounds, showing that the leaders' valuesbecome spread apart as the execution progresses, which in turn implies thatstraggling leaders get quickly eliminated. We complement our analysis withempirical results, showing that our protocol stabilizes extremely fast, evenfor large network sizes.

Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States