Michael Bender

History-Independent Load Balancing

2026 · Society for Industrial and Applied Mathematics eBooks

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 …