Achieving optimal backlog in multi-processor cup games

Many problems in processor scheduling, deamortization, and buffer management can be modeled as single- and multi-processor cup games.

Authors

• Michael A. Bender
• Martín Farach-Colton
• William Kuszmaul

Keywords

• deamortization
• processor sharing
• parallelism
• discretized scheduling
• cup emptying
• smoothed analysis