Deterministic size discovery and topology recognition in radio networks with short labels

DOI10.1016/J.IC.2023.105010arXiv2105.10595OpenAlexW3164441574WikidataQ120992389 ScholiaQ120992389MaRDI QIDQ6040656FDOQ6040656

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

Publication date: 19 May 2023

Published in: Information and Computation (Search for Journal in Brave)

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. In radio networks, nodes communicate in synchronous rounds and start in the same round. In each round a node can either transmit the same message to all its neighbors, or stay silent and listen. At the receiving end, a node $v$ hears a message from a neighbor $w$ in a given round, if $v$ listens in this round, and if $w$ is its only neighbor that transmits in this round. If more than one neighbor of a node $v$ transmits in a given round, there is a collision at $v$. We do not assume collision detection: in case of a collision, node $v$ does not hear anything. The time of a deterministic algorithm for each of the above problems is the worst-case number of rounds it takes to solve it. Our goal is to construct short labeling schemes for size discovery and topology recognition in arbitrary radio networks, and to design efficient deterministic algorithms using these schemes. For size discovery, we construct a labeling scheme of length $O(loglogDelta)$ and we design an algorithm for this problem using this scheme and working in time $O(lo{g}^{2}n)$, where $n$ is the size of the graph. We also show that time complexity $O(lo{g}^{2}n)$ is optimal for the problem of size discovery, whenever the labeling scheme is of optimal length. For topology recognition, we construct a labeling scheme of length $O(logDelta)$, and we design an algorithm for this problem using this scheme working in time $Oleft(DDelta+min(Delt{a}^2,n)ight)$. We also show that the length of our labeling scheme is asymptotically optimal.

Full work available at URL: https://arxiv.org/abs/2105.10595

zbMATH Keywords

topology recognitionlabeling schemeradio networksize discovery

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Optimal deterministic broadcasting in known topology radio networks
• Topology recognition with advice
• Online computation with advice
• Local MST computation with short advice
• Fast radio broadcasting with advice
• Communication algorithms with advice
• A lower bound for radio broadcast
• Faster communication in known topology radio networks
• Fast broadcasting and gossiping in radio networks
• Leader election in ad hoc radio networks: a keen ear helps
• Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks
• Deterministic communication in radio networks with large labels
• Deterministic communication in radio networks
• Randomized broadcast in radio networks with collision detection
• Time vs. information tradeoffs for leader election in anonymous trees
• Deterministic Graph Exploration with Advice
• Graph reconstruction in the congested clique
• Labeling schemes for deterministic radio multi-broadcast
• Lower and upper bounds for deterministic convergecast with labeling schemes
• Adjacency labeling schemes and induced-universal graphs

This page was built for publication: Deterministic size discovery and topology recognition in radio networks with short labels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6040656)