Brief Announcement: A Generalization of Multiple Choice Balls-into-Bins

摘要

In the multiple choice balls into bins problem, each ball is placed into the least loaded one out of d bins chosen independently and uniformly at random (i.u.r.). It is known that the maximum load after n balls are placed into n bins is ln ln n/ ln d + O(1). In this paper, we consider a variation of the standard multiple choice process. For k < d, we place k balls at a time into k least loaded bins among d possible locations chosen i.u.r. We provide the maximum load in terms of k, d and n. The maximum load in the standard multiple choice problem can be derived from our general formulation as a special case with k = 1. More interestingly, our result indicates that, for any d ≤ (ln n)~(Θ(1)) and k < d, the maximum load is still O(ln ln n). Our allocation scheme can be employed as optimal file replication and data partition policies in distributed file systems and databases. When a new file is created, A-copies/fragments of the file are stored into k least loaded among d randomly chosen servers, where k is a tunable parameter that may depend on the level of load balance, file availability, fault tolerance, and popularity or size of a file.