TY - GEN
T1 - History-Independent Load Balancing
AU - Bender, Michael A.
AU - Kuszmaul, William
AU - Shi, Elaine
AU - Silver, Rose
N1 - Publisher Copyright:
© 2026 Association for Computing Machinery. All rights reserved.
PY - 2026
Y1 - 2026
N2 - We show that there exists a (strongly) history-independent two-choice balls-and-bins algorithm that supports both insertions and deletions on a set of up to m balls, while guaranteeing a maximum load of m/n+O(1) with high probability, and achieving an expected recourse of O(log log(m/n)) per operation. To the best of our knowledge, this is the first history-independent solution to achieve nontrivial guarantees of any sort for m/n ≥ ω(1), and is the first fully dynamic solution (history independent or not) to achieve O(1) overload with o(m/n) expected recourse.
AB - We show that there exists a (strongly) history-independent two-choice balls-and-bins algorithm that supports both insertions and deletions on a set of up to m balls, while guaranteeing a maximum load of m/n+O(1) with high probability, and achieving an expected recourse of O(log log(m/n)) per operation. To the best of our knowledge, this is the first history-independent solution to achieve nontrivial guarantees of any sort for m/n ≥ ω(1), and is the first fully dynamic solution (history independent or not) to achieve O(1) overload with o(m/n) expected recourse.
UR - https://www.scopus.com/pages/publications/105033624280
U2 - 10.1137/1.9781611978971.44
DO - 10.1137/1.9781611978971.44
M3 - Conference contribution
AN - SCOPUS:105033624280
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1097
EP - 1127
BT - Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026
A2 - Larsen, Kasper Green
A2 - Saha, Barna
PB - Association for Computing Machinery
T2 - 37th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026
Y2 - 11 January 2026 through 14 January 2026
ER -