Active and passive techniques for group size estimation in large-scale and dynamic distributed systems

This paper presents two solutions to a distributed statistic collection problem, called Group Size Estimation. These algorithms are intended for large-scale and dynamic distributed systems such as Grids, peer-to-peer overlays, etc. Each algorithm estimates (both in a one-shot and continuous manner) the number of non-faulty processes present in the global group. The first active scheme samples receipt times of gossip messages, while the second passive scheme calculates the density of process identifiers when hashed to a real interval. Our analysis, trace-driven simulation and deployment on a 33-node Linux cluster study and compare the latencies, scalability, and accuracy of these schemes.