History-Independent Load Balancing

Michael A. Bender, William Kuszmaul, Elaine Shi +1

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…