CHOICE-MEMORY TRADEOFF IN ALLOCATIONS

• 成果类型: Article
• 署名作者: Alon, Noga; Gurel-Gurevich, Ori; Lubetzky, Eyal
• 署名单位: Tel Aviv University; Microsoft; MICROSOFT ISRAEL; Microsoft
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/09-AAP656
• 发表日期: 2010
• 页码: 1470-1511
• 关键词: time-space tradeoff; Lower bounds

摘要

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(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(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 km >> n one can achieve a constant maximal load, while for km << 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 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 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 Theta(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.