Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. On de Bruijn Routing in Distributed Hash Tables: There and Back Again
 
conference paper

On de Bruijn Routing in Distributed Hash Tables: There and Back Again

Datta, Anwitaman  
•
Girdzijauskas, Sarunas
•
Aberer, Karl  
2004
P2P2004, The 4th IEEE International Conference on Peer-to-Peer Computing
The Fourth IEEE International Conference on Peer-to-Peer Computing

We show in this paper that de Bruijn networks, despite providing efficient search while using constant routing table size, as well as simplicity of the understanding and implementation of such networks, are unsuitable where key distribution will be uneven, a realistic scenario for most practical applications. In presence of arbitrarily skewed data distribution, it has only recently been shown that some traditional P2P overlay networks with non-constant (typically logarithmic) in stead of constant routing table size can meet conflicting objectives of storage load balancing as well as search efficiency. So this paper, while showing that de Bruijn networks fail to meet these dual objectives, opens up a more general problem for the research community as to whether P2P systems with constant routing table can at all achieve the conflicting objectives of retaining search efficiency as well as storage load balancing, while preserving key ordering (which leads to uneven key distribution).

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

de_Bruijn_routing.pdf

Access type

openaccess

Size

103.96 KB

Format

Adobe PDF

Checksum (MD5)

b1b37bbefd571830a667a223733e0b70

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés