Randomized load balancing by joining and splitting bins

作     者：Aspnes, James Yin, Yitong 

作者机构：Nanjing Univ State Key Lab Novel Software Technol Nanjing Jiangsu Peoples R China Yale Univ Dept Comp Sci New Haven CT 06520 USA 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2012年第112卷第8-9期

页      面：309-313页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSF [CNS-0435201, CCF-0916389] National Science Foundation of China [61003023, 61021062] Direct For Computer & Info Scie & Enginr Division of Computing and Communication Foundations Funding Source: National Science Foundation 

主　　题：Randomized algorithms Load balancing 

摘      要：We analyze the performance of a very natural randomized load balancing scheme: uniformly joining and splitting weighted bins. We develop a norm-based technique for analyzing this simple procedure. By applying the technique, we prove several bounds for the expected load factor. Specifically, if we keep uniformly splitting the bins without joining them, the expected load factor is between Omega(n(0.5)) and O(n(0.742)), however, if we alternatively join and split bins, the expected load factor converges to O(n(1/root 1/2 log2 n)). These bounds justify the intuition that the power of being adaptive to the current loads is essential for load balancing tasks, and they also show a somehow surprising phenomenon that joins can actually help load balancing if such power is not available. (C) 2012 Elsevier B.V. All rights reserved.