On the Tradeoff between Resilience and Degree Overload in Dynamic P2P Graphs

Author(s)

Zhongmei Yao, University of DaytonFollow
Daren B. H. Cline, Texas A & M University - College Station
Dmitri Loguinov, Texas A & M University - College Station

Document Type

Conference Paper

Publication Date

9-2014

Publication Source

14th IEEE International Conference on Peer-to-Peer Computing

Abstract

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.

ISBN/ISSN

2161-3559

Comments

Permission documentation is on file.

Copyright

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.

Publisher

Institute of Electrical and Electronics Engineers

Peer Reviewed

yes

eCommons Citation

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.
https://ecommons.udayton.edu/cps_fac_pub/162