Pacific Institute for the Mathematical Sciences - PIMS

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