How to Optimally Configure Stopping Criteria for Distributed Consensus Algorithms to Estimate Network Size

Knowing at least an accurate estimate of the network size is necessary for many real-world applications (e.g., routing, synchronization, etc.). However, estimating the network size in a distributed way is not a trivial task since no centralization and global identifiers are exploited. This paper investigates how to optimally stop distributed consensus algorithms for network size estimation. More specifically, we examine three well-known algorithms from this category (namely, the Local Degree weights, the Best Constant Degree weights, and the Convex Optimized weights) in two scenarios and under several various conditions by applying two metrics. The goal of this paper is to identify which scenario ensures higher performance of distributed consensus algorithms for network size estimation. In other words, we investigate whether stopping the algorithms based on network size estimates or on arithmetic mean estimates can guarantee the lowest estimation error and the highest convergence rate.