research-article

Building a reliable P2P system out of unreliable P2P clients: the case of KAD

Authors:

Ernst W. BiersackAuthors Info & Claims

CoNEXT '07: Proceedings of the 2007 ACM CoNEXT conference

Article No.: 28, Pages 1 - 12

https://doi.org/10.1145/1364654.1364690

Published: 10 December 2007 Publication History

Abstract

Distributed Hash Tables (DHT) provide a framework for managing information in a large distributed network of nodes. One of the main challenges DHT systems must face is node churn, i.e., nodes can arrive and depart at any time. To assure that information published in a DHT remains available despite node churn is equivalent to building a reliable system out of unreliable components.

In this paper we analyze KAD, a widely deployed DHT system. We focus on how to assure that information published in KAD remains available despite churn. We apply reliability theory to understand how the probability of finding an object published in KAD evolves over time. We also evaluate the cost, in terms of message exchanges, associated with the publishing scheme.

Once we have identified the main weaknesses of the existing system, we propose an improved publishing scheme that is able to assure the same reliability but at a dramatically reduced cost. By exploiting knowledge about the lifetime of the nodes used to store the information, it is possible to reduce the publishing cost by one order of magnitude.

References

[1]

M. Steiner, E. W. Biersack, and T. En-Najjary, "Actively Monitoring Peers in Kad," in Proc. of IPTPS, Bellevue, WA, USA, Feb. 2007.

[2]

M. Steiner, T. Ennajjary, and E. W. Biersack, "A Global View of KAD," in Proc. of IMC, San Diego, CA, USA, Oct. 2007.

Digital Library

[3]

D. Stutzbach, and R. Rejaie, "Improving Lookup Performance over a Widely-Deployed DHT," in Proc. of INFOCOM, Barcelona, Spain, April 2006.

[4]

D. Stutzbach, and R. Rejaie, "Understanding Churn in Peer-to-Peer Networks," in Proc. of IMC, Rio de Janeiro, Brazil, Oct. 2006.

Digital Library

[5]

Y. Qiao, and F. E. Bustamante, "Structured and Unstructured Overlays Under the Microscope -- A Measurement-based View of Two P2P Systems That People Use," in Proc. of the USENIX Annual Technical Conference, June 2006.

Digital Library

[6]

J. Li, J. Stribling, R. Morris, M. F. Kaashoek, and T. M. Gil, "A performance vs. cost framework for evaluating DHT design tradeoffs under churn," in Proc. of INFOCOM, Miami, FL, USA, Mar. 2005.

[7]

D. Liben-Nowell, H. Balakrishnan, and D. Karger, "Analysis of the Evolution of Peer-to-Peer Systems," in Proc. of PODC, Monterey, CA, USA, July 2002.

Digital Library

[8]

S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz, "Handling Churn in a DHT," in Proc. of the USENIX Annual Technical Conference, June 2004

Digital Library

[9]

R. Bhagwan, S. Savage, and G. M. Voelker, "Understanding Availability," in Proc. of IPTPS, February 2003.

[10]

R. J. Dunn, J. Zahorjan, S. D. Gribble, H. M. Levy, "Presence-Based Availability and P2P Systems," in Proc. of IEEE P2P 2005, Konstanz, Germany, September 2005.

Digital Library

[11]

D. Wu, Y. Tian, and K. W. Ng, "Analytical Study on Improving DHT Lookup Performance under Churn," in Proc. of IEEE P2P 2006, Cambridge, UK, Sep. 2006.

Digital Library

[12]

P. Ji, Z. Ge, J. Kurose, and D. Towsley, "A Comparison of Hard-state and Soft-state Signaling Protocols" IEEE/ACM Transactions on Networking, Vol. 15, No. 2, pp. 281 294, Apr. 2007.

Digital Library

[13]

V. Duvvuri, P. Shenoy, and R. Tewari, "Adaptive Leases: A Strong Consistency Mechanism for the World Wide Web," IEEE Transactions on Knowledge and Data Engineering, Vol. 5, No. 5, pp. 1266--1276, Sept. 2003.

Digital Library

[14]

G. Pierre, M. van Steen, and A. S. Tanenbaum, "Dynamically Selecting Optimal Distribution Strategies for Web Documents," IEEE Transactions on Computers, Vol. 51, No. 6, pp. 637--651, June 2002.

Digital Library

[15]

M. Rausand, and A. Hoyland, "System Reliability Theory: Models, Statistical Methods, and Applications," John Wiley & Sons, 1994.

[16]

A. T. Gai, and L. Viennot, "Optimizing and Balancing Load in Fully Distributed P2P File Sharing Systems," in Proc. of ICIW, Feb 2006.

Digital Library

[17]

N. Prabhu, "Stochastic processes: basic theory and its applications," New York: Macmillan, 1965

[18]

O. G. Okogbaa, and X. Peng, "Time Series Intervention Analysis for Preventive/Predictive Maintenance Management of Multiunit Systems," in Proc. IEEE SMC, San Diego, CA, USA, Oct. 1998.

[19]

Y. Yang, and G.-A. Klutke, "Improved Inspection Schemes for Deteriorating Equipment," Probability in the Engineering and Informational Sciences, Vol. 14, pp. 445--460, 2000.

Digital Library

[20]

L. Cui, M. Xie, and H. T. Loh, "Inspection schemes for general systems," IIE TRANSACTIONS, vol. 36, n. 9, pages 817--826, 2004.

