Consensus based estimation of anonymous networks size using Bernoulli trials
Damiano Varagnolo, Gianluigi Pillonetto, Luca Schenato · 2012
To maintain and organize distributed systems it is necessary to have a certain degree of knowledge of their status like the number of cooperating agents. The estimation of this number, usually referred as the network size, can pose challenging questions when agents' identification information cannot be disclosed, since the exchanged information cannot be associated to who originated it. In this paper we propose a totally distributed network size estimation strategy based on statistical inference concepts that can be applied under anonymity constraints. The scheme is based on the following paradigm: agents locally generate some Bernoulli trials, then distributedly compute averages of these generated data, finally locally compute the Maximum Likelihood estimate of the network size exploiting its probabilistic dependencies with the previously computed averages. In this work we study the statistical properties of this estimation strategy, and show how the probability of returning a wrong evaluation decreases exponentially in the number of locally generated trials. Finally, we discuss how practical implementation issues may affect the estimator, and show that there exists a neat phase transition between insensitivity to numerical errors and uselessness of the results.