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

A Simple Fault Tolerant Distributed Hash Table

  • Conference paper
Peer-to-Peer Systems II (IPTPS 2003)

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

Included in the following conference series:

Abstract

We introduce a distributed hash table (DHT) with logarithmic degree and logarithmic dilation. We show two lookup algorithms. The first has a message complexity of log n and is robust under random deletion of nodes. The second has parallel time of log n and message complexity of log2 n. It is robust under spam induced by a random subset of the nodes. We then show a construction which is fault tolerant against random deletions and has an optimal degree-dilation tradeoff. The construction has improved parameters when compared to other DHT’s. Its main merits are its simplicity, its flexibility and the fresh ideas introduced in its design. It is very easy to modify and to add more sophisticated protocols, such as dynamic caching and erasure correcting codes.

Research supported in part by the RAND/APX grant from the EU Program IST.

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. Byers, J.W., Luby, M., Mitzenmacher, M., Rege, A.: A digital fountain approach to reliable distribution of bulk data. In: SIGCOMM, pp. 56–67 (1998)

    Google Scholar 

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

    Google Scholar 

  3. Karger, D.R., Lehman, E., Leighton, F.T., Panigrahy, R., Levine, M.S., Lewin, D.: Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In: ACM Symposium on Theory of Computing, May 1997, pp. 654–663 (May 1997)

    Google Scholar 

  4. Malkhi, D., Naor, M., Ratajczak, D.: Viceroy: A scalable and dynamic emulation of the butterfly. In: PODC (2002)

    Google Scholar 

  5. Naor, M., Wieder, U.: Novel architectures for p2p applications: the continuousdiscrete approach (2002), http://www.wisdom.weizmann.ac.il/~uwiede

  6. Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A scalable content addressable network. In: Proc. ACM SIGCOMM, San Diego CA, August 2001, pp. 161–172 (2001)

    Google Scholar 

  7. 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, MIT Faculty Club, Cambridge, MA, USA (2002)

    Google Scholar 

  8. Stoica, I., Morris, R., Karger, D., Kaashoek, F., Balakrishnan, H.: Chord: A scalable Peer-To-Peer lookup service for internet applications. In: Proceedings of the 2001 ACM SIGCOMM Conference, pp. 149–160 (2001)

    Google Scholar 

  9. Weatherspoon, H., Kubiatowicz, J.D.: Erasure coding vs. replication: A quantitative comparison. In: First International Workshop on Peer-to-Peer Systems, MIT Faculty Club, Cambridge, MA, USA (2002)

    Google Scholar 

  10. Zhao, B.Y., Kubiatowicz, J.: Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB CSD 01-1141, University of California at Berkeley, Computer Science Department (2001)

    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

Naor, M., Wieder, U. (2003). A Simple Fault Tolerant Distributed Hash Table. In: Kaashoek, M.F., Stoica, I. (eds) Peer-to-Peer Systems II. IPTPS 2003. Lecture Notes in Computer Science, vol 2735. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45172-3_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-45172-3_8

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-40724-9

  • Online ISBN: 978-3-540-45172-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics