Load-balancing performance of consistent hashing: Asymptotic analysis of random node join Academic Article

abstract

• Balancing of structured peer-to-peer graphs, including their zone sizes, has recently become an important topic of distributed hash table (DHT) research. To bring analytical understanding into the various peer-join mechanisms based on consistent hashing, we study how zone-balancing decisions made during the initial sampling of the peer space affect the resulting zone sizes and derive several asymptotic bounds for the maximum and minimum zone sizes that hold with high probability. Several of our results contradict those of prior work and shed new light on the theoretical performance limitations of consistent hashing. We use simulations to verify our models and compare the performance of the various methods using the example of recently proposed de Bruijn DHTs. 2007 IEEE.

authors

• Loguinov, Dmitri

published proceedings

• IEEE-ACM TRANSACTIONS ON NETWORKING

author list (cited authors)

• Wang, X., & Loguinov, D.

citation count

• 23

complete list of authors

• Wang, Xiaoming||Loguinov, Dmitri

publication date

• August 2007

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• IEEE/ACM Transactions on Networking  Journal

keywords

• Asymptotic Bounds
• Balls-into-bins
• Consistent Hashing
• Load Balancing
• Peer-to-peer (p2p)

Digital Object Identifier (DOI)

• 10.1109/TNET.2007.893881

start page

• 892

end page

• 905

volume

• 15

issue

• 4

URL

• http%3A%2F%2Fdx.doi.org%2F10.1109%2Ftnet.2007.893881