Call for Papers
About the Journal
Editorial Board
Publication Ethics
Instructions for Authors
Announcements
Current Issue
Back Issues
Search for Articles
Categories
Back Issues
 

JCSE, vol. 2, no. 3, pp.249-273, September, 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:   117 Downloads, 3678 View

 
 
ⓒ Copyright 2010 KIISE – All Rights Reserved.    
Korean Institute of Information Scientists and Engineers (KIISE)   #401 Meorijae Bldg., 984-1 Bangbae 3-dong, Seo-cho-gu, Seoul 137-849, Korea
Phone: +82-2-588-9240    Fax: +82-2-521-1352    Homepage: http://jcse.kiise.org    Email: office@kiise.org