## 2009 Probability Seminar - 09

- Date: 04/08/2009

University of British Columbia

Choice-memory tradeoff in allocations

Consider the classical balls-and-bins setup: n balls are thrown

independently and uniformly into n bins. The most loaded bin then has

log n/log log n balls with high probability. What happens when instead

of throwing balls completely by random, there is an allocation

algorithm which is given k uniformly and independently selected bins to

choose from for the location of each ball? A well known result of Azar,

Broder, Karlin & Upfal states that one can then achieve a maximal

load of log_k log n, simply by putting each ball in the less loaded of

the k optional bins. In order to implement this simple algorithm, one

needs to keep track of the status of the entire array of n bins, which

requires about n bits of memory.

The problem of what can be achieved with less memory was raised by Itai

Benjamini. The main result in this talk is that, generally speaking,

there is a tradeoff between the number of choices, k, and the memory,

m. That is, when km>>n one can achieve a constant maximal load,

while for km<

3:00pm-4:00pm, WMAX 216