Search Results

Documents authored by Kowalski, Dariusz R.

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.80
Distributed Fast Crash-Tolerant Consensus with Nearly-Linear Quantum Communication

Authors: Mohammad T. HajiAghayi, Dariusz R. Kowalski, and Jan Olkowski

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Fault-tolerant Consensus is about reaching agreement on some of the input values in a limited time by non-faulty autonomous processes, despite of failures of processes or communication medium. This problem is particularly challenging and costly against an adaptive adversary with full information. Bar-Joseph and Ben-Or (PODC'98) were the first who proved an absolute lower bound Ω(√{n/log n}) on expected time complexity of Consensus in any classical (i.e., randomized or deterministic) message-passing network with n processes succeeding with probability 1 against such a strong adaptive adversary crashing processes. Seminal work of Ben-Or and Hassidim (STOC'05) broke the Ω(√{n/log n}) barrier for consensus in the classical (deterministic and randomized) networks by enhancing the model with quantum channels. In such networks, quantum communication between every pair of processes participating in the protocol is also allowed. They showed an (expected) constant-time quantum algorithm for a linear number of crashes t < n/3. In this paper, we improve upon that seminal work by reducing the number of quantum and communication bits to an arbitrarily small polynomial, and even more, to a polylogarithmic number - though, the latter in the cost of a slightly larger polylogarithmic time (still exponentially smaller than the time lower bound Ω(√{n/log n}) for the classical computation models).
Cite as

Mohammad T. HajiAghayi, Dariusz R. Kowalski, and Jan Olkowski. Distributed Fast Crash-Tolerant Consensus with Nearly-Linear Quantum Communication. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 80:1-80:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hajiaghayi_et_al:LIPIcs.ICALP.2024.80,
  author =	{HajiAghayi, Mohammad T. and Kowalski, Dariusz R. and Olkowski, Jan},
  title =	{{Distributed Fast Crash-Tolerant Consensus with Nearly-Linear Quantum Communication}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{80:1--80:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.80},
  URN =		{urn:nbn:de:0030-drops-202235},
  doi =		{10.4230/LIPIcs.ICALP.2024.80},
  annote =	{Keywords: distributed algorithms, quantum algorithms, adaptive adversary, crash failures, Consensus, quantum common coin, approximate counting}
}
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
DOI: 10.4230/LIPIcs.MFCS.2022.22
Tree Exploration in Dual-Memory Model

Authors: Dominik Bojko, Karol Gotfryd, Dariusz R. Kowalski, and Dominik Pająk

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
We study the problem of online tree exploration by a deterministic mobile agent. Our main objective is to establish what features of the model of the mobile agent and the environment allow linear exploration time. We study agents that, upon entering a node, do not receive as input the edge via which they entered. In such model, deterministic memoryless exploration is infeasible, hence the agent needs to be allowed to use some memory. The memory can be located at the agent or at each node. The existing lower bounds show that if the memory is either only at the agent or only at the nodes, then the exploration needs superlinear time. We show that tree exploration in dual-memory model, with constant memory at the agent and logarithmic in the degree at each node is possible in linear time when one of the two additional features is present: fixed initial state of the memory at each node (so called clean memory) or a single movable token. We present two algorithms working in linear time for arbitrary trees in these two models. On the other hand, in our lower bound we show that if the agent has a single bit of memory and one bit is present at each node, then the exploration may require quadratic time even on paths, if the initial memory at nodes could be set arbitrarily (so called dirty memory). This shows that having clean node memory or a token allows linear time exploration of trees in the dual-memory model, but having neither of those features may lead to quadratic exploration time even on a simple path.
Cite as

Dominik Bojko, Karol Gotfryd, Dariusz R. Kowalski, and Dominik Pająk. Tree Exploration in Dual-Memory Model. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bojko_et_al:LIPIcs.MFCS.2022.22,
  author =	{Bojko, Dominik and Gotfryd, Karol and Kowalski, Dariusz R. and Paj\k{a}k, Dominik},
  title =	{{Tree Exploration in Dual-Memory Model}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.22},
  URN =		{urn:nbn:de:0030-drops-168207},
  doi =		{10.4230/LIPIcs.MFCS.2022.22},
  annote =	{Keywords: Graph exploration, agent, memory, tree, deterministic algorithms, lower bound}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.30
Fast Agreement in Networks with Byzantine Nodes

Authors: Bogdan S. Chlebus, Dariusz R. Kowalski, and Jan Olkowski

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
We study Consensus in synchronous networks with arbitrary connected topologies. Nodes may be faulty, in the sense of either Byzantine or proneness to crashing. Let t denote a known upper bound on the number of faulty nodes, and D_s denote a maximum diameter of a network obtained by removing up to s nodes, assuming the network is (s+1)-connected. We give an algorithm for Consensus running in time t + D_{2t} with nodes subject to Byzantine faults. We show that, for any algorithm solving Consensus for Byzantine nodes, there is a network G and an execution of the algorithm on this network that takes Ω(t + D_{2t}) rounds. We give an algorithm solving Consensus in t + D_{t} communication rounds with Byzantine nodes using authenticated messages of polynomial size. We show that for any numbers t and d > 4, there exists a network G and an algorithm solving Consensus with Byzantine nodes using authenticated messages in fewer than t + 3 rounds on G, but all algorithms solving Consensus without message authentication require at least t + d rounds on G. This separates Consensus with Byzantine nodes from Consensus with Byzantine nodes using message authentication, with respect to asymptotic time performance in networks of arbitrary connected topologies, which is unlike complete networks. Let f denote the number of failures actually occurring in an execution and unknown to the nodes. We develop an algorithm solving Consensus against crash failures and running in time 𝒪(f + D_{f}), assuming only that nodes know their names and can differentiate among ports; this algorithm is also communication-efficient, by using messages of size 𝒪(mlog n), where n is the number of nodes and m is the number of edges. We give a lower bound t+D_t-2 on the running time of any deterministic solution to Consensus in (t+1)-connected networks, if t nodes may crash.
Cite as

