Networks cardinality estimation using order statistics

We consider a network of collaborative peers that aim at distributedly estimating the network cardinality. We assume nodes to be endowed with unique identification numbers (IDs), and we study the performance of size estimators that are based on exchanging these IDs. Motivated by practical scenarios where the time-to-estimate is critical, we specifically address the case where the convergence time of the algorithm, i.e., the number of communications required to achieve the final estimate, is minimal. We thus construct estimators of the network size by exploiting statistical inference concepts on top of the distributed computation of order statistics of the IDs, i.e., of the M biggest IDs available in the network. We then characterize the statistical performance of these estimators from theoretical perspectives and show their effectiveness in practical estimation situations by means of numerical examples.