Search Results

Documents authored by Pająk, Dominik

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
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.148
Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol

Authors: Frederik Mallmann-Trenn, Yannic Maus, and Dominik Pajak

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

Abstract
We study a process of averaging in a distributed system with noisy communication. Each of the agents in the system starts with some value and the goal of each agent is to compute the average of all the initial values. In each round, one pair of agents is drawn uniformly at random from the whole population, communicates with each other and each of these two agents updates their local value based on their own value and the received message. The communication is noisy and whenever an agent sends any value v, the receiving agent receives v+N, where N is a zero-mean Gaussian random variable. The two quality measures of interest are (i) the total sum of squares TSS(t), which measures the sum of square distances from the average load to the initial average and (ii) bar{phi}(t), which measures the sum of square distances from the average load to the running average (average at time t). It is known that the simple averaging protocol - in which an agent sends its current value and sets its new value to the average of the received value and its current value - converges eventually to a state where bar{phi}(t) is small. It has been observed that TSS(t), due to the noise, eventually diverges and previous research - mostly in control theory - has focused on showing eventual convergence w.r.t. the running average. We obtain the first probabilistic bounds on the convergence time of bar{phi}(t) and precise bounds on the drift of TSS(t) that show that although TSS(t) eventually diverges, for a wide and interesting range of parameters, TSS(t) stays small for a number of rounds that is polynomial in the number of agents. Our results extend to the synchronous setting and settings where the agents are restricted to discrete values and perform rounding.
Cite as

