New Clocks, Fast Line Formation and Self-Replication Population Protocols

Gasieniec, Leszek ORCID: 0000-0003-1809-9814, Spirakis, Paul and Stachowiak, Grzegorz
(2021) New Clocks, Fast Line Formation and Self-Replication Population Protocols. [Preprint]

[img] Text
2111.10822v1.pdf - OA Published Version

Download (1MB) | Preview


In this paper we consider a variant of population protocols in which agents are allowed to be connected by edges, known as the constructors model. During an interaction between two agents the relevant connecting edge can be formed, maintained or eliminated by the transition function. The contributions of this paper are manifold. -- We propose and analyse a novel type of phase clocks allowing to count parallel time $\Theta(n\log n)$ in the constructors model. This new type of clocks can be also implemented in the standard population protocol model assuming a unique leader is available. -- The new clock enables a nearly optimal $O(n\log n)$ parallel time spanning line construction which improves dramatically on the best previously known $O(n^2)$ parallel time solution. -- We define a probabilistic version of bubble-sort in which random comparisons are allowed only between adjacent numbers in the sequence being sorted. We show that rather surprisingly this probabilistic bubble-sort requires $O(n^2)$ comparisons in expectation, i.e., on the same level as its deterministic counterpart. -- We propose the first self-replication protocol allowing to reproduce a {\em strand} (line-segment carrying information) of length $k$ in parallel time $O(n(k+\log n)).$ This result is based on the probabilistic bubble-sort argument. This protocol permits also simultaneous replication where $l$ copies of the strand can be obtained in time $O(n(k+\log n)\log l).$ All protocols in this paper operate with high probability.

Item Type: Preprint
Uncontrolled Keywords: cs.DC, cs.DC, cs.DS
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 02 Dec 2021 11:47
Last Modified: 27 May 2022 02:11
Related URLs: