Search Results

Documents authored by Lewko, Mateusz


Document
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-dev.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}
}
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