History-Independent Load Balancing

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 \ge \omega(1)\), and is the first fully dynamic solution (history independent or not) to achieve \(O(1)\) overload with \(o(m/n)\) expected recourse.