History-Independent Load Balancing
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918334437523456 |
|---|---|
| author | Bender, Michael A. Kuszmaul, William Shi, Elaine Silver, Rose |
| author_facet | Bender, Michael A. Kuszmaul, William Shi, Elaine Silver, Rose |
| contents | 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 / 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 ω(1)$ and is the first fully dynamic solution (history independent or not) to achieve $O(1)$ overload with $o(m/n)$ expected recourse. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_11953 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | History-Independent Load Balancing Bender, Michael A. Kuszmaul, William Shi, Elaine Silver, Rose Data Structures and Algorithms 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 / 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 ω(1)$ and is the first fully dynamic solution (history independent or not) to achieve $O(1)$ overload with $o(m/n)$ expected recourse. |
| title | History-Independent Load Balancing |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.11953 |