[21]

J. Gurland, and J. Sethuraman, "How Pooling Failure Data May Reverse Increasing Failure Rates," Journal of the American Statistical Association, Vol. 90, No. 432 (Dec., 1995), pp. 1416--1423.

[22]

KAD traces, http://www.eurecom.fr/~btroup/kadtraces/, Oct. 2007.

Cited By

Pérez-Miguel CMendiburu AMiguel-Alonso J(2015)Modeling the availability of CassandraJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.08.00186:C(29-44)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.jpdc.2015.08.001
Bingshuang Liu Tao Wei Jianyu Zhang Jun Li Wei Zou Mo Zhou (2012)Revisiting why Kad lookup fails2012 IEEE 12th International Conference on Peer-to-Peer Computing (P2P)10.1109/P2P.2012.6335808(37-42)Online publication date: Sep-2012
https://doi.org/10.1109/P2P.2012.6335808
Locher TSchmid SWattenhofer R(2011)eDonkey & eMule's Kad: Measurements & AttacksFundamenta Informaticae10.5555/2361347.2361348109:4(383-403)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.5555/2361347.2361348
Show More Cited By

Index Terms

Building a reliable P2P system out of unreliable P2P clients: the case of KAD

Recommendations

Push-pull incentive-based P2P live media streaming system

Peer-to-peer (P2P) file sharing has become increasingly popular, accounting for as much as 70% of Internet traffic by some estimates. Recently, we have been witnessing the emergence of a new class of popular P2P applications, namely, P2P audio and video ...
Understanding churn in peer-to-peer networks
IMC '06: Proceedings of the 6th ACM SIGCOMM conference on Internet measurement

The dynamics of peer participation, or churn, are an inherent property of Peer-to-Peer (P2P) systems and critical for design and evaluation. Accurately characterizing churn requires precise and unbiased information about the arrival and departure of ...
Bandwidth trading in BitTorrent-like P2P networks for content distribution

Bandwidth trading schemes give peers an incentive to provide upload bandwidth to other peers in a P2P network for fast file distribution. A popular example is the tit-for-tat strategy used in the BitTorrent protocol. Although this game theoretical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '07: Proceedings of the 2007 ACM CoNEXT conference

December 2007

448 pages

ISBN:9781595937704

DOI:10.1145/1364654

General Chairs:
Jim Kurose
University of Massachusetts
,
Henning Schulzrinne
Columbia University

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Alcatel-Lucent
SIGCOMM: ACM Special Interest Group on Data Communication
Thomson
CISCO
IMDEA
IBM: IBM

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 December 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Sixth Framework Programme

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
216
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pérez-Miguel CMendiburu AMiguel-Alonso J(2015)Modeling the availability of CassandraJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.08.00186:C(29-44)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.jpdc.2015.08.001
Bingshuang Liu Tao Wei Jianyu Zhang Jun Li Wei Zou Mo Zhou (2012)Revisiting why Kad lookup fails2012 IEEE 12th International Conference on Peer-to-Peer Computing (P2P)10.1109/P2P.2012.6335808(37-42)Online publication date: Sep-2012
https://doi.org/10.1109/P2P.2012.6335808
Locher TSchmid SWattenhofer R(2011)eDonkey & eMule's Kad: Measurements & AttacksFundamenta Informaticae10.5555/2361347.2361348109:4(383-403)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.5555/2361347.2361348
Carra DSteiner MMichiardi P(2011)Adaptive load balancing in KAD2011 IEEE International Conference on Peer-to-Peer Computing10.1109/P2P.2011.6038666(92-101)Online publication date: Aug-2011
https://doi.org/10.1109/P2P.2011.6038666
Timpanaro JCholez TChrisment IFestor O(2011)When KAD Meets BitTorrent - Building a Stronger P2P NetworkProceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum10.1109/IPDPS.2011.318(1635-1642)Online publication date: 16-May-2011
https://dl.acm.org/doi/10.1109/IPDPS.2011.318
Ohmata HIshikawa KSakakihara HKamiwada T(2011)Churn-resistant method for DHT-based content delivery systems2011 IEEE Consumer Communications and Networking Conference (CCNC)10.1109/CCNC.2011.5766536(537-538)Online publication date: Jan-2011
https://doi.org/10.1109/CCNC.2011.5766536
Ou ZHarjula EKassinen OYlianttila M(2010)Performance evaluation of a Kademlia-based communication-oriented P2P system under churnComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2009.09.02254:5(689-705)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1016/j.comnet.2009.09.022
Steiner MEn-Najjary TBiersack E(2009)Long term study of peer behavior in the KAD DHTIEEE/ACM Transactions on Networking10.1109/TNET.2008.200905317:5(1371-1384)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1109/TNET.2008.2009053
Lo Cigno RPecorella TSereno MVeltri L(2009)Peer-to-Peer beyond file sharingProceedings of the 2009 IEEE International Symposium on Parallel&Distributed Processing10.1109/IPDPS.2009.5160958(1-8)Online publication date: 23-May-2009
https://dl.acm.org/doi/10.1109/IPDPS.2009.5160958
Jia AChiu D(2008)Designs and Evaluation of a Tracker in P2P NetworksProceedings of the 2008 Eighth International Conference on Peer-to-Peer Computing10.1109/P2P.2008.11(227-230)Online publication date: 8-Sep-2008
https://dl.acm.org/doi/10.1109/P2P.2008.11

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents