On the Tradeoff between Resilience and Degree Overload in Dynamic P2P Graphs
14th IEEE International Conference on Peer-to-Peer Computing
Prior work has shown that resilience of random P2P graphs under dynamic node failure can be improved by age-biased neighbor selection that delivers outbound edges to more reliable users with higher probability. However, making the bias too aggressive may cause the group of nodes that receive connections to become small in comparison to graph size. As they become overloaded, these peers are forced to reject future connection requests, which leads to potentially unbounded join delays and high traffic overhead. To investigate these issues, we propose several analytical models for understanding the interplay between resilience and degree. We formulate a Pareto-optimal objective for this tradeoff, introduce new metrics of resilience and degree, analyze them under Pareto lifetimes, and discover that traditional techniques can be highly suboptimal in this setting. We then show evidence that optimization can be solved by a family of step-functions, which connect outgoing edges to uniformly random users whose age exceeds some threshold.
Copyright © 2014, IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Institute of Electrical and Electronics Engineers
Yao, Zhongmei; Cline, Daren B. H.; and Loguinov, Dmitri, "On the Tradeoff between Resilience and Degree Overload in Dynamic P2P Graphs" (2014). Computer Science Faculty Publications. 162.