Chains-into-bins processes

详细信息	查看全文 | 推荐本文 |

• 作者：Tu臒kan Batu^a ; ^{t.batu@lse.ac.uk} ; Petra Berenbrink^b ; ^{petra@cs.sfu.ca} ; Colin Cooper^c ; ^{colin.cooper@kcl.ac.uk}
• 关键词：Balls-into-bins processes ; Chains-into-bins processes ; Random processes ; Online load balancing
• 刊名：Journal of Discrete Algorithms
• 出版年：2012
• 期刊代码：10_15708667
• 类别：mt
• 出版时间：July, 2012
• 卷：14
• 期：Complete
• 页码：21-28
• 文件大小：177 K

摘要

The study of balls-into-bins processes or occupancy problems has a long history. These processes can be used to translate realistic problems into mathematical ones in a natural way. In general, the goal of a balls-into-bins process is to allocate a set of independent objects (tasks, jobs, balls) to a set of resources (servers, bins, urns) and, thereby, to minimize the maximum load. In this paper, we analyze the maximum load for the chains-into-bins problem, which is defined as follows. There are n bins, and m objects to be allocated. Each object consists of balls connected into a chain of length 鈩?/em>, so that there are m鈩?/em> balls in total. We assume the chains cannot be broken, and that the balls in one chain have to be allocated to 鈩?/em> consecutive bins. We allow each chain d independent and uniformly random bin choices for its starting position. The chain is allocated using the rule that the maximum load of any bin receiving a ball of that chain is minimized. We show that, for and , the maximum load is with probability .