# zbMATH — the first resource for mathematics

Fast size approximation of a radio network in beeping model. (English) Zbl 1437.68013
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 in a class of uniform algorithms.
##### MSC:
 68M10 Network design and communication in computer systems 68M12 Network protocols 68M14 Distributed systems 68W15 Distributed algorithms 68W25 Approximation algorithms
HyperLogLog
Full Text: