A simpler load-balancing algorithm for range-partitioned data in peer-to-peer systems

被引:4
作者
Chawachat, Jakarin [1 ]
Fakcharoenphol, Jittat [1 ]
机构
[1] Kasetsart Univ, Dept Comp Engn, Bangkok, Thailand
关键词
load-balancing; range searching; peer-to-peer; amortized analysis; potential function; SERVICE; QUERIES;
D O I
10.1002/net.21627
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
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's key insertion and deletion with a guaranteed max-min load ratio, the imbalance ratio, of 4.237 using constant amortized costs. Nonetheless, the algorithm is not straightforward to implement in real networks because of its recursiveness. The algorithm mostly uses local operations with global max-min load information. In this work, we present a simple nonrecursive algorithm using essentially the same primitive operations as in Ganesan et al.'s work. For insertions and deletions, our algorithm guarantees a proven constant imbalance ratio of 7.464 with constant amortized costs. (c) 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(3), 235-249 2015
引用
收藏
页码:235 / 249
页数:15
相关论文
共 50 条
[31]   Reliability of data in structured peer-to-peer systems [J].
Rieche, S ;
Wehrle, K ;
Landsiedel, O ;
Götz, S ;
Petrak, L .
2004 INTERNATIONAL WORKSHOP ON HOT TOPICS IN PEER-TO-PEER SYSTEMS, PROCEEDINGS, 2004, :108-113
[32]   Parallel Load Balancing Strategies for Tree-Structured Peer-to-Peer Networks [J].
Chen, Yaw-Huei ;
Ju, Yu-Ren .
ADVANCES IN DATA AND WEB MANAGEMENT, PROCEEDINGS, 2009, 5446 :468-479
[33]   ACHIEVING LOAD BALANCING IN HETEROGENEOUS PEER-TO-PEER NETWORKS BY ALLOCATING AND REALLOCATING PROCESS [J].
Ibrahim, Niyas ;
Thanabal, M. S. .
ICCN: 2008 INTERNATIONAL CONFERENCE ON COMPUTING, COMMUNICATION AND NETWORKING, 2008, :608-614
[34]   HAND: An overlay optimization algorithm in peer-to-peer systems [J].
Chen, Xiaoming ;
Li, Zhoujun ;
Zhuang, Yongzhen ;
Han, Jinsong ;
Chen, Lei .
HIGH PERFORMANCE COMPUTING AND COMMUNICATIONS, PROCEEDINGS, 2006, 4208 :290-299
[35]   Towards Secure Data Exchange in Peer-to-Peer Data Management Systems [J].
Rahman, Sk Md Mizanur ;
Masud, Mehedi ;
Noman, Ali N. M. ;
Alamri, Atif ;
Hassan, Mohammad Mehedi .
APPLIED MATHEMATICS & INFORMATION SCIENCES, 2014, 8 (06) :2775-2787
[36]   Peer-to-peer data structures for cooperative traffic information systems [J].
Rybicki, Jedrzej ;
Scheuermann, Bjoern ;
Mauve, Martin .
PERVASIVE AND MOBILE COMPUTING, 2012, 8 (02) :194-209
[37]   Dynamic load sharing in peer-to-peer systems - When some peers are more equal than others [J].
Serbu, Sabina ;
Bianchi, Silvia ;
Kropf, Peter ;
Felber, Pascal .
IEEE INTERNET COMPUTING, 2007, 11 (04) :53-61
[38]   Building a network-aware and load-balanced peer-to-peer system for range queries [J].
Joung, Yuh-Jzer ;
Wong, Wing-Tat ;
Huang, Hsiao-Mei ;
Chou, Yi-Fang .
COMPUTER NETWORKS, 2012, 56 (08) :2148-2167
[39]   ASAP: An Advertisement-based Search Algorithm for Unstructured Peer-to-peer Systems [J].
Gu, Peng ;
Wang, Jun ;
Cai, Hailong .
2007 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING WORKSHOPS (ICPP), 2007, :63-+
[40]   A distance based semantic search algorithm for peer-to-peer open hypermedia systems [J].
Zhou, J ;
Dialani, V ;
De Roure, D ;
Hall, W .
PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES, PDCAT'2003, PROCEEDINGS, 2003, :7-11