Search Results

Documents authored by Jurdzinski, Tomasz

Found 3 Possible Name Variants:

Jurdzínski, Tomasz

Document
DOI: 10.4230/LIPIcs.DISC.2025.33
Approach of Agents with Restricted Fuel Tanks

Authors: Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Two mobile agents, modelled as points in the plane moving at speed 1, have to get at a distance at most 1 from each other. This task is known as approach or rendezvous in the plane. An adversary initially places both agents at distinct points, called their bases, at distance at most D, and wakes them up at possibly different times. Each of the agents has a fuel tank that allows them to traverse a trajectory of length D, and can be replenished at the base of the agent. The algorithm of each agent consists of a series of actions which are either moves at a chosen distance in a chosen direction or staying idle for a chosen period of time. For a given instance of the approach task, the execution time of an approach algorithm is the length of the period between the start of the later agent and the moment of approach. Our goal is to design approach algorithms with optimal time complexity. We consider two independent coherence assumptions. One of them is time coherence, i.e., agents start simultaneously, and the other is orientation coherence: agents have compatible compasses, showing the same North direction. Our main result is establishing optimal time complexity of the approach problem with restricted fuel tanks. It turns out that this optimal complexity heavily depends on the above coherence assumptions. If both of them are satisfied then approach can be performed in time O(D²) and we show that this complexity is optimal. If any of the two coherence assumptions is missing then approach can be performed in time O(D²√D) and we prove that this order of magnitude cannot be improved. Our main technical contribution are lower bounds showing that, for each of the considered scenarios, our fairly natural approach algorithms are, in fact, optimal.
Cite as

Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak. Approach of Agents with Restricted Fuel Tanks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 33:1-33:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2025.33,
  author =	{Ganczorz, Adam and Jurdzinski, Tomasz and Pelc, Andrzej and Stachowiak, Grzegorz},
  title =	{{Approach of Agents with Restricted Fuel Tanks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{33:1--33:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.33},
  URN =		{urn:nbn:de:0030-drops-248506},
  doi =		{10.4230/LIPIcs.DISC.2025.33},
  annote =	{Keywords: mobile agent, approach, rendezvous, plane, restricted energy}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.58
Brief Announcement: Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks

Authors: Adam Ganczorz, Tomasz Jurdzinski, and Andrzej Pelc

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We consider two fundamental communication tasks in arbitrary radio networks: broadcasting (information from one source has to reach all nodes) and gossiping (every node has a message and all messages have to reach all nodes). Nodes are assigned labels that are (not necessarily different) binary strings. Each node knows its own label and can use it as a parameter in the same deterministic algorithm. The length of a labeling scheme is the largest length of a label. The goal is to find labeling schemes of asymptotically optimal length for the above tasks, and to design fast deterministic distributed algorithms for each of them, using labels of optimal length. Our main result concerns broadcasting. We show the existence of a labeling scheme of constant length that supports broadcasting in time O(D+log² n), where D is the diameter of the network and n is the number of nodes. This broadcasting time is an improvement over the best currently known O(Dlog n + log² n) time of broadcasting with constant-length labels, due to Ellen and Gilbert (SPAA 2020). It also matches the optimal broadcasting time in radio networks of known topology. Hence, we show that appropriately chosen node labels of constant length permit to achieve, in a distributed way, the optimal centralized broadcasting time. This is, perhaps, the most surprising finding of this paper. We are able to obtain our result thanks to a novel methodological tool of propagating information in radio networks, that we call a 2-height respecting tree. Next, we apply our broadcasting algorithm to solve the gossiping problem. We get a gossiping algorithm working in time O(D + Δlog n + log² n), using a labeling scheme of optimal length O(log Δ), where Δ is the maximum degree. Our time is the same as the best known gossiping time in radio networks of known topology.
Cite as

Adam Ganczorz, Tomasz Jurdzinski, and Andrzej Pelc. Brief Announcement: Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 58:1-58:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2025.58,
  author =	{Ganczorz, Adam and Jurdzinski, Tomasz and Pelc, Andrzej},
  title =	{{Brief Announcement: Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{58:1--58:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.58},
  URN =		{urn:nbn:de:0030-drops-248744},
  doi =		{10.4230/LIPIcs.DISC.2025.58},
  annote =	{Keywords: radio network, distributed algorithms, algorithms with advice, labeling scheme, broadcasting, gossiping}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.22
Deterministic Size Discovery and Topology Recognition in Radio Networks with Short Labels

Authors: Adam Gańczorz, Tomasz Jurdziński, Mateusz Lewko, and Andrzej Pelc

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
We consider the fundamental problems of size discovery and topology recognition in radio networks modeled by simple undirected connected graphs. Size discovery calls for all nodes to output the number of nodes in the graph, called its size, and in the task of topology recognition each node has to learn the topology of the graph and its position in it. We do not assume collision detection: in case of a collision, node v does not hear anything (except the background noise that it also hears when no neighbor transmits). The time of a deterministic algorithm for each of the above problems is the worst-case number of rounds it takes to solve it. Nodes have labels which are (not necessarily different) binary strings. Each node knows its own label and can use it when executing the algorithm. The length of a labeling scheme is the largest length of a label. For size discovery, we construct a labeling scheme of length O(log logΔ) (which is known to be optimal, even if collision detection is available) and we design an algorithm for this problem using this scheme and working in time O(log² n), where n is the size of the graph. We also show that time complexity O(log² n) is optimal for the problem of size discovery, whenever the labeling scheme is of optimal length O(log logΔ). For topology recognition, we construct a labeling scheme of length O(logΔ), and we design an algorithm for this problem using this scheme and working in time O (DΔ+min(Δ²,n)), where D is the diameter of the graph. We also show that the length of our labeling scheme is asymptotically optimal.
Cite as

Adam Gańczorz, Tomasz Jurdziński, Mateusz Lewko, and Andrzej Pelc. Deterministic Size Discovery and Topology Recognition in Radio Networks with Short Labels. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2021.22,
  author =	{Ga\'{n}czorz, Adam and Jurdzi\'{n}ski, Tomasz and Lewko, Mateusz and Pelc, Andrzej},
  title =	{{Deterministic Size Discovery and Topology Recognition in Radio Networks with Short Labels}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.22},
  URN =		{urn:nbn:de:0030-drops-148242},
  doi =		{10.4230/LIPIcs.DISC.2021.22},
  annote =	{Keywords: size discovery, topology recognition, radio network, labeling scheme}
}
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
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.2017.54
Brief Announcement: On Connectivity in the Broadcast Congested Clique

Authors: Tomasz Jurdzínski and Krzysztof Nowicki

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
Recently, very fast deterministic and randomized algorithms have been obtained for connectivity and minimum spanning tree in the unicast congested clique. In contrast, no solution faster than a simple parallel implementation of the Boruvka's algorithm has been known for both problems in the broadcast congested clique. In this announcement, we present the first sub-logarithmic deterministic algorithm for connected components in the broadcast congested clique.
Cite as

Tomasz Jurdzínski and Krzysztof Nowicki. Brief Announcement: On Connectivity in the Broadcast Congested Clique. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 54:1-54:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jurdzinski_et_al:LIPIcs.DISC.2017.54,
  author =	{Jurdz{\'\i}nski, Tomasz and Nowicki, Krzysztof},
  title =	{{Brief Announcement: On Connectivity in the Broadcast Congested Clique}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{54:1--54:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.54},
  URN =		{urn:nbn:de:0030-drops-79903},
  doi =		{10.4230/LIPIcs.DISC.2017.54},
  annote =	{Keywords: congested clique, broadcast, connected components, bandwidth}
}

Jurdzinski, Tomasz

Document
DOI: 10.4230/LIPIcs.DISC.2025.33
Approach of Agents with Restricted Fuel Tanks

Authors: Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Two mobile agents, modelled as points in the plane moving at speed 1, have to get at a distance at most 1 from each other. This task is known as approach or rendezvous in the plane. An adversary initially places both agents at distinct points, called their bases, at distance at most D, and wakes them up at possibly different times. Each of the agents has a fuel tank that allows them to traverse a trajectory of length D, and can be replenished at the base of the agent. The algorithm of each agent consists of a series of actions which are either moves at a chosen distance in a chosen direction or staying idle for a chosen period of time. For a given instance of the approach task, the execution time of an approach algorithm is the length of the period between the start of the later agent and the moment of approach. Our goal is to design approach algorithms with optimal time complexity. We consider two independent coherence assumptions. One of them is time coherence, i.e., agents start simultaneously, and the other is orientation coherence: agents have compatible compasses, showing the same North direction. Our main result is establishing optimal time complexity of the approach problem with restricted fuel tanks. It turns out that this optimal complexity heavily depends on the above coherence assumptions. If both of them are satisfied then approach can be performed in time O(D²) and we show that this complexity is optimal. If any of the two coherence assumptions is missing then approach can be performed in time O(D²√D) and we prove that this order of magnitude cannot be improved. Our main technical contribution are lower bounds showing that, for each of the considered scenarios, our fairly natural approach algorithms are, in fact, optimal.
Cite as

Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak. Approach of Agents with Restricted Fuel Tanks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 33:1-33:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2025.33,
  author =	{Ganczorz, Adam and Jurdzinski, Tomasz and Pelc, Andrzej and Stachowiak, Grzegorz},
  title =	{{Approach of Agents with Restricted Fuel Tanks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{33:1--33:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.33},
  URN =		{urn:nbn:de:0030-drops-248506},
  doi =		{10.4230/LIPIcs.DISC.2025.33},
  annote =	{Keywords: mobile agent, approach, rendezvous, plane, restricted energy}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.58
Brief Announcement: Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks

Authors: Adam Ganczorz, Tomasz Jurdzinski, and Andrzej Pelc

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We consider two fundamental communication tasks in arbitrary radio networks: broadcasting (information from one source has to reach all nodes) and gossiping (every node has a message and all messages have to reach all nodes). Nodes are assigned labels that are (not necessarily different) binary strings. Each node knows its own label and can use it as a parameter in the same deterministic algorithm. The length of a labeling scheme is the largest length of a label. The goal is to find labeling schemes of asymptotically optimal length for the above tasks, and to design fast deterministic distributed algorithms for each of them, using labels of optimal length. Our main result concerns broadcasting. We show the existence of a labeling scheme of constant length that supports broadcasting in time O(D+log² n), where D is the diameter of the network and n is the number of nodes. This broadcasting time is an improvement over the best currently known O(Dlog n + log² n) time of broadcasting with constant-length labels, due to Ellen and Gilbert (SPAA 2020). It also matches the optimal broadcasting time in radio networks of known topology. Hence, we show that appropriately chosen node labels of constant length permit to achieve, in a distributed way, the optimal centralized broadcasting time. This is, perhaps, the most surprising finding of this paper. We are able to obtain our result thanks to a novel methodological tool of propagating information in radio networks, that we call a 2-height respecting tree. Next, we apply our broadcasting algorithm to solve the gossiping problem. We get a gossiping algorithm working in time O(D + Δlog n + log² n), using a labeling scheme of optimal length O(log Δ), where Δ is the maximum degree. Our time is the same as the best known gossiping time in radio networks of known topology.
Cite as

Adam Ganczorz, Tomasz Jurdzinski, and Andrzej Pelc. Brief Announcement: Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 58:1-58:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2025.58,
  author =	{Ganczorz, Adam and Jurdzinski, Tomasz and Pelc, Andrzej},
  title =	{{Brief Announcement: Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{58:1--58:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.58},
  URN =		{urn:nbn:de:0030-drops-248744},
  doi =		{10.4230/LIPIcs.DISC.2025.58},
  annote =	{Keywords: radio network, distributed algorithms, algorithms with advice, labeling scheme, broadcasting, gossiping}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.22
Deterministic Size Discovery and Topology Recognition in Radio Networks with Short Labels

Authors: Adam Gańczorz, Tomasz Jurdziński, Mateusz Lewko, and Andrzej Pelc

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
We consider the fundamental problems of size discovery and topology recognition in radio networks modeled by simple undirected connected graphs. Size discovery calls for all nodes to output the number of nodes in the graph, called its size, and in the task of topology recognition each node has to learn the topology of the graph and its position in it. We do not assume collision detection: in case of a collision, node v does not hear anything (except the background noise that it also hears when no neighbor transmits). The time of a deterministic algorithm for each of the above problems is the worst-case number of rounds it takes to solve it. Nodes have labels which are (not necessarily different) binary strings. Each node knows its own label and can use it when executing the algorithm. The length of a labeling scheme is the largest length of a label. For size discovery, we construct a labeling scheme of length O(log logΔ) (which is known to be optimal, even if collision detection is available) and we design an algorithm for this problem using this scheme and working in time O(log² n), where n is the size of the graph. We also show that time complexity O(log² n) is optimal for the problem of size discovery, whenever the labeling scheme is of optimal length O(log logΔ). For topology recognition, we construct a labeling scheme of length O(logΔ), and we design an algorithm for this problem using this scheme and working in time O (DΔ+min(Δ²,n)), where D is the diameter of the graph. We also show that the length of our labeling scheme is asymptotically optimal.
Cite as

Adam Gańczorz, Tomasz Jurdziński, Mateusz Lewko, and Andrzej Pelc. Deterministic Size Discovery and Topology Recognition in Radio Networks with Short Labels. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2021.22,
  author =	{Ga\'{n}czorz, Adam and Jurdzi\'{n}ski, Tomasz and Lewko, Mateusz and Pelc, Andrzej},
  title =	{{Deterministic Size Discovery and Topology Recognition in Radio Networks with Short Labels}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.22},
  URN =		{urn:nbn:de:0030-drops-148242},
  doi =		{10.4230/LIPIcs.DISC.2021.22},
  annote =	{Keywords: size discovery, topology recognition, radio network, labeling scheme}
}
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
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.2017.54
Brief Announcement: On Connectivity in the Broadcast Congested Clique

Authors: Tomasz Jurdzínski and Krzysztof Nowicki

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
Recently, very fast deterministic and randomized algorithms have been obtained for connectivity and minimum spanning tree in the unicast congested clique. In contrast, no solution faster than a simple parallel implementation of the Boruvka's algorithm has been known for both problems in the broadcast congested clique. In this announcement, we present the first sub-logarithmic deterministic algorithm for connected components in the broadcast congested clique.
Cite as

Tomasz Jurdzínski and Krzysztof Nowicki. Brief Announcement: On Connectivity in the Broadcast Congested Clique. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 54:1-54:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jurdzinski_et_al:LIPIcs.DISC.2017.54,
  author =	{Jurdz{\'\i}nski, Tomasz and Nowicki, Krzysztof},
  title =	{{Brief Announcement: On Connectivity in the Broadcast Congested Clique}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{54:1--54:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.54},
  URN =		{urn:nbn:de:0030-drops-79903},
  doi =		{10.4230/LIPIcs.DISC.2017.54},
  annote =	{Keywords: congested clique, broadcast, connected components, bandwidth}
}

Jurdziński, Tomasz

Document
DOI: 10.4230/LIPIcs.DISC.2025.33
Approach of Agents with Restricted Fuel Tanks

Authors: Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Two mobile agents, modelled as points in the plane moving at speed 1, have to get at a distance at most 1 from each other. This task is known as approach or rendezvous in the plane. An adversary initially places both agents at distinct points, called their bases, at distance at most D, and wakes them up at possibly different times. Each of the agents has a fuel tank that allows them to traverse a trajectory of length D, and can be replenished at the base of the agent. The algorithm of each agent consists of a series of actions which are either moves at a chosen distance in a chosen direction or staying idle for a chosen period of time. For a given instance of the approach task, the execution time of an approach algorithm is the length of the period between the start of the later agent and the moment of approach. Our goal is to design approach algorithms with optimal time complexity. We consider two independent coherence assumptions. One of them is time coherence, i.e., agents start simultaneously, and the other is orientation coherence: agents have compatible compasses, showing the same North direction. Our main result is establishing optimal time complexity of the approach problem with restricted fuel tanks. It turns out that this optimal complexity heavily depends on the above coherence assumptions. If both of them are satisfied then approach can be performed in time O(D²) and we show that this complexity is optimal. If any of the two coherence assumptions is missing then approach can be performed in time O(D²√D) and we prove that this order of magnitude cannot be improved. Our main technical contribution are lower bounds showing that, for each of the considered scenarios, our fairly natural approach algorithms are, in fact, optimal.
Cite as

Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak. Approach of Agents with Restricted Fuel Tanks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 33:1-33:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2025.33,
  author =	{Ganczorz, Adam and Jurdzinski, Tomasz and Pelc, Andrzej and Stachowiak, Grzegorz},
  title =	{{Approach of Agents with Restricted Fuel Tanks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{33:1--33:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.33},
  URN =		{urn:nbn:de:0030-drops-248506},
  doi =		{10.4230/LIPIcs.DISC.2025.33},
  annote =	{Keywords: mobile agent, approach, rendezvous, plane, restricted energy}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.58
Brief Announcement: Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks

Authors: Adam Ganczorz, Tomasz Jurdzinski, and Andrzej Pelc

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We consider two fundamental communication tasks in arbitrary radio networks: broadcasting (information from one source has to reach all nodes) and gossiping (every node has a message and all messages have to reach all nodes). Nodes are assigned labels that are (not necessarily different) binary strings. Each node knows its own label and can use it as a parameter in the same deterministic algorithm. The length of a labeling scheme is the largest length of a label. The goal is to find labeling schemes of asymptotically optimal length for the above tasks, and to design fast deterministic distributed algorithms for each of them, using labels of optimal length. Our main result concerns broadcasting. We show the existence of a labeling scheme of constant length that supports broadcasting in time O(D+log² n), where D is the diameter of the network and n is the number of nodes. This broadcasting time is an improvement over the best currently known O(Dlog n + log² n) time of broadcasting with constant-length labels, due to Ellen and Gilbert (SPAA 2020). It also matches the optimal broadcasting time in radio networks of known topology. Hence, we show that appropriately chosen node labels of constant length permit to achieve, in a distributed way, the optimal centralized broadcasting time. This is, perhaps, the most surprising finding of this paper. We are able to obtain our result thanks to a novel methodological tool of propagating information in radio networks, that we call a 2-height respecting tree. Next, we apply our broadcasting algorithm to solve the gossiping problem. We get a gossiping algorithm working in time O(D + Δlog n + log² n), using a labeling scheme of optimal length O(log Δ), where Δ is the maximum degree. Our time is the same as the best known gossiping time in radio networks of known topology.
Cite as

Adam Ganczorz, Tomasz Jurdzinski, and Andrzej Pelc. Brief Announcement: Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 58:1-58:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2025.58,
  author =	{Ganczorz, Adam and Jurdzinski, Tomasz and Pelc, Andrzej},
  title =	{{Brief Announcement: Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{58:1--58:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.58},
  URN =		{urn:nbn:de:0030-drops-248744},
  doi =		{10.4230/LIPIcs.DISC.2025.58},
  annote =	{Keywords: radio network, distributed algorithms, algorithms with advice, labeling scheme, broadcasting, gossiping}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.22
Deterministic Size Discovery and Topology Recognition in Radio Networks with Short Labels

Authors: Adam Gańczorz, Tomasz Jurdziński, Mateusz Lewko, and Andrzej Pelc

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
We consider the fundamental problems of size discovery and topology recognition in radio networks modeled by simple undirected connected graphs. Size discovery calls for all nodes to output the number of nodes in the graph, called its size, and in the task of topology recognition each node has to learn the topology of the graph and its position in it. We do not assume collision detection: in case of a collision, node v does not hear anything (except the background noise that it also hears when no neighbor transmits). The time of a deterministic algorithm for each of the above problems is the worst-case number of rounds it takes to solve it. Nodes have labels which are (not necessarily different) binary strings. Each node knows its own label and can use it when executing the algorithm. The length of a labeling scheme is the largest length of a label. For size discovery, we construct a labeling scheme of length O(log logΔ) (which is known to be optimal, even if collision detection is available) and we design an algorithm for this problem using this scheme and working in time O(log² n), where n is the size of the graph. We also show that time complexity O(log² n) is optimal for the problem of size discovery, whenever the labeling scheme is of optimal length O(log logΔ). For topology recognition, we construct a labeling scheme of length O(logΔ), and we design an algorithm for this problem using this scheme and working in time O (DΔ+min(Δ²,n)), where D is the diameter of the graph. We also show that the length of our labeling scheme is asymptotically optimal.
Cite as

Adam Gańczorz, Tomasz Jurdziński, Mateusz Lewko, and Andrzej Pelc. Deterministic Size Discovery and Topology Recognition in Radio Networks with Short Labels. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2021.22,
  author =	{Ga\'{n}czorz, Adam and Jurdzi\'{n}ski, Tomasz and Lewko, Mateusz and Pelc, Andrzej},
  title =	{{Deterministic Size Discovery and Topology Recognition in Radio Networks with Short Labels}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.22},
  URN =		{urn:nbn:de:0030-drops-148242},
  doi =		{10.4230/LIPIcs.DISC.2021.22},
  annote =	{Keywords: size discovery, topology recognition, radio network, labeling scheme}
}
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
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.2017.54
Brief Announcement: On Connectivity in the Broadcast Congested Clique

Authors: Tomasz Jurdzínski and Krzysztof Nowicki

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
Recently, very fast deterministic and randomized algorithms have been obtained for connectivity and minimum spanning tree in the unicast congested clique. In contrast, no solution faster than a simple parallel implementation of the Boruvka's algorithm has been known for both problems in the broadcast congested clique. In this announcement, we present the first sub-logarithmic deterministic algorithm for connected components in the broadcast congested clique.
Cite as

Tomasz Jurdzínski and Krzysztof Nowicki. Brief Announcement: On Connectivity in the Broadcast Congested Clique. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 54:1-54:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jurdzinski_et_al:LIPIcs.DISC.2017.54,
  author =	{Jurdz{\'\i}nski, Tomasz and Nowicki, Krzysztof},
  title =	{{Brief Announcement: On Connectivity in the Broadcast Congested Clique}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{54:1--54:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.54},
  URN =		{urn:nbn:de:0030-drops-79903},
  doi =		{10.4230/LIPIcs.DISC.2017.54},
  annote =	{Keywords: congested clique, broadcast, connected components, bandwidth}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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