A Self-stabilizing Network Size Estimation Gossip Algorithm for Peer-to-Peer Systems
Number of Authors: 4
2005 (English)Report (Refereed)
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.
Place, publisher, year, edition, pages
Swedish Institute of Computer Science , 2005, 1. , 12 p.
SICS Technical Report, ISSN 1100-3154 ; 2005:16
Network Size Estimation, Gossip Algorithms, Peer-to-Peer, DHTs
Computer and Information Science
IdentifiersURN: urn:nbn:se:ri:diva-22096OAI: oai:DiVA.org:ri-22096DiVA: diva2:1041638