SODA

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

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]

[img]
Preview
PDF
113Kb
[img]Postscript
150Kb

Abstract

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
ID Code:2374
Deposited By:Vicki Carleson
Deposited On:29 Oct 2007
Last Modified:18 Nov 2009 16:07

Repository Staff Only: item control page