| Choice-memory tradeoff in allocations (2009) | |||||||||
Abstract | |||||||||
| 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 has order n and the maximum number of balls in a bin has order (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 is at least of order (log n). Moreover, it is possible whp to avoid any collisions between (n/2) balls if (k> log_2 n). 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 (k m) larger than n, one can achieve a constant maximal load, while for (k m) smaller than 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^2 n)), one can achieve a constant load whp if (k m = \Omega(n)), yet the load is unbounded if (k m =o(n)). Similarly, if (k m > C n) then (n/2) balls can be allocated without any collisions whp, whereas for (k m < \epsilon n) there are typically order n collisions. Furthermore, we show that the load is whp at least log(n/m)/[log k + log log(n/m)]. In particular, for k=polylog(n), if m = n^{1-\delta} the optimal maximal load is of order (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 non-adaptive allocation algorithms and give tight upper and lower bounds for their performance.. Comment: 41 pages | |||||||||
Publication details | |||||||||
| |||||||||