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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Kyungbaek KIM, "Assessing the Impact of Node Churn to Random Walk-Based Overlay Construction" in IEICE TRANSACTIONS on Information,
vol. E94-D, no. 9, pp. 1830-1833, September 2011, doi: 10.1587/transinf.E94.D.1830.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E94.D.1830/_p
Copy
@ARTICLE{e94-d_9_1830,
author={Kyungbaek KIM, },
journal={IEICE TRANSACTIONS on Information},
title={Assessing the Impact of Node Churn to Random Walk-Based Overlay Construction},
year={2011},
volume={E94-D},
number={9},
pages={1830-1833},
abstract={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.},
keywords={},
doi={10.1587/transinf.E94.D.1830},
ISSN={1745-1361},
month={September},}
Copy
TY - JOUR
TI - Assessing the Impact of Node Churn to Random Walk-Based Overlay Construction
T2 - IEICE TRANSACTIONS on Information
SP - 1830
EP - 1833
AU - Kyungbaek KIM
PY - 2011
DO - 10.1587/transinf.E94.D.1830
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E94-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2011
AB - 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.
ER -