2026-07-24T21:35:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10086 2024-03-06T10:45:35Z ddc:004 open_access

Approximate Neighbor Counting in Radio Networks Newport, Calvin Zheng, Chaodong Radio networks neighborhood size estimation approximate counting For many distributed algorithms, neighborhood size is an important parameter. In radio networks, however, obtaining this information can be difficult due to ad hoc deployments and communication that occurs on a collision-prone shared channel. This paper conducts a comprehensive survey of the approximate neighbor counting problem, which requires nodes to obtain a constant factor approximation of the size of their network neighborhood. We produce new lower and upper bounds for three main variations of this problem in the radio network model: (a) the network is single-hop and every node must obtain an estimate of its neighborhood size; (b) the network is multi-hop and only a designated node must obtain an estimate of its neighborhood size; and (c) the network is multi-hop and every node must obtain an estimate of its neighborhood size. In studying these problem variations, we consider solutions with and without collision detection, and with both constant and high success probability. Some of our results are extensions of existing strategies, while others require technical innovations. We argue this collection of results provides insight into the nature of this well-motivated problem (including how it differs from related symmetry breaking tasks in radio networks), and provides a useful toolbox for algorithm designers tackling higher level problems that might benefit from neighborhood size estimates. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Calvin Newport and Chaodong Zheng 2019 Is Part Of LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2018.26 urn:nbn:de:0030-drops-100860 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.26 eng https://creativecommons.org/licenses/by/3.0/legalcode