TY - GEN
T1 - Balanced allocation on dynamic hypergraphs
AU - Greenhill, Catherine
AU - Mans, Bernard
AU - Pourmiri, Ali
N1 - Copyright the Author(s) 2020. Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.
PY - 2020/8
Y1 - 2020/8
N2 - The balls-into-bins model randomly allocates n sequential balls into n bins, as follows: each ball selects a set D of d ≥ 2 bins, independently and uniformly at random, then the ball is allocated to a least-loaded bin from D (ties broken randomly). The maximum load is the maximum number of balls in any bin. In 1999, Azar et al. showed that, provided ties are broken randomly, after n balls have been placed the maximum load, is logd log n + O(1), with high probability. We consider this popular paradigm in a dynamic environment where the bins are structured as a dynamic hypergraph. A dynamic hypergraph is a sequence of hypergraphs, say H(t), arriving over discrete times t = 1, 2,..., such that the vertex set of H(t)'s is the set of n bins, but (hyper)edges may change over time. In our model, the t-th ball chooses an edge from H(t) uniformly at random, and then chooses a set D of d ≥ 2 random bins from the selected edge. The ball is allocated to a least-loaded bin from D, with ties broken randomly. We quantify the dynamicity of the model by introducing the notion of pair visibility, which measures the number of rounds in which a pair of bins appears within a (hyper)edge. We prove that if, for some ε > 0, a dynamic hypergraph has pair visibility at most n1−ε, and some mild additional conditions hold, then with high probability the process has maximum load O(logd log n). Our proof is based on a variation of the witness tree technique, which is of independent interest. The model can also be seen as an adversarial model where an adversary decides the structure of the possible sets of d bins available to each ball.
AB - The balls-into-bins model randomly allocates n sequential balls into n bins, as follows: each ball selects a set D of d ≥ 2 bins, independently and uniformly at random, then the ball is allocated to a least-loaded bin from D (ties broken randomly). The maximum load is the maximum number of balls in any bin. In 1999, Azar et al. showed that, provided ties are broken randomly, after n balls have been placed the maximum load, is logd log n + O(1), with high probability. We consider this popular paradigm in a dynamic environment where the bins are structured as a dynamic hypergraph. A dynamic hypergraph is a sequence of hypergraphs, say H(t), arriving over discrete times t = 1, 2,..., such that the vertex set of H(t)'s is the set of n bins, but (hyper)edges may change over time. In our model, the t-th ball chooses an edge from H(t) uniformly at random, and then chooses a set D of d ≥ 2 random bins from the selected edge. The ball is allocated to a least-loaded bin from D, with ties broken randomly. We quantify the dynamicity of the model by introducing the notion of pair visibility, which measures the number of rounds in which a pair of bins appears within a (hyper)edge. We prove that if, for some ε > 0, a dynamic hypergraph has pair visibility at most n1−ε, and some mild additional conditions hold, then with high probability the process has maximum load O(logd log n). Our proof is based on a variation of the witness tree technique, which is of independent interest. The model can also be seen as an adversarial model where an adversary decides the structure of the possible sets of d bins available to each ball.
KW - Balanced allocation
KW - Balls-into-bins
KW - Power of two choices
KW - Witness tree technique
UR - http://www.scopus.com/inward/record.url?scp=85091295400&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX/RANDOM.2020.11
DO - 10.4230/LIPIcs.APPROX/RANDOM.2020.11
M3 - Conference proceeding contribution
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
A2 - Byrka, Jarosław
A2 - Meka, Raghu
PB - Dagstuhl Publishing
CY - Saarbrücken, Germany
ER -