Computer Science – Data Structures and Algorithms
Scientific paper
2005-10-27
Computer Science
Data Structures and Algorithms
Scientific paper
In this paper, we study the two choice balls and bins process when balls are not allowed to choose any two random bins, but only bins that are connected by an edge in an underlying graph. We show that for $n$ balls and $n$ bins, if the graph is almost regular with degree $n^\epsilon$, where $\epsilon$ is not too small, the previous bounds on the maximum load continue to hold. Precisely, the maximum load is $\log \log n + O(1/\epsilon) + O(1)$. For general $\Delta$-regular graphs, we show that the maximum load is $\log\log n + O(\frac{\log n}{\log (\Delta/\log^4 n)}) + O(1)$ and also provide an almost matching lower bound of $\log \log n + \frac{\log n}{\log (\Delta \log n)}$. V{\"o}cking [Voc99] showed that the maximum bin size with $d$ choice load balancing can be further improved to $O(\log\log n /d)$ by breaking ties to the left. This requires $d$ random bin choices. We show that such bounds can be achieved by making only two random accesses and querying $d/2$ contiguous bins in each access. By grouping a sequence of $n$ bins into $2n/d$ groups, each of $d/2$ consecutive bins, if each ball chooses two groups at random and inserts the new ball into the least-loaded bin in the lesser loaded group, then the maximum load is $O(\log\log n/d)$ with high probability.
Kenthapadi Krishnaram
Panigrahy Rina
No associations
LandOfFree
Balanced Allocation on Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Balanced Allocation on Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Balanced Allocation on Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-500072