Search Results

Documents authored by Stachowiak, Grzegorz

Document
DOI: 10.4230/LIPIcs.STACS.2023.33
New Clocks, Optimal Line Formation and Self-Replication Population Protocols

Authors: Leszek Gąsieniec, Paul G. Spirakis, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

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 Θ(n²) 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(polylog 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 Θ(nlog 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(polylog n). - We prove that any spanning line formation protocol requires Ω(nlog n) parallel time if high probability guaranty is imposed. We also show that the new clock enables an optimal O(nlog n) parallel time spanning line construction, which improves dramatically on the best currently known O(n²) parallel time protocol, solving the main open problem in the considered model [O. Michail and P. Spirakis, 2016]. - 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(n²) 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.
Cite as

Leszek Gąsieniec, Paul G. Spirakis, and Grzegorz Stachowiak. New Clocks, Optimal Line Formation and Self-Replication Population Protocols. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 33:1-33:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gasieniec_et_al:LIPIcs.STACS.2023.33,
  author =	{G\k{a}sieniec, Leszek and Spirakis, Paul G. and Stachowiak, Grzegorz},
  title =	{{New Clocks, Optimal Line Formation and Self-Replication Population Protocols}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{33:1--33:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.33},
  URN =		{urn:nbn:de:0030-drops-176857},
  doi =		{10.4230/LIPIcs.STACS.2023.33},
  annote =	{Keywords: Population protocols, constructors, probabilistic bubble-sort, self-replication}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.17
Contention Resolution Without Collision Detection: Constant Throughput And Logarithmic Energy

Authors: Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
A shared channel, also called a multiple access channel, is among the most popular and widely studied models of communication in distributed computing. An unknown number of stations (potentially unbounded) is connected to the channel and can communicate by transmitting and listening. A message is successfully transmitted on the channel if and only if there is a unique transmitter at that time; otherwise the message collides with some other transmission and nothing is sensed by the participating stations. We consider the general framework without collision detection and in which any participating station can join the channel at any moment. The contention resolution task is to let each of the contending stations to broadcast successfully its message on the channel. In this setting we present the first algorithm which exhibits asymptotically optimal Θ(1) throughput and only an O(log k) energy cost, understood as the maximum number of transmissions performed by a single station (where k is the number of participating stations, initially unknown). We also show that such efficiency cannot be reproduced by non-adaptive algorithms, i.e., whose behavior does not depend on the channel history (for example, classic backoff protocols). Namely, we show that non-adaptive algorithms cannot simultaneously achieve throughput Ω(1/polylog(k)) and energy O((log² k)/(log log k)²).
Cite as

Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak. Contention Resolution Without Collision Detection: Constant Throughput And Logarithmic Energy. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{demarco_et_al:LIPIcs.DISC.2022.17,
  author =	{De Marco, Gianluca and Kowalski, Dariusz R. and Stachowiak, Grzegorz},
  title =	{{Contention Resolution Without Collision Detection: Constant Throughput And Logarithmic Energy}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{17:1--17:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.17},
  URN =		{urn:nbn:de:0030-drops-172081},
  doi =		{10.4230/LIPIcs.DISC.2022.17},
  annote =	{Keywords: Shared channel, Contention resolution, Throughput, Energy consumption, Randomized algorithms, Lower bound}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.44
Brief Announcement: New Clocks, Fast Line Formation and Self-Replication Population Protocols

Authors: Leszek Gąsieniec, Paul Spirakis, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
In this paper we consider a known variant of the standard population protocol model in which agents can 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. The state space of agents is fixed (constant size) and the size n of the population is not known, i.e., not hard-coded in the transition function. Since pairs of agents are chosen uniformly at random the status of each edge is updated every Θ(n²) 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(polylog n) parallel time. The main focus in 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 analyse a novel edge based phase clock counting parallel time Θ(nlog n) in the network constructor model, showing also that its leader based counterpart provides the same time guaranties in the standard population protocol model. Note that all currently known phase clocks can count parallel time not exceeding O(polylog n). - The new clock enables a nearly optimal O(nlog n) parallel time spanning line construction (a key component of universal network construction), which improves dramatically on the best currently known O(n²) parallel time protocol, solving the main open problem in the considered model [O. Michail and P. Spirakis, 2016]. - We propose a new probabilistic bubble-sort algorithm in which random comparisons and transfers are allowed only between the adjacent positions in the sequence. Utilising a novel potential function reasoning we show that rather surprisingly this probabilistic sorting (via conditional pipelining) procedure requires O(n²) 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 a k-bit message of size independent of the state space) in parallel time O(n(k+log n)). The pipelining mechanism and the time complexity analysis of the strand self-replication protocol mimic those used in the probabilistic bubble-sort. The new protocol permits also simultaneous self-replication, where l copies of the strand can be created in time O(n(k+log n)log l). Finally, we discuss application of the strand self-replication protocol to pattern matching. Our protocols are always correct and provide time guaranties with high probability defined as 1-n^{-η}, for a constant η > 0.
Cite as

Leszek Gąsieniec, Paul Spirakis, and Grzegorz Stachowiak. Brief Announcement: New Clocks, Fast Line Formation and Self-Replication Population Protocols. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 44:1-44:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gasieniec_et_al:LIPIcs.DISC.2022.44,
  author =	{G\k{a}sieniec, Leszek and Spirakis, Paul and Stachowiak, Grzegorz},
  title =	{{Brief Announcement: New Clocks, Fast Line Formation and Self-Replication Population Protocols}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{44:1--44:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.44},
  URN =		{urn:nbn:de:0030-drops-172351},
  doi =		{10.4230/LIPIcs.DISC.2022.44},
  annote =	{Keywords: Population protocols, network constructors, probabilistic bubble-sort, self-replication}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.SWAT.2022.2
Time, Clocks and Efficiency of Population Protocols (Invited Paper)

Authors: Leszek Gąsieniec and Grzegorz Stachowiak

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
The model of population protocols is used to study distributed processes based on pairwise interactions between simple anonymous agents drawn from a large population of size n. The order in which agents meet in pairs is determined by the random scheduler, s.t., each consecutive pair is chosen uniformly at random. After each interaction the state of the relevant agents are amended according to the predefined transition function (the actual code of the algorithm) which governs the considered process. The state space of agents is often fixed and the size n is not known in advance, i.e., not hard-coded in the transition function. We assume that a population protocol starts in the predefined initial configuration of agents' states representing the input. And if successful, the protocol stabilises in a final configuration of states forming the output representing the solution to the considered problem. The time complexity of a population protocol refers to the number of interactions required to stabilise this protocol in a final configuration. We also define parallel time as the time complexity divided by n. Note that the parallel time of the system and the expected local time of each agent, i.e., the number of interactions observed by each agent, are correlated. Several mechanisms, known as phase clocks, have been developed to measure parallel time more accurately than counting local interactions. Most of the clocks target counting Θ(log n) parallel time required to fully synchronise all agents in the population. There are leader (and junta) based phase clocks which utilise a fixed number of states [D. Angluin et al., 2008; L. Gąsieniec and G. Stachowiak, 2021]. This type of clocks allows also counting any poly-logarithmic time while preserving fix state utilisation. The other type refers to leaderless clocks utilising Θ(log n) states [D. Alistarh et al., 2018; D. Doty et al., 2021]. This type allows approximate counting of parallel time as fixed resolution clocks [D. Doty et al., 2021] or oscillators [D. Alistarh et al., 2018]. Another clock type introduced recently in [L. Gąsieniec et al., 2021] enables counting Θ(nlog n) parallel time utilising a fixed number of states and either leaders or connections in the network constructor model. We also discuss parallel efficiency of population protocols referring to protocols operating in Θ(polylog n) parallel time, we propose extensions of the population protocol model leading to further improvement in state and time utilisation, and we state some open problems.
Cite as

Leszek Gąsieniec and Grzegorz Stachowiak. Time, Clocks and Efficiency of Population Protocols (Invited Paper). In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gasieniec_et_al:LIPIcs.SWAT.2022.2,
  author =	{G\k{a}sieniec, Leszek and Stachowiak, Grzegorz},
  title =	{{Time, Clocks and Efficiency of Population Protocols}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{2:1--2:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.2},
  URN =		{urn:nbn:de:0030-drops-161624},
  doi =		{10.4230/LIPIcs.SWAT.2022.2},
  annote =	{Keywords: Population protocols, phase clocks, oscillators, parallel time and efficiency}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2018.44
Brief Announcement: Deterministic Contention Resolution on a Shared Channel

Authors: Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
A shared channel, also called multiple-access channel, is one of the fundamental communication models. Autonomous entities communicate over a shared medium, and one of the main challenges is how to efficiently resolve collisions occurring when more than one entity attempts to access the channel at the same time. In this work we explore the impact of asynchrony, knowledge (or linear estimate) of the number of contenders, and acknowledgments, on both latency and channel utilization for the Contention resolution problem with non-adaptive deterministic algorithms.
Cite as

Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak. Brief Announcement: Deterministic Contention Resolution on a Shared Channel. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 44:1-44:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{demarco_et_al:LIPIcs.DISC.2018.44,
  author =	{De Marco, Gianluca and Kowalski, Dariusz R. and Stachowiak, Grzegorz},
  title =	{{Brief Announcement: Deterministic Contention Resolution on a Shared Channel}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{44:1--44:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.44},
  URN =		{urn:nbn:de:0030-drops-98331},
  doi =		{10.4230/LIPIcs.DISC.2018.44},
  annote =	{Keywords: Shared channel, multiple-access channel, distributed algorithm}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.14
Deterministic Population Protocols for Exact Majority and Plurality

Authors: Leszek Gasieniec, David Hamilton, Russell Martin, Paul G. Spirakis, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
In this paper we study space-efficient deterministic population protocols for several variants of the majority problem including plurality consensus. We focus on space efficient majority protocols in populations with an arbitrary number of colours C represented by k-bit labels, where k = ceiling (log C). In particular, we present asymptotically space-optimal (with respect to the adopted k-bit representation of colours) protocols for (1) the absolute majority problem, i.e., a protocol which decides whether a single colour dominates all other colours considered together, and (2) the relative majority problem, also known in the literature as plurality consensus, in which colours declare their volume superiority versus other individual colours. The new population protocols proposed in this paper rely on a dynamic formulation of the majority problem in which the colours originally present in the population can be changed by an external force during the communication process. The considered dynamic formulation is based on the concepts studied by D. Angluin et al. and O. Michail et al. about stabilizing inputs and composition of population protocols. Also, the protocols presented in this paper use a composition of some known protocols for static and dynamic majority.
Cite as

Leszek Gasieniec, David Hamilton, Russell Martin, Paul G. Spirakis, and Grzegorz Stachowiak. Deterministic Population Protocols for Exact Majority and Plurality. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gasieniec_et_al:LIPIcs.OPODIS.2016.14,
  author =	{Gasieniec, Leszek and Hamilton, David and Martin, Russell and Spirakis, Paul G. and Stachowiak, Grzegorz},
  title =	{{Deterministic Population Protocols for Exact Majority and Plurality}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.14},
  URN =		{urn:nbn:de:0030-drops-70837},
  doi =		{10.4230/LIPIcs.OPODIS.2016.14},
  annote =	{Keywords: Deterministic population protocols, majority, plurality consenus}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact