2012/10/30 by Jakarin Chawachat, Jittat Fakcharoenphol, Chawachat, Jakarin +1
Computer Science · #Caching and Content Delivery #Distributed #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #Opportunistic and Delay-Tolerant Networks #Parallel #Peer-to-Peer Network Technologies #and Cluster Computing (cs.DC) #cs.DC #cs.NI
paper · pdf · doi:10.48550/arxiv.1210.7954
(21 pages, 3 figures)
openalex publication_date 2012/10/30 · arxiv created 2013/04/28 · arxiv updated 2013/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Random hashing is a standard method to balance loads among nodes in Peer-to-Peer networks. However, hashing destroys locality properties of object keys, the critical properties to many applications, more specifically, those that require range searching. To preserve a key order while keeping loads balanced, Ganesan, Bawa and Garcia-Molina proposed a load-balancing algorithm that supports both object insertion and deletion that guarantees a ratio of 4.237 between the maximum and minimum loads among nodes in the network using constant amortized costs. However, their algorithm is not straightforward to implement in real networks because it is recursive. Their algorithm mostly uses local operations with global max-min load information. In this work, we present a simple non-recursive algorithm using essentially the same primitive operations as in Ganesan \em et al.'s work. We prove that for insertion and deletion, our algorithm guarantees a constant max-min load ratio of 7.464 with constant amortized costs.