Frederik Mallmann-Trenn, Yannic Maus, and Dominik Pajak. Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 148:1-148:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mallmanntrenn_et_al:LIPIcs.ICALP.2019.148,
  author =	{Mallmann-Trenn, Frederik and Maus, Yannic and Pajak, Dominik},
  title =	{{Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{148:1--148:16},
  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.148},
  URN =		{urn:nbn:de:0030-drops-107240},
  doi =		{10.4230/LIPIcs.ICALP.2019.148},
  annote =	{Keywords: population protocols, noisy communication, distributed averaging}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.27
On Simple Back-Off in Unreliable Radio Networks

Authors: Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
In this paper, we study local and global broadcast in the dual graph model, which describes communication in a radio network with both reliable and unreliable links. Existing work proved that efficient solutions to these problems are impossible in the dual graph model under standard assumptions. In real networks, however, simple back-off strategies tend to perform well for solving these basic communication tasks. We address this apparent paradox by introducing a new set of constraints to the dual graph model that better generalize the slow/fast fading behavior common in real networks. We prove that in the context of these new constraints, simple back-off strategies now provide efficient solutions to local and global broadcast in the dual graph model. We also precisely characterize how this efficiency degrades as the new constraints are reduced down to non-existent, and prove new lower bounds that establish this degradation as near optimal for a large class of natural algorithms. We conclude with an analysis of a more general model where we propose an enhanced back-off algorithm. These results provide theoretical foundations for the practical observation that simple back-off algorithms tend to work well even amid the complicated link dynamics of real radio networks.
Cite as

Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak. On Simple Back-Off in Unreliable Radio Networks. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gilbert_et_al:LIPIcs.OPODIS.2018.27,
  author =	{Gilbert, Seth and Lynch, Nancy and Newport, Calvin and Pajak, Dominik},
  title =	{{On Simple Back-Off in Unreliable Radio Networks}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.27},
  URN =		{urn:nbn:de:0030-drops-100877},
  doi =		{10.4230/LIPIcs.OPODIS.2018.27},
  annote =	{Keywords: radio networks, broadcast, unreliable links, distributed algorithm, robustness}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2018.48
Brief Announcement: On Simple Back-Off in Unreliable Radio Networks

Authors: Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak

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

Abstract
In this paper, we study local broadcast in the dual graph model, which describes communication in a radio network with both reliable and unreliable links. Existing work proved that efficient solutions to these problems are impossible in the dual graph model under standard assumptions. In real networks, however, simple back-off strategies tend to perform well for solving these basic communication tasks. We address this apparent paradox by introducing a new set of constraints to the dual graph model that better generalize the slow/fast fading behavior common in real networks. We prove that in the context of these new constraints, simple back-off strategies now provide efficient solutions to local broadcast in the dual graph model. These results provide theoretical foundations for the practical observation that simple back-off algorithms tend to work well even amid the complicated link dynamics of real radio networks.
Cite as

Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak. Brief Announcement: On Simple Back-Off in Unreliable Radio Networks. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 48:1-48:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gilbert_et_al:LIPIcs.DISC.2018.48,
  author =	{Gilbert, Seth and Lynch, Nancy and Newport, Calvin and Pajak, Dominik},
  title =	{{Brief Announcement: On Simple Back-Off in Unreliable Radio Networks}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{48:1--48: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.48},
  URN =		{urn:nbn:de:0030-drops-98373},
  doi =		{10.4230/LIPIcs.DISC.2018.48},
  annote =	{Keywords: radio networks, broadcast, unreliable links, distributed algorithm, robustness}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.44
Multiple Random Walks on Paths and Grids

Authors: Andrej Ivaskovic, Adrian Kosowski, Dominik Pajak, and Thomas Sauerwald

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We derive several new results on multiple random walks on "low dimensional" graphs. First, inspired by an example of a weighted random walk on a path of three vertices given by Efremenko and Reingold, we prove the following dichotomy: as the path length n tends to infinity, we have a super-linear speed-up w.r.t. the cover time if and only if the number of walks k is equal to 2. An important ingredient of our proofs is the use of a continuous-time analogue of multiple random walks, which might be of independent interest. Finally, we also present the first tight bounds on the speed-up of the cover time for any d-dimensional grid with d >= 2 being an arbitrary constant, and reveal a sharp transition between linear and logarithmic speed-up.
Cite as

Andrej Ivaskovic, Adrian Kosowski, Dominik Pajak, and Thomas Sauerwald. Multiple Random Walks on Paths and Grids. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ivaskovic_et_al:LIPIcs.STACS.2017.44,
  author =	{Ivaskovic, Andrej and Kosowski, Adrian and Pajak, Dominik and Sauerwald, Thomas},
  title =	{{Multiple Random Walks on Paths and Grids}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.44},
  URN =		{urn:nbn:de:0030-drops-69897},
  doi =		{10.4230/LIPIcs.STACS.2017.44},
  annote =	{Keywords: random walks, randomized algorithms, parallel computing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.263
Bounds on the Cover Time of Parallel Rotor Walks

Authors: Dariusz Dereniowski, Adrian Kosowski, Dominik Pajak, and Przemyslaw Uznanski

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node maintains a cyclic ordering of its outgoing arcs, and successively propagates walkers which visit it along its outgoing arcs in round-robin fashion, according to the fixed ordering. We consider the cover time of such a system, i.e., the number of steps after which each node has been visited by at least one walk, regardless of the starting locations of the walks. In the case of k=1, [Yanovski et al., 2003] and [Bampas et al., 2009] showed that a single walk achieves a cover time of exactly Theta(mD) for any n-node graph with m edges and diameter D, and that the walker eventually stabilizes to a traversal of an Eulerian circuit on the set of all directed edges of the graph. For k>1 parallel walks, no similar structural behaviour can be observed. In this work we provide tight bounds on the cover time of k parallel rotor walks in a graph. We show that this cover time is at most (mD/log(k)) and at least Theta(mD/k) for any graph, which corresponds to a speedup of between Theta(log(k)) and Theta(k) with respect to the cover time of a single walk. Both of these extremal values of speedup are achieved for some graph classes. Our results hold for up to a polynomially large number of walks, k=O(poly(n)).
Cite as

Dariusz Dereniowski, Adrian Kosowski, Dominik Pajak, and Przemyslaw Uznanski. Bounds on the Cover Time of Parallel Rotor Walks. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 263-275, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{dereniowski_et_al:LIPIcs.STACS.2014.263,
  author =	{Dereniowski, Dariusz and Kosowski, Adrian and Pajak, Dominik and Uznanski, Przemyslaw},
  title =	{{Bounds on the Cover Time of Parallel Rotor Walks}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{263--275},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.263},
  URN =		{urn:nbn:de:0030-drops-44637},
  doi =		{10.4230/LIPIcs.STACS.2014.263},
  annote =	{Keywords: Distributed graph exploration, Rotor-Router, Collaborative robots, Parallel random walks, Derandomization}
}
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