DIMPLE: DynamIc Membership ProtocoL for Epidemic protocols

Epidemic protocols assume that information of a random set of nodes is provided at each protocol round. By definition, the random set needs to be chosen uniformly and randomly from the entire set to gossip with. Consequently, a node observes a different set of randomly chosen nodes at each different protocol round. Several proposals have addressed the issue of providing a different random set of nodes at each different round. In general, for large systems, this is done by creating a partial view of the entire membership at each node and exchanging part of the partial view among nodes. While many interesting properties of this approach have been found, investigation is needed to study the performance of this approach with practically high network churn. Without an action specifically designed for churn, shuffling would produce many dangling pointers in the partial view which point to an already left node. This in turn would significantly degrade the quality of epidemic protocols. The reason for the poor quality of the partial view is that the procedures of leave and join can take too long time to handle churn efficiently. To address this issue, an additional action of reinforcement and a new join procedure are proposed and evaluated in this paper. The reinforcement detects and removes dangling pointers at each shuffle more effectively, and the new join procedure accommodates a newly joining node remarkably fast. The subsequent simulations show that these ideas enhance the shuffling mechanism such that the system processes network churn much faster and the quality of the node degrees is significantly enhanced.