A Self-stabilizing Network Size Estimation Gossip Algorithm for Peer-to-Peer Systems

We present a self-stabilizing network size estimation gossip algorithm which determines the number of nodes in a structured peer-to-peer system. The algorithm can handle joins, leaves, and failures and is applicable to most structured peer-to-peer systems providing a distributed hash table abstraction. Furthermore, the algorithm is self-stabilizing with respect to the local estimates of any node, which might be arbitrary at any given time. Once state corruption ceases, the algorithm eventually adjusts all estimates to the correct value even in presence of joins and leaves. The algorithm only assumes that the system is weakly fair, and does hence not require the nodes to make the same number of exchanges, to be correct