Ghodsi, Ali and El-Ansary, Sameh and Krishnamurthy, Supriya and Haridi, Seif (2005) A Self-stabilizing Network Size Estimation Gossip Algorithm for Peer-to-Peer Systems. [SICS Report]
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.
|Item Type:||SICS Report|
|Uncontrolled Keywords:||Network Size Estimation, Gossip Algorithms, Peer-to-Peer, DHTs|
|Deposited By:||Vicki Carleson|
|Deposited On:||29 Oct 2007|
|Last Modified:||18 Nov 2009 16:07|
Repository Staff Only: item control page