Time-Optimal and Energy-Efficient Size Approximation of Radio Networks
Vlady Ravelomanana · 2016
Radio networks (RN) are distributed systems consisting in n active stations. Assuming the number n unknown, we consider the model of RN without collision detection and design distributed randomized protocol that allows to compute a stochastic estimate N of the number n of active stations. Our algorithms are shown to run in expected time O(log n) with no station being awake for more than O(log log n) time slots. Our protocols can be parametrized in such a way that they end with all participants being aware of the value of N whose expectation can be made arbitrarily close to n.