On the Tradeoff Between Resilience and Degree Overload in Dynamic P2P Graphs
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
2014 IEEE. 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.
name of conference
14-th IEEE International Conference on Peer-to-Peer Computing