History-Independent Load Balancing

We give a (strongly) history-independent two-choice balls-and-bins algorithm on $n$ bins that supports both insertions and deletions on a set of up to $m$ balls, while guaranteeing a maximum load of $m\mathrm{/}n+O(1)$ with high probability, and achieving an expected recourse of $O(\log \log (m\mathrm{/}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\mathrm{/}n\ge \omega (1)$ and is the first fully dynamic solution (history independent or not) to achieve $O(1)$ overload with $o(m\mathrm{/}n)$ expected recourse.