Buch ; Online: Leaderless Population Protocols Decide Double-exponential Thresholds
2022
Abstract: Population protocols are a model of distributed computation in which finite-state agents interact randomly in pairs. A protocol decides for any initial configuration whether it satisfies a fixed property, specified as a predicate on the set of ... ...
Abstract | Population protocols are a model of distributed computation in which finite-state agents interact randomly in pairs. A protocol decides for any initial configuration whether it satisfies a fixed property, specified as a predicate on the set of configurations. The state complexity of a predicate is smallest number of states of any protocol deciding that predicate. For threshold predicates of the form $x\ge k$, with $k$ constant, prior work has shown that they have state complexity $\Theta(\log\log k)$ if the protocol is extended with leaders. For ordinary protocols it is only known to be in $\Omega(\log\log k)\cap \mathcal{O}(\log k)$. We close this remaining gap by showing that it is $\Theta(\log\log k)$ as well, i.e. we construct protocols with $\mathcal{O}(n)$ states deciding $x\ge k$ with $k\ge2^{2^n}$. |
---|---|
Schlagwörter | Computer Science - Distributed ; Parallel ; and Cluster Computing |
Erscheinungsdatum | 2022-04-05 |
Erscheinungsland | us |
Dokumenttyp | Buch ; Online |
Datenquelle | BASE - Bielefeld Academic Search Engine (Lebenswissenschaftliche Auswahl) |
Volltext online
Zusatzmaterialien
Kategorien
Fernleihe an ZB MED
Sie können sich den gewünschten Titel als lokale Nutzerin oder lokaler Nutzer von ZB MED direkt an den Standort Köln schicken lassen.