Balanced allocations: The heavily loaded case with deletions
N Bansal, W Kuszmaul - 2022 IEEE 63rd Annual Symposium …, 2022 - ieeexplore.ieee.org
In the 2-choice allocation problem, m balls are placed into n bins, and each ball must
choose between two random bins i,j∈n that it has been assigned to. It has been known for …
choose between two random bins i,j∈n that it has been assigned to. It has been known for …
Randomized cup game algorithms against strong adversaries
MA Bender, W Kuszmaul - Proceedings of the 2021 ACM-SIAM Symposium on …, 2021 - SIAM
In each step of the cup game on n cups, a filler distributes up to 1–∊ water among the cups,
and then an emptier removes 1 unit of water from a single cup. The emptier's goal is to …
and then an emptier removes 1 unit of water from a single cup. The emptier's goal is to …
How asymmetry helps buffer management: achieving optimal tail size in cup games
W Kuszmaul - Proceedings of the 53rd Annual ACM SIGACT …, 2021 - dl.acm.org
The cup game on n cups is a multi-step game with two players, a filler and an emptier. At
each step, the filler distributes 1 unit of water among the cups, and then the emptier selects a …
each step, the filler distributes 1 unit of water among the cups, and then the emptier selects a …
Root-to-Leaf Scheduling in Write-Optimized Trees
Write-optimized dictionaries are a class of cache-efficient data structures that buffer updates
and apply them in batches to optimize the amortized cache misses per update. For example …
and apply them in batches to optimize the amortized cache misses per update. For example …
Bamboo trimming revisited: Simple algorithms can do well too
J Kuszmaul - Proceedings of the 34th ACM Symposium on …, 2022 - dl.acm.org
The bamboo trimming problem considers n bamboo with growth rates h1, 2,..., satisfying
Σihi= 1. During a given unit of time, each bamboo grows by hi, and then the bamboo …
Σihi= 1. During a given unit of time, each bamboo grows by hi, and then the bamboo …
External-memory Dictionaries in the Affine and PDAM Models
Storage devices have complex performance profiles, including costs to initiate IOs (eg, seek
times in hard drives), parallelism and bank conflicts (in SSDs), costs to transfer data, and …
times in hard drives), parallelism and bank conflicts (in SSDs), costs to transfer data, and …
The variable-processor cup game
W Kuszmaul, A Westover - arXiv preprint arXiv:2012.00127, 2020 - arxiv.org
The problem of scheduling tasks on $ p $ processors so that no task ever gets too far behind
is often described as a game with cups and water. In the $ p $-processor cup game on $ n …
is often described as a game with cups and water. In the $ p $-processor cup game on $ n …
Cutting bamboo down to size
This paper studies the problem of programming a robotic panda gardener to keep a bamboo
garden from obstructing the view of the lake by your house. The garden consists of n …
garden from obstructing the view of the lake by your house. The garden consists of n …
Brief Announcement: Root-to-Leaf Scheduling in Write-Optimized Trees
C Chung, W Jannen, S McCauley… - Proceedings of the 36th …, 2024 - dl.acm.org
In a large, parallel dictionary, performance is dominated by the cache efficiency of its
database operations, analyzed theoretically in the DAM model. Write-optimized dictionaries …
database operations, analyzed theoretically in the DAM model. Write-optimized dictionaries …
External-memory dictionaries with worst-case update cost
The $ B^{\epsilon} $-tree [Brodal and Fagerberg 2003] is a simple I/O-efficient external-
memory-model data structure that supports updates orders of magnitude faster than B-tree …
memory-model data structure that supports updates orders of magnitude faster than B-tree …