License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.16
URN: urn:nbn:de:0030-drops-135559
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13555/
Go to the corresponding LIPIcs Volume Portal

Kuszmaul, William ; Westover, Alek

The Variable-Processor Cup Game

pdf-format:
LIPIcs-ITCS-2021-16.pdf (0.5 MB)

Abstract

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 cups, there are two players, a filler and an emptier, that take turns adding and removing water from a set of n cups. In each turn, the filler adds p units of water to the cups, placing at most 1 unit of water in each cup, and then the emptier selects p cups to remove up to 1 unit of water from. The emptier’s goal is to minimize the backlog, which is the height of the fullest cup.
The p-processor cup game has been studied in many different settings, dating back to the late 1960’s. All of the past work shares one common assumption: that p is fixed. This paper initiates the study of what happens when the number of available processors p varies over time, resulting in what we call the variable-processor cup game.
Remarkably, the optimal bounds for the variable-processor cup game differ dramatically from its classical counterpart. Whereas the p-processor cup has optimal backlog Θ(log n), the variable-processor game has optimal backlog Θ(n). Moreover, there is an efficient filling strategy that yields backlog Ω(n^{1 - ε}) in quasi-polynomial time against any deterministic emptying strategy.
We additionally show that straightforward uses of randomization cannot be used to help the emptier. In particular, for any positive constant Δ, and any Δ-greedy-like randomized emptying algorithm ?, there is a filling strategy that achieves backlog Ω(n^{1 - ε}) against ? in quasi-polynomial time.

BibTeX - Entry

@InProceedings{kuszmaul_et_al:LIPIcs.ITCS.2021.16,
  author =	{William Kuszmaul and Alek Westover},
  title =	{{The Variable-Processor Cup Game}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{James R. Lee},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13555},
  URN =		{urn:nbn:de:0030-drops-135559},
  doi =		{10.4230/LIPIcs.ITCS.2021.16},
  annote =	{Keywords: scheduling, cup games, online algorithms, lower bounds}
}

Keywords: scheduling, cup games, online algorithms, lower bounds
Collection: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Issue Date: 2021
Date of publication: 04.02.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI