The Library
On parallel time in population protocols
Tools
Tools
Tools
Czumaj, Artur and Lingas, Andrzej (2023) On parallel time in population protocols. Information Processing Letters, 179 . 106314. doi:10.1016/j.ipl.2022.106314 ISSN 0020-0190.
|
PDF
WRAP-parallel-time-population-protocols-Czumaj-2023.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (256Kb) | Preview |
Official URL: https://doi.org/10.1016/j.ipl.2022.106314
Abstract
The parallel time of a population protocol is defined as the average number of required interactions in which an agent in the protocol participates, i.e., the quotient between the total number of interactions required by the protocol and the total number n of agents, or just roughly the number of required rounds, where a round stands for a sequence of n consecutive interactions. This naming triggers an intuition that at least the expected number of parallel steps sufficient to implement a round is O(1). In a single parallel step only mutually independent interactions can be involved. We show that when the transition function of a population protocol is treated as a black box then the expected maximum number of parallel steps necessary to implement a round is Ω ( logn log logn ). We also provide a combinatorial argument for a matching upper bound on the expected number of parallel steps under additional assumptions. Further, we extend these bounds by showing that the situation changes dramatically for sequences of m = Ω (n logn) interactions. Then, the expected number of parallel steps required to implement such sequences is Θ( m n ) under the aforementioned additional assumptions. Thus, it asymptotically coincides with the notion of parallel time, i.e., O( m n ), for sequences of interactions produced by protocols solving any non-trivial problems requiring Ω(n logn) interactions.
| Item Type: | Journal Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
| SWORD Depositor: | Library Publications Router | ||||||||||||
| Library of Congress Subject Headings (LCSH): | Electronic data processing -- Distributed processing, Parallel processing (Electronic computers), Computational complexity | ||||||||||||
| Journal or Publication Title: | Information Processing Letters | ||||||||||||
| Publisher: | Elsevier Science BV | ||||||||||||
| ISSN: | 0020-0190 | ||||||||||||
| Official Date: | January 2023 | ||||||||||||
| Dates: |
|
||||||||||||
| Volume: | 179 | ||||||||||||
| Article Number: | 106314 | ||||||||||||
| DOI: | 10.1016/j.ipl.2022.106314 | ||||||||||||
| Status: | Peer Reviewed | ||||||||||||
| Publication Status: | Published | ||||||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
| Date of first compliant deposit: | 15 November 2022 | ||||||||||||
| Date of first compliant Open Access: | 15 November 2022 | ||||||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
