Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

On parallel time in population protocols

Czumaj, Artur and Lingas, Andrzej LU (2023) In Information Processing Letters 179.
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... (More)

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 [Formula presented]. 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=Ω(nlog⁡n) interactions. Then, the expected number of parallel steps required to implement such sequences is [Formula presented] under the aforementioned additional assumptions. Thus, it asymptotically coincides with the notion of parallel time, i.e., [Formula presented], for sequences of interactions produced by protocols solving any non-trivial problems requiring Ω(nlog⁡n) interactions.

(Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Directed acyclic graph, Distributed computing, Parallel time complexity, Population protocols, Randomized algorithms
in
Information Processing Letters
volume
179
article number
106314
publisher
Elsevier
external identifiers
  • scopus:85137172550
ISSN
0020-0190
DOI
10.1016/j.ipl.2022.106314
language
English
LU publication?
yes
id
ed795015-53a7-4199-abfe-66ffbc1727e6
date added to LUP
2022-10-14 08:00:29
date last changed
2022-10-14 08:03:59
@article{ed795015-53a7-4199-abfe-66ffbc1727e6,
  abstract     = {{<p>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 [Formula presented]. 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=Ω(nlog⁡n) interactions. Then, the expected number of parallel steps required to implement such sequences is [Formula presented] under the aforementioned additional assumptions. Thus, it asymptotically coincides with the notion of parallel time, i.e., [Formula presented], for sequences of interactions produced by protocols solving any non-trivial problems requiring Ω(nlog⁡n) interactions.</p>}},
  author       = {{Czumaj, Artur and Lingas, Andrzej}},
  issn         = {{0020-0190}},
  keywords     = {{Directed acyclic graph; Distributed computing; Parallel time complexity; Population protocols; Randomized algorithms}},
  language     = {{eng}},
  month        = {{01}},
  publisher    = {{Elsevier}},
  series       = {{Information Processing Letters}},
  title        = {{On parallel time in population protocols}},
  url          = {{http://dx.doi.org/10.1016/j.ipl.2022.106314}},
  doi          = {{10.1016/j.ipl.2022.106314}},
  volume       = {{179}},
  year         = {{2023}},
}