Strongly History-Independent Storage Allocation: New Upper and Lower Bounds
William Kuszmaul · 2023
A data structure is said to be strongly history independent if its state is fully determined by its current set of elements (and random bits). One of the most basic questions that strongly history-independent algorithms face is storage allocation: given a set S of up to $(1-\epsilon) n+1$ elements, assign them to distinct positions in an array of size n. If we ask that the allocation be strongly history independent, then what is the optimal asymptotic cost of performing an insertion or deletion? On the upper-bound side, Berger et al. (ICALP ’22) showed how to achieve expected cost $O\left(1+\log \epsilon^{-1}\right)$. In this paper, we offer a nearly matching lower bound of $\tilde{\Omega}\left(\log \epsilon^{-1}\right)$. As corollaries, we get nearly tight lower bounds for strongly history-independent hashing (STOC ’01, FOCS ’07, ICALP’ 08) and for the so-called memoryless worker-task assignment problem (SSS ’17, ICALP ’20, ICALP ’22). Next we consider the problem of partitioning an array of size n among many items of different sizes (and whose cumulative sizes are at most $(1-\epsilon) n+1)$. In STOC ’01, Naor and Teague gave a weakly history-independent solution to this problem with logarithmic overhead (and with $\epsilon=1 / 2$); they posed as an open question whether one could hope to do better. We give a new construction that achieves $O(1)$ expected overhead, also for $\epsilon=$ $1 / 2$, and that is strongly history independent. Generalizing to $\epsilon\lt 1 / 2$, our solution achieves expected overhead $O\left(1+\log \epsilon^{-1}\right)$ for insertion/deletions of objects whose sizes are at most $O\left(\epsilon^{4} n\right)$.