Choice-memory tradeoff in allocations

DOI10.1214/09-AAP656MaRDI QIDQ990388zbMATH OpenFDO

Authors Noga Alon, Ori Gurel-Gurevich, Eyal Lubetzky

Publication date 1 September 2010

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0901.4056

zbMATH Keywords

balls and bins paradigmspace/performance tradeoffs

Mathematics Subject Classification ID

Combinatorial probability (60C05) Sums of independent random variables; random walks (60G50) Analysis of algorithms and problem complexity (68Q25)

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 is $Theta(n)$ and the maximum number of balls in a bin is $Theta(fraclognloglogn)$. 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(logn)$. Moreover, it is possible w.h.p. to avoid any collisions between $n/2$ balls if $k>lo{g}_{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 $kmggn$ one can achieve a constant maximal load, while for $kmlln$ no substantial improvement can be gained over the case $k=1$ (i.e., a random allocation). For any $k=Omega(logn)$ and $m=Omega(lo{g}^{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<epsilonn$ there are typically $Omega(n)$ collisions. Furthermore, we show that the load is w.h.p. at least $fraclog(n/m)logk+loglog(n/m)$. In particular, for $kleqoperatornamepolylog(n)$, if $m=n^{1-delta}$ the optimal maximal load is $Theta(fraclognloglogn)$ (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.

Review text

The paper focuses on the balls-and-bins paradigm which describes the process where \(b\) balls are placed independently and uniformly at random in \(n\) bins. The authors study the above models in the presence of constraint on the memory that the online algorithm has at its disposal. They find that a tradeoff between the choice and the memory governs the ability to achieve a perfect allocation as well as a constant maximal load.

Recommendations

• Choice-Memory Tradeoff in Allocations
• Choosing an optimum version of main-memory allocation
• Balanced allocation: memory performance tradeoffs
• Allocate-on-use space complexity of shared-memory algorithms
• Information and memory in dynamic resource allocation
• OPTVersusLOADin Dynamic Storage Allocation
• OPT versus LOAD in dynamic storage allocation

Cites work

• A Best Possible Kolmogoroff-Type Inequality for Martingales and a Characteristic Property
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Balanced Allocations
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• Dimension reduction for hyperbolic space
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• scientific article; zbMATH DE number 4072047 (Why is no real title available?)
• scientific article; zbMATH DE number 3548141 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1857645 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• On tail probabilities for martingales
• Percolation
• Probability and Computing
• The Complexity of Parallel Sorting
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Time-space lower bounds for satisfiability
• Time-space trade-off lower bounds for randomized computation of decision problems
• Time-space tradeoffs for branching programs

Cited in

(8)

• On approximating the stationary distribution of time-reversible Markov chains
• On approximating the stationary distribution of time-reversible Markov chains
• Recency-Abstraction for Heap-Allocated Storage
• Quantifying and evaluating the space overhead for alternative C++ memory layouts
• Balanced allocation: memory performance tradeoffs
• Long-term balanced allocation via thinning
• Balanced allocations with the choice of noise
• Choosing an optimum version of main-memory allocation

This page was built for publication: Choice-memory tradeoff in allocations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990388)