Choice-memory tradeoff in allocations

Details Choice-memory tradeoff in allocations Choice-memory tradeoff in allocations

2009-01-26

arxiv.org/abs/0901.4056v4

Annals of Applied Probability 2010, Vol. 20, No. 4, 1470-1511

Mathematics

Combinatorics

Published in at http://dx.doi.org/10.1214/09-AAP656 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Inst

Scientific paper

10.1214/09-AAP656

In the classical balls-and-bins paradigm, where $n$ balls are placed independently and uniformly in $n$ bins, typically the number of bins with at least two balls in them is $\Theta(n)$ and the maximum number of balls in a bin is $\Theta(\frac{\log n}{\log \log n})$. It is well known that when each round offers $k$ independent uniform options for bins, it is possible to typically achieve a constant maximal load if and only if $k=\Omega(\log n)$. Moreover, it is possible w.h.p. to avoid any collisions between $n/2$ balls if $k>\log_2n$. In this work, we extend this into the setting where only $m$ bits of memory are available. We establish a tradeoff between the number of choices $k$ and the memory $m$, dictated by the quantity $km/n$. Roughly put, we show that for $km\gg n$ one can achieve a constant maximal load, while for $km\ll n$ no substantial improvement can be gained over the case $k=1$ (i.e., a random allocation). For any $k=\Omega(\log n)$ and $m=\Omega(\log^2n)$, one can achieve a constant load w.h.p. if $km=\Omega(n)$, yet the load is unbounded if $km=o(n)$. Similarly, if $km>Cn$ then $n/2$ balls can be allocated without any collisions w.h.p., whereas for $km<\epsilon n$ there are typically $\Omega(n)$ collisions. Furthermore, we show that the load is w.h.p. at least $\frac{\log(n/m)}{\log k+\log\log(n/m)}$. In particular, for $k\leq\operatorname {polylog}(n)$, if $m=n^{1-\delta}$ the optimal maximal load is $\Theta(\frac{\log n}{\log\log n})$ (the same as in the case $k=1$), while $m=2n$ suffices to ensure a constant load. Finally, we analyze nonadaptive allocation algorithms and give tight upper and lower bounds for their performance.

Affiliated with

Also associated with

No associations

Rating

Choice-memory tradeoff in allocations 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 Choice-memory tradeoff in allocations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Choice-memory tradeoff in allocations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-372530