Cup Emptying Games and I/O Scheduling

Cup-emptying games model problems throughout computer science, in areas ranging from processor scheduling, to deamortization, to buffer management. In a basic cup game, n cups are initially empty. In each step, a filler distributes 1 unit of water among the cups, and then an emptier selects a cup and removes (1+epsilon) units from that cup. The goal of the emptier is to minimize the amount of water in the fullest cup, also known as the backlog.  The greedy algorithm (i.e., empty the fullest cup) achieves backlog O(log n), and no deterministic algorithm can do better.

In this talk we first show that a small amount of randomization in a cup game leads to an exponentially smaller backlog.   We analyze parallel cup games, in which the emptier removes water from more than one cups in each step.  The parallel cup game has resisted analysis for two decades.

Finally, we describe a buffer-management problem that is faced by high-performance databases, file systems, and key-value stores. We show how cup game analyses offer a solution.

Joint work with Rathish Das, Martin Farach-Colton, Rob Johnson, and William Kuszmaul.

Michael A. Bender is the David R. Smith Leading Scholar of Computer Science at Stony Brook University.  His research interests span the areas of data structures and algorithms, I/O-efficient computing, parallel computing, and scheduling.  He has coauthored over 140 articles on these and other topics.  He has won several awards, including an R&D 100 Award, a Test-of-Time award, two Best Paper Awards, and five awards for graduate and undergraduate teaching.

Bender was Founder and Chief Scientist at Tokutek, Inc, an enterprise database company, which was acquired by Percona in 2015.  He has held Visiting Scientist positions at both MIT and King’s College London.

Bender received his B.A. in Applied Mathematics from Harvard University in 1992 and obtained a D.E.A. in Computer Science from the Ecole Normale Superieure de Lyon, France in 1993. He completed a Ph.D. on Scheduling Algorithms from Harvard University in 1998.