Gasieniec, Leszek 
ORCID: 0000-0003-1809-9814, Spirakis, Paul and Stachowiak, Grzegorz
(2021)
New Clocks, Optimal Line Formation and Self-Replication Population
Protocols.
[Preprint]
|
Text
2111.10822v1.pdf - Published version Download (1MB) | Preview |
Abstract
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 an 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 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: | 15 Mar 2024 04:43 |
| DOI: | 10.48550/arxiv.2111.10822 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3144421 |
Dimensions
Dimensions
