JCSE, vol. 2, no. 3, pp.249-273, 2008

DOI:

DIMPLE-II: Dynamic Membership Protocol for Epidemic Protocols

Jin Sun, Byung K. Choi Kwang-Mo Jung
Departments of Computer Science, Michigan Technological University, Houghton, MI, USA|Korea Electronics Technology Institute

Abstract: Epidemic protocols have two fundamental assumptions. One is the availability of a mechanismthat provides each node with a set of log(N) (fanout) nodes to gossip with at each cycle. Theother is that the network size N is known to all member nodes. While it may be trivial tosupport these assumptions in small systems, it is a challenge to realize them in large opendynamic systems, such as peer-to-peer (P2P) systems. Technically, since the most fundamentalparameter of epidemic protocols is log(N), without knowing the system size, the protocols willbe limited. Further, since the network churn, frequently observed in P2P systems, causes rapidmembership changes, providing a different set of log(N) at each cycle is a difficult problem. Inorder to support the assumptions, the fanout nodes should be selected randomly and uniformlyfrom the entire membership.This paper investigates one possible solution which addresses both problems; providing ateach cycle a different set of log(N) nodes selected randomly and uniformly from the entirenetwork under churn, and estimating the dynamic network size in the number of nodes. Thissolution improves the previously developed distributed algorithm called Shuffle to deal withchurn, and utilizes the Shuffle infrastructure to estimate the dynamic network size. Theeffectiveness of the proposed solution is evaluated by simulation. According to the simulationresults, the proposed algorithms successfully handle network churn in providing random log(N)fanout nodes, and practically and accurately estimate the network size. Overall, this workprovides insights in designing epidemic protocols for large scale open dynamic systems, wherethe protocols behave autonomically.

Keyword: No keyword

Full Paper:   122 Downloads, 4046 View