Bogdan S. Chlebus, Dariusz R. Kowalski, and Jan Olkowski. Fast Agreement in Networks with Byzantine Nodes. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chlebus_et_al:LIPIcs.DISC.2020.30,
  author =	{Chlebus, Bogdan S. and Kowalski, Dariusz R. and Olkowski, Jan},
  title =	{{Fast Agreement in Networks with Byzantine Nodes}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{30:1--30:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.30},
  URN =		{urn:nbn:de:0030-drops-131088},
  doi =		{10.4230/LIPIcs.DISC.2020.30},
  annote =	{Keywords: distributed algorithm, network, Consensus, Byzantine fault, message authentication, node crash, lower bound}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.17
Stable Memoryless Queuing under Contention

Authors: Paweł Garncarek, Tomasz Jurdziński, and Dariusz R. Kowalski

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
In this work we study stability of local memoryless packet scheduling policies in a distributed system of n nodes/queues under contention. The local policies at nodes may only access their current local queues, and have no other feedback from the underlying distributed system. Moreover, their memory is limited to some basic parameters. The packets arrive at queues according to arrival patterns controlled by an adversary restricted only by injection rate rho and burstiness b, or driven by a stochastic process; the former model analyzes worst-case stability while the latter - average case. We assume that the underlying distributed system is a classic shared channel, in which no two packets could be successfully scheduled (and removed from queues) at the same time. We show that there is a local memoryless scheduling policy which is both adversarially and stochastically stable for injection rates Omega(1/log n). Another algorithm achieves even higher - constant - stable injection rate, but only for a bounded range of burstiness. The first algorithm is utilizing properties of interleaved ultra-selectors, for which we prove stronger properties than known so far, while the second one is based on entirely new concept of selector with thresholds, unlike previously considered binary selectors/codes in the literature. Note that popular Backoff algorithms, some of which achieve stability for constant (stochastic) injection rates [Johan Håstad et al., 1996], use memory to record current state (e.g., the number of unsuccessful transmissions or the result of random sampling in each window) as well as randomization and feedback from the channel; unlike solutions in this work, which are memoryless and do not rely on randomization or channel feedback (thus, could be used independently from the link layer protocols). {}
Cite as

Paweł Garncarek, Tomasz Jurdziński, and Dariusz R. Kowalski. Stable Memoryless Queuing under Contention. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{garncarek_et_al:LIPIcs.DISC.2019.17,
  author =	{Garncarek, Pawe{\l} and Jurdzi\'{n}ski, Tomasz and Kowalski, Dariusz R.},
  title =	{{Stable Memoryless Queuing under Contention}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.17},
  URN =		{urn:nbn:de:0030-drops-113244},
  doi =		{10.4230/LIPIcs.DISC.2019.17},
  annote =	{Keywords: packet scheduling, online algorithms, adversarial injections, stochastic injections, stability, memoryless algorithms}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.147
Polynomial Anonymous Dynamic Distributed Computing Without a Unique Leader

Authors: Dariusz R. Kowalski and Miguel A. Mosteiro

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Counting the number of nodes in {Anonymous Dynamic Networks} is enticing from an algorithmic perspective: an important computation in a restricted platform with promising applications. Starting with Michail, Chatzigiannakis, and Spirakis [Michail et al., 2013], a flurry of papers sped up the running time guarantees from doubly-exponential to polynomial [Dariusz R. Kowalski and Miguel A. Mosteiro, 2018]. There is a common theme across all those works: a distinguished node is assumed to be present, because Counting cannot be solved deterministically without at least one. In the present work we study challenging questions that naturally follow: how to efficiently count with more than one distinguished node, or how to count without any distinguished node. More importantly, what is the minimal information needed about these distinguished nodes and what is the best we can aim for (count precision, stochastic guarantees, etc.) without any. We present negative and positive results to answer these questions. To the best of our knowledge, this is the first work that addresses them.
Cite as

Dariusz R. Kowalski and Miguel A. Mosteiro. Polynomial Anonymous Dynamic Distributed Computing Without a Unique Leader. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 147:1-147:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kowalski_et_al:LIPIcs.ICALP.2019.147,
  author =	{Kowalski, Dariusz R. and Mosteiro, Miguel A.},
  title =	{{Polynomial Anonymous Dynamic Distributed Computing Without a Unique Leader}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{147:1--147:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.147},
  URN =		{urn:nbn:de:0030-drops-107239},
  doi =		{10.4230/LIPIcs.ICALP.2019.147},
  annote =	{Keywords: Anonymous Dynamic Networks, Counting, distributed algorithms}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.28
Local Queuing Under Contention

Authors: Pawel Garncarek, Tomasz Jurdzinski, and Dariusz R. Kowalski

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

Abstract
We study stability of local packet scheduling policies in a distributed system of n nodes. The local policies at nodes may only access their local queues, and have no other feedback from the underlying distributed system. The packets arrive at queues according to arrival patterns controlled by an adversary restricted only by injection rate rho and burstiness b. In this work, we assume that the underlying distributed system is a shared channel, in which in order to get rid of a packet from the queue, a node needs to schedule it for transmission on the channel and no other packet is scheduled for transmission at the same time. We show that there is a local adaptive scheduling policy with relatively small memory, which is universally stable on a shared channel, that is, it has bounded queues for any rho<1 and b >= 0. On the other hand, without memory the maximal stable injection rate is O(1/log n). We show a local memoryless (non-adaptive) scheduling policy based on novel idea of ultra strong selectors which is stable for slightly smaller injection c/log^2 n, for some constant c>0.
Cite as

Pawel Garncarek, Tomasz Jurdzinski, and Dariusz R. Kowalski. Local Queuing Under Contention. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{garncarek_et_al:LIPIcs.DISC.2018.28,
  author =	{Garncarek, Pawel and Jurdzinski, Tomasz and Kowalski, Dariusz R.},
  title =	{{Local Queuing Under Contention}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{28:1--28:18},
  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.28},
  URN =		{urn:nbn:de:0030-drops-98172},
  doi =		{10.4230/LIPIcs.DISC.2018.28},
  annote =	{Keywords: Distributed algorithms, local queuing, shared channel, multiple-access channel, adversarial packet arrivals, stability, deterministic algorithms}
}
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.ICALP.2018.156
Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations

Authors: Dariusz R. Kowalski and Miguel A. Mosteiro

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Starting with Michail, Chatzigiannakis, and Spirakis work [Michail et al., 2013], the problem of Counting the number of nodes in {Anonymous Dynamic Networks} has attracted a lot of attention. The problem is challenging because nodes are indistinguishable (they lack identifiers and execute the same program) and the topology may change arbitrarily from round to round of communication, as long as the network is connected in each round. The problem is central in distributed computing as the number of participants is frequently needed to make important decisions, such as termination, agreement, synchronization, and many others. A variety of algorithms built on top of mass-distribution techniques have been presented, analyzed, and also experimentally evaluated; some of them assumed additional knowledge of network characteristics, such as bounded degree or given upper bound on the network size. However, the question of whether Counting can be solved deterministically in sub-exponential time remained open. In this work, we answer this question positively by presenting Methodical Counting, which runs in polynomial time and requires no knowledge of network characteristics. Moreover, we also show how to extend Methodical Counting to compute the sum of input values and more complex functions without extra cost. Our analysis leverages previous work on random walks in evolving graphs, combined with carefully chosen alarms in the algorithm that control the process and its parameters. To the best of our knowledge, our Counting algorithm and its extensions to other algebraic and Boolean functions are the first that can be implemented in practice with worst-case guarantees.
Cite as

Dariusz R. Kowalski and Miguel A. Mosteiro. Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 156:1-156:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kowalski_et_al:LIPIcs.ICALP.2018.156,
  author =	{Kowalski, Dariusz R. and Mosteiro, Miguel A.},
  title =	{{Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{156:1--156:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.156},
  URN =		{urn:nbn:de:0030-drops-91602},
  doi =		{10.4230/LIPIcs.ICALP.2018.156},
  annote =	{Keywords: Anonymous Dynamic Networks, Counting, Boolean functions, distributed algorithms, deterministic algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2446
Dynamic Sharing of a Multiple Access Channel

Authors: Marcin Bienkowski, Marek Klonowski, Miroslaw Korzeniowski, and Dariusz R. Kowalski

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
In this paper we consider the mutual exclusion problem on a multiple access channel. Mutual exclusion is one of the fundamental problems in distributed computing. In the classic version of this problem, $n$ processes perform a concurrent program which occasionally triggers some of them to use shared resources, such as memory, communication channel, device, etc. The goal is to design a distributed algorithm to control entries and exits to/from the shared resource in such a way that in any time there is at most one process accessing it. We consider both the classic and a slightly weaker version of mutual exclusion, called $\ep$-mutual-exclusion, where for each period of a process staying in the critical section the probability that there is some other process in the critical section is at most $\ep$. We show that there are channel settings, where the classic mutual exclusion is not feasible even for randomized algorithms, while $\ep$-mutual-exclusion is. In more relaxed channel settings, we prove an exponential gap between the makespan complexity of the classic mutual exclusion problem and its weaker $\ep$-exclusion version. We also show how to guarantee fairness of mutual exclusion algorithms, i.e., that each process that wants to enter the critical section will eventually succeed.
Cite as

Marcin Bienkowski, Marek Klonowski, Miroslaw Korzeniowski, and Dariusz R. Kowalski. Dynamic Sharing of a Multiple Access Channel. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 83-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.STACS.2010.2446,
  author =	{Bienkowski, Marcin and Klonowski, Marek and Korzeniowski, Miroslaw and Kowalski, Dariusz R.},
  title =	{{Dynamic Sharing of a Multiple Access Channel}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{83--94},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2446},
  URN =		{urn:nbn:de:0030-drops-24467},
  doi =		{10.4230/LIPIcs.STACS.2010.2446},
  annote =	{Keywords: Distributed algorithms, multiple access channel, mutual exclusion}
}
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 Imprint Privacy Contact