Lune

SODA2026Top-tier venue

History-Independent Load Balancing

Michael A. Bender, William Kuszmaul, Elaine Shi, Rose Silver

Abstract

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 mm balls, while guaranteeing a maximum load of m/n+O(1)m/n + O(1) with high probability, and achieving an expected recourse of O(log⁡log⁡(m/n))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≥ω(1)m/n \ge \omega(1), and is the first fully dynamic solution (history independent or not) to achieve O(1)O(1) overload with o(m/n)o(m/n) expected recourse.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Strongly History-Independent Storage Allocation: New Upper and Lower Bounds cites Balanced Allocations: The Heavily Loaded Case with Deletions
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on2

  1. Strongly History-Independent Storage Allocation: New Upper and Lower BoundsWilliam KuszmaulFOCS 2023 · 7 citations
  2. Balanced Allocations: The Heavily Loaded Case with DeletionsNikhil Bansal, William KuszmaulFOCS 2022 · 6 citations

Related papers

  1. Balls and Bins and the Infinite Process with Random DeletionsPetra Berenbrink, Tom Friedetzky, Peter Kling, Lars NagelSODA 2026
  2. Load balancing with dynamic set of balls and binsAnders Aamand, Jakob Bæk Tejs Knudsen, Mikkel ThorupSTOC 2021 · 4 citations
  3. Linear Hashing Is OptimalMichael Jaber, Vinayak M. Kumar, David ZuckermanSTOC 2025 · 1 citation
  4. Balanced Allocations with Heterogeneous Bins: The Power of MemoryDimitrios Los, Thomas Sauerwald, John SylvesterSODA 2023 · 5 citations
  5. The power of two choices in graphical allocationNikhil Bansal, Ohad N. FeldheimSTOC 2022 · 5 citations
Dusk over the sea between two cliffs drawn in fine vertical lines