# zbMATH — the first resource for mathematics

Approximating the size of a radio network in beeping model. (English) Zbl 1437.68012
Suomela, Jukka (ed.), Structural information and communication complexity. 23rd international colloquium, SIROCCO 2016, Helsinki, Finland, July 19–21, 2016. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 9988, 358-373 (2016).
Summary: In a single-hop radio network, nodes can communicate with each other by broadcasting to a shared wireless channel. In each time slot, all nodes receive feedback from the channel depending on the number of transmitters. In the beeping model, each node learns whether zero or at least one node have transmitted. In such a model, a procedure estimating the size of the network can be used for efficiently solving the problems of leader election or conflict resolution. We introduce a time-efficient uniform algorithm for size estimation of single-hop networks. With probability at least $$1-1/f$$ our solution returns $$(1+\varepsilon)$$-approximation of the network size $$n$$ within $$\mathcal {O}(\log \log n+\log f/\varepsilon ^2)$$ time slots. We prove that the algorithm is asymptotically time-optimal for any constant $$\varepsilon >0$$.
For the entire collection see [Zbl 1350.68019].

##### MSC:
 68M10 Network design and communication in computer systems 68M12 Network protocols 68M14 Distributed systems 68W15 Distributed algorithms 68W25 Approximation algorithms
HyperLogLog
Full Text: