A Generic Scheme for Estimating the Size of a Group While Avoiding Feedback Implosion
The authors present a probabilistic polling scheme for estimating the size of a group of nodes affected by the same event. They analyze the bias of the proposed scheme and show how it can be completely eliminated. Their scheme differs from previous work in several important ways. First, it is generic in the sense that it is not dependent on the physical properties of the underlying network. Second, it uses a "One-shot" estimation technique that does not depend on the results of previous rounds. Finally, the estimating nodes control the number of feedback messages, thus allowing a good balance between the overhead imposed by the scheme and its precision.