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

Gąsieniec, L ORCID: 0000-0003-1809-9814, Spirakis, PG ORCID: 0000-0001-5396-3749 and Stachowiak, G (2023) New Clocks, Optimal Line Formation and Self-Replication Population Protocols. In: 40th International Symposium on Theoretical Aspects of Computer Science, 2023-3-7 - 2023-3-10, Hamburg, Germany.

Text PPline-Elements.pdf - Author Accepted Manuscript Download (1MB) | Preview

Abstract

In this paper we consider a known variant of the standard population protocol model in which agents are allowed to be connected by edges, referred to as the network constructor model. During an interaction between two agents the relevant connecting edge can be formed, maintained or eliminated by the transition function. Since pairs of agents are chosen uniformly at random the status of each edge is updated every Θ(n2) interactions in expectation which coincides with Θ(n) parallel time. This phenomenon provides a natural lower bound on the time complexity for any non-trivial network construction designed for this variant. This is in contrast with the standard population protocol model in which efficient protocols operate in O(poly log n) parallel time. The main focus of this paper is on efficient manipulation of linear structures including formation, self-replication and distribution (including pipelining) of complex information in the adopted model. We propose and analyze a novel edge based phase clock counting parallel time Θ(n log n) in the network constructor model, showing also that its leader based counterpart provides the same time guarantees in the standard population protocol model. Note that all currently known phase clocks can count parallel time not exceeding O(poly log n). We prove that any spanning line formation protocol requires Ω(n log n) parallel time if high probability guaranty is imposed. We also show that the new clock enables an optimal O(n log n) parallel time spanning line construction, which improves dramatically on the best currently known O(n2) parallel time protocol, solving the main open problem in the considered model [24]. We propose a new probabilistic bubble-sort algorithm in which random comparisons and transfers are limited to the adjacent positions in the sequence. Utilising a novel potential function reasoning we show that rather surprisingly this probabilistic sorting procedure requires O(n2) comparisons in expectation and whp, and is on par with its deterministic counterpart. We propose the first population protocol allowing self-replication of a strand of an arbitrary length k (carrying k-bit message of size independent of the state space) in parallel time O(n(k + log n)). The bit pipelining mechanism and the time complexity analysis of self-replication process mimic those used in the probabilistic bubble-sort argument. The new protocol permits also simultaneous self-replication, where l copies of the strand can be created in parallel in time O(n(k+log n) log l). We also discuss application of the strand self-replication protocol to pattern matching. All protocols are always correct and provide time guarantees with high probability defined as 1−n−η, for a constant η > 0.

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	14 Dec 2022 14:52
Last Modified:	29 Mar 2023 15:51
DOI:	10.4230/LIPIcs.STACS.2023.33
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3166661