[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Asymptotically Efficient Approaches to Fault-Tolerance in Peer-to-Peer Networks

  • Conference paper
Distributed Computing (DISC 2003)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2848))

Included in the following conference series:

Abstract

In this paper, we show that two peer-to-peer systems, Pastry [13] and Tapestry [17] can be made tolerant to certain classes of failures and a limited class of attacks. These systems are said to operate properly if they can find the closest node matching a requested ID. The system must also be able to dynamically construct the necessary routing information when new nodes enter or the network changes. We show that with an additional factor of O(log2 n) storage overhead and O(log n) communication overhead, they can continue to achieve both of these goals in the presence of a constant fraction nodes that do not obey the protocol. Our techniques are similar in spirit to those of Saia et al. [14] and Naor and Wieder [10]. Some simple simulations show that these techniques are useful even with constant overhead.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Castro, M., Druschel, P., Hu, Y.C., Rowstron, A.: Exploiting network proximity in peer-to-peer overlay networks. In: Proceedings of the International Workshop on Future Directions in Distributed Computing (2002)

    Google Scholar 

  2. Castro, M., Druschel, P., Ganesh, A., Rowstron, A., Wallach, D.S.: Secure routing for structured peer-to-peer overlay networks. In: Proceedings of the 5th Symposium on Operating Systems Desgin and Implementation, pp. 299–314 (2002)

    Google Scholar 

  3. Douceur, J.: The Sybil attack. In: Druschel, P., Kaashoek, M.F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol. 2429, pp. 251–260. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  4. Fiat, A., Saia, J.: Censorship resistant peer-to-peer content addressable networks. In: Proceedings of Symposium on Discrete Algorithms (2002)

    Google Scholar 

  5. Harvey, N.J.A., Jones, M.T.M.B., Sarouiu, S., Wolman, A.: Skipnet: A peer-to-peer overlay network. In: Proceedings of the fourth USENIX Symposium on Internet Technologies and Systems (2003)

    Google Scholar 

  6. Hildrum, K., Kubiatowicz, J., Rao, S.: Improved bounds on finding nearest neighbors in growth-restricted metrics, http://www.cs.berkeley.edu/~hildrum/nn.ps

  7. Hildrum, K., Kubiatowicz, J.D., Rao, S., Zhao, B.Y.: Distributed object location in a dynamic network. In: Proceedings of the Fourteenth ACM Symposium on Parallel Algorithms and Architectures (2002)

    Google Scholar 

  8. Malkhi, D., Naor, M., Ratajczak, D.: Viceroy: a scalable and dynamic emulation of the butterfly. In: Proceedings of the twenty-first annual symposium on Principles of distributed computing, pp. 183–192 (2002)

    Google Scholar 

  9. Naor, M., Wieder, U.: Novel architectures for p2p applications: the continuous-discrete approach. In: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, pp. 50–59 (2003)

    Google Scholar 

  10. Naor, M., Wieder, U.: A simple fault tolerant distributed hash table. In: Second International Workshop on Peer-to-Peer Systems (2003)

    Google Scholar 

  11. Plaxton, C.G., Rajaraman, R., Richa, A.W.: Accessing nearby copies of replicated objects in a distributed environment. In: Proc. of the 9th Annual Symp. on Parallel Algorithms and Architectures, pp. 311–320 (1997)

    Google Scholar 

  12. Ratnasamy, S., Francis, P., Handley, M., Karp, R., Schenker, S.: A scalable content-addressable network. In: Proc. of SIGCOMM, pp. 161–172 (2001)

    Google Scholar 

  13. Rowstron, A., Druschel, P.: Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In: Proceedings of IFIP/ACM Middleware (2001)

    Google Scholar 

  14. Saia, J., Fiat, A., Gribble, S., Karlin, A.R., Saroiu, S.: Dynamically fault-tolerant content addressable networks. In: First International Workshop on Peer-to-Peer Systems (2002)

    Google Scholar 

  15. Sit, E., Morris, R.: Security considerations for peer-to-peer distributed hash tables. In: Proceedings of the first International Workshop on Peer-to-Peer Systems, Cambridge, MA (2002)

    Google Scholar 

  16. Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakr-ishnan, H.: Chord: A scalable peer-to-peer lookup service for internet applications. In: Proc. of SIGCOMM, pp. 149–160 (2001)

    Google Scholar 

  17. Zhao, B.Y., Huang, L., Rhea, S.C., Stribling, J., Joseph, A.D., Kubiatowicz, J.D.: Tapestry: A global-scale overlay for rapid service deployment. IEEE Journal on Selected Areas in Communications (2003); Special Issue on Service Overlay Networks (to appear)

    Google Scholar 

  18. Zhao, B.Y., Joseph, A., Kubiatowicz, J.: Locality-aware mechanisms for large-scale networks. In: Proc. of Workshop on Future Directions in Distributed Comp. (2002)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hildrum, K., Kubiatowicz, J. (2003). Asymptotically Efficient Approaches to Fault-Tolerance in Peer-to-Peer Networks. In: Fich, F.E. (eds) Distributed Computing. DISC 2003. Lecture Notes in Computer Science, vol 2848. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39989-6_23

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-39989-6_23

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-20184-7

  • Online ISBN: 978-3-540-39989-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics