iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/3-540-45749-6_29
Balanced-Replication Algorithms for Distribution Trees | SpringerLink
Skip to main content

Balanced-Replication Algorithms for Distribution Trees

  • Conference paper
  • First Online:
Algorithms — ESA 2002 (ESA 2002)

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

Included in the following conference series:

Abstract

In many Internet applications, requests for a certain object are routed bottom-up over a tree where the root of the tree is the node containing the object. When an object becomes popular, the root node of the tree may become a hotspot. Therefore many applications allow intermediate nodes to acquire the ability to serve the requests, for example by caching the object. We call such distinguished nodes primed. We propose and analyse different algorithms where nodes decide when to become primed; these algorithms balance the maximum load on a node and the number of primed nodes.

Many applications require both fully distributed decisions and smooth convergence to a stable set of primed nodes. We first present optimal algorithms which require communication across the tree. We then consider the natural previously proposed THRESHOLD algorithm, where a node becomes primed when the incoming flow of requests exceeds a threshold. We show examples where THRESHOLD exhibits undesirable behavior during convergence. Finally, we propose another fully distributed algorithm, GAP, which converges gracefully.

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

Access this chapter

Subscribe and save

Springer+ Basic
$34.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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • 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. B. Awerbuch, Y. Bartal, and A. Fiat. Distributed paging for general networks. In Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, pages 574–583. ACM-SIAM, 1996.

    Google Scholar 

  2. Open Source Community. Gnutella. In http://gnutella.wego.com/, 2001.

  3. Napster Inc. The napster homepage. In http://www.napster.com/, 2001.

  4. D. Karger, Lehman E., T. Leighton, M. Levine, D. Lewin, and R. Panigraphy. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web. In Proc. 29th Annual ACM Symposium on Theory of Computing, pages 654–663. ACM, 1997.

    Google Scholar 

  5. M.R. Korupolu, C. G. Plaxton, and R. Rajaraman. Placement algorithms for hierarchical cooperative caching. In Proc. 10th ACM-SIAM Symposium on Discrete Algorithms. ACM, 1999.

    Google Scholar 

  6. B. Li, M. Golin, G. Italiano, X. Deng, and K. Sohraby. On the optimal placement of Web proxies in the Internet. In Proceedings of the IEEE Infocom’ 99 Conference, 1999.

    Google Scholar 

  7. Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker. Search and replication in unstructured peer-to-peer networks. In Proceedings of the ACM SIGMETRICS’02 Conference, 2002.

    Google Scholar 

  8. C.G. Plaxton, R. Rajaraman, and A.W. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proc. 9th annual ACM Symposium on Parallel Algorithms and Architectures, pages 311–320. ACM, 1997.

    Google Scholar 

  9. S. Ratnassamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Proceedings of the ACM SIGCOMM’01 Conference, 2001.

    Google Scholar 

  10. I. Stoica, R. Morris, D. Karger, and H. Frans Kaashoek, M. ad Balakrishnana. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of the ACM SIGCOMM’01 Conference, 2001.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Cohen, E., Kaplan, H. (2002). Balanced-Replication Algorithms for Distribution Trees. In: Möhring, R., Raman, R. (eds) Algorithms — ESA 2002. ESA 2002. Lecture Notes in Computer Science, vol 2461. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45749-6_29

Download citation

  • DOI: https://doi.org/10.1007/3-540-45749-6_29

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

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

  • Online ISBN: 978-3-540-45749-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics