Assessing the Impact of Node Churn to Random Walk-Based Overlay Construction

Kyungbaek KIM  

IEICE TRANSACTIONS on Information and Systems   Vol.E94-D   No.9   pp.1830-1833
Publication Date: 2011/09/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E94.D.1830
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Information Network
random walk,  random scale-free overlay,  node churn,  decision function,  

Full Text: PDF>>
Buy this Article

Distributed systems desire to construct a random overlay graph for robustness, efficient information dissemination and load balancing. A random walk-based overlay construction is a promising alternative to generate an ideal random scale free overlay in distributed systems. However, a simple random walk-based overlay construction can be affected by node churn. Especially, the number of edges increases and the degree distribution is skewed. This inappropriate distortion can be exploited by malicious nodes. In this paper, we propose a modified random walk-based overlay construction supported by a logistic/trial based decision function to compensate the impact of node churn. Through event-driven simulations, we show that the decision function helps an overlay maintain the proper degree distribution, low diameter and low clustering coefficient with shorter random walks.