Balanced Allocation: Memory Performance Tradeoffs

Details Balanced Allocation: Memory Performance Tradeoffs Balanced Allocation: Memory Performance Tradeoffs

2009-01-09

arxiv.org/abs/0901.1155v1

Computer Science

Data Structures and Algorithms

Scientific paper

Suppose that we sequentially put $n$ balls into $n$ bins. If we put each ball into a random bin then the heaviest bin will contain $\log n /\log\log n$ balls (w.h.p.). However, Azar, Broder, Karlin and Upfal showed that if for each ball we choose two bins at random and put it in the least loaded bin among the two then the heaviest bin will contain only $\log\log n$ balls (w.h.p). How much memory do we need to implement this scheme? We need roughly $\log\log\log n$ bits per bin, and $n\log\log\log n$ bits in total. Let us assume now that we have limited amount of memory. For each ball, we are given two random bins and we have to put the ball into one of them. Our goal is to minimize the load of the heaviest bin. We prove that if we have $n^{1-\delta}$ bits then the heaviest bin will contain at least $\Omega(\delta \log n/\log\log n)$ balls. The bound is tight in the communication complexity model.

Affiliated with

Also associated with

No associations

Rating

Balanced Allocation: Memory Performance Tradeoffs 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: Memory Performance Tradeoffs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Balanced Allocation: Memory Performance Tradeoffs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-544025