Achieving optimal backlog in multi-processor cup games

Michael A. Bender, Martin Farach-Colton, William Kuszmaul

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

Many problems in processor scheduling, deamortization, and buffer management can be modeled as single- and multi-processor cup games. At the beginning of the single-processor n-cup game, all cups are empty. In each step of the game, a filler distributes 1 − ε units of water among the cups, and then an emptier selects a cup and removes up to 1 unit of water from it. 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 from the fullest cup) is known to achieve backlog O(log n), and no deterministic algorithm can do better. We show that the performance of the greedy algorithm can be exponentially improved with a small amount of randomization: After each step and for any k ≥ Ω(log ε−1), the emptier achieves backlog at most O(k) with probability at least 1 − O(2−2k ). We call our algorithm the smoothed greedy algorithm because if follows from a smoothed analysis of the (standard) greedy algorithm. In each step of the p-processor n-cup game, the filler distributes p(1 − ε) unit of water among the cups, with no cup receiving more than 1 − δ units of water, and then the emptier selects p cups and removes 1 unit of water from each. Proving nontrivial bounds on the backlog for the multi-processor cup game has remained open for decades. We present a simple analysis of the greedy algorithm for the multi-processor cup game, establishing a backlog of O(ε−1 log n), as long as δ > 1/poly(n). Turning to randomized algorithms, we find that the backlog drops to constant. Specifically, we show that if ε and δ satisfy reasonable constraints, then there exists an algorithm that bounds the backlog after a given step by 3 with probability at least 1 − O(exp(−Ω(ε2p)). We prove that our results are asymptotically optimal for constant ε, in the sense that no algorithms can achieve better bounds, up to constant factors in the backlog and in p. Moreover, we prove robustness results, demonstrating that our randomized algorithms continue to behave well even when placed in bad starting states.

Original languageEnglish (US)
Title of host publicationSTOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
EditorsMoses Charikar, Edith Cohen
PublisherAssociation for Computing Machinery
Pages1148-1157
Number of pages10
ISBN (Electronic)9781450367059
DOIs
StatePublished - Jun 23 2019
Event51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, United States
Duration: Jun 23 2019Jun 26 2019

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
CountryUnited States
CityPhoenix
Period6/23/196/26/19

Fingerprint

Water
Fillers
Scheduling

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Cup emptying
  • Deamortization
  • Discretized scheduling
  • Parallelism
  • Processor sharing
  • Smoothed analysis

Cite this

Bender, M. A., Farach-Colton, M., & Kuszmaul, W. (2019). Achieving optimal backlog in multi-processor cup games. In M. Charikar, & E. Cohen (Eds.), STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (pp. 1148-1157). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3313276.3316342
Bender, Michael A. ; Farach-Colton, Martin ; Kuszmaul, William. / Achieving optimal backlog in multi-processor cup games. STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. editor / Moses Charikar ; Edith Cohen. Association for Computing Machinery, 2019. pp. 1148-1157 (Proceedings of the Annual ACM Symposium on Theory of Computing).
@inproceedings{138fce3b11df4a90887c32dce581ce39,
title = "Achieving optimal backlog in multi-processor cup games",
abstract = "Many problems in processor scheduling, deamortization, and buffer management can be modeled as single- and multi-processor cup games. At the beginning of the single-processor n-cup game, all cups are empty. In each step of the game, a filler distributes 1 − ε units of water among the cups, and then an emptier selects a cup and removes up to 1 unit of water from it. 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 from the fullest cup) is known to achieve backlog O(log n), and no deterministic algorithm can do better. We show that the performance of the greedy algorithm can be exponentially improved with a small amount of randomization: After each step and for any k ≥ Ω(log ε−1), the emptier achieves backlog at most O(k) with probability at least 1 − O(2−2k ). We call our algorithm the smoothed greedy algorithm because if follows from a smoothed analysis of the (standard) greedy algorithm. In each step of the p-processor n-cup game, the filler distributes p(1 − ε) unit of water among the cups, with no cup receiving more than 1 − δ units of water, and then the emptier selects p cups and removes 1 unit of water from each. Proving nontrivial bounds on the backlog for the multi-processor cup game has remained open for decades. We present a simple analysis of the greedy algorithm for the multi-processor cup game, establishing a backlog of O(ε−1 log n), as long as δ > 1/poly(n). Turning to randomized algorithms, we find that the backlog drops to constant. Specifically, we show that if ε and δ satisfy reasonable constraints, then there exists an algorithm that bounds the backlog after a given step by 3 with probability at least 1 − O(exp(−Ω(ε2p)). We prove that our results are asymptotically optimal for constant ε, in the sense that no algorithms can achieve better bounds, up to constant factors in the backlog and in p. Moreover, we prove robustness results, demonstrating that our randomized algorithms continue to behave well even when placed in bad starting states.",
keywords = "Cup emptying, Deamortization, Discretized scheduling, Parallelism, Processor sharing, Smoothed analysis",
author = "Bender, {Michael A.} and Martin Farach-Colton and William Kuszmaul",
year = "2019",
month = "6",
day = "23",
doi = "10.1145/3313276.3316342",
language = "English (US)",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",
pages = "1148--1157",
editor = "Moses Charikar and Edith Cohen",
booktitle = "STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing",

}

Bender, MA, Farach-Colton, M & Kuszmaul, W 2019, Achieving optimal backlog in multi-processor cup games. in M Charikar & E Cohen (eds), STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 1148-1157, 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, United States, 6/23/19. https://doi.org/10.1145/3313276.3316342

Achieving optimal backlog in multi-processor cup games. / Bender, Michael A.; Farach-Colton, Martin; Kuszmaul, William.

STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. ed. / Moses Charikar; Edith Cohen. Association for Computing Machinery, 2019. p. 1148-1157 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Achieving optimal backlog in multi-processor cup games

AU - Bender, Michael A.

AU - Farach-Colton, Martin

AU - Kuszmaul, William

PY - 2019/6/23

Y1 - 2019/6/23

N2 - Many problems in processor scheduling, deamortization, and buffer management can be modeled as single- and multi-processor cup games. At the beginning of the single-processor n-cup game, all cups are empty. In each step of the game, a filler distributes 1 − ε units of water among the cups, and then an emptier selects a cup and removes up to 1 unit of water from it. 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 from the fullest cup) is known to achieve backlog O(log n), and no deterministic algorithm can do better. We show that the performance of the greedy algorithm can be exponentially improved with a small amount of randomization: After each step and for any k ≥ Ω(log ε−1), the emptier achieves backlog at most O(k) with probability at least 1 − O(2−2k ). We call our algorithm the smoothed greedy algorithm because if follows from a smoothed analysis of the (standard) greedy algorithm. In each step of the p-processor n-cup game, the filler distributes p(1 − ε) unit of water among the cups, with no cup receiving more than 1 − δ units of water, and then the emptier selects p cups and removes 1 unit of water from each. Proving nontrivial bounds on the backlog for the multi-processor cup game has remained open for decades. We present a simple analysis of the greedy algorithm for the multi-processor cup game, establishing a backlog of O(ε−1 log n), as long as δ > 1/poly(n). Turning to randomized algorithms, we find that the backlog drops to constant. Specifically, we show that if ε and δ satisfy reasonable constraints, then there exists an algorithm that bounds the backlog after a given step by 3 with probability at least 1 − O(exp(−Ω(ε2p)). We prove that our results are asymptotically optimal for constant ε, in the sense that no algorithms can achieve better bounds, up to constant factors in the backlog and in p. Moreover, we prove robustness results, demonstrating that our randomized algorithms continue to behave well even when placed in bad starting states.

AB - Many problems in processor scheduling, deamortization, and buffer management can be modeled as single- and multi-processor cup games. At the beginning of the single-processor n-cup game, all cups are empty. In each step of the game, a filler distributes 1 − ε units of water among the cups, and then an emptier selects a cup and removes up to 1 unit of water from it. 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 from the fullest cup) is known to achieve backlog O(log n), and no deterministic algorithm can do better. We show that the performance of the greedy algorithm can be exponentially improved with a small amount of randomization: After each step and for any k ≥ Ω(log ε−1), the emptier achieves backlog at most O(k) with probability at least 1 − O(2−2k ). We call our algorithm the smoothed greedy algorithm because if follows from a smoothed analysis of the (standard) greedy algorithm. In each step of the p-processor n-cup game, the filler distributes p(1 − ε) unit of water among the cups, with no cup receiving more than 1 − δ units of water, and then the emptier selects p cups and removes 1 unit of water from each. Proving nontrivial bounds on the backlog for the multi-processor cup game has remained open for decades. We present a simple analysis of the greedy algorithm for the multi-processor cup game, establishing a backlog of O(ε−1 log n), as long as δ > 1/poly(n). Turning to randomized algorithms, we find that the backlog drops to constant. Specifically, we show that if ε and δ satisfy reasonable constraints, then there exists an algorithm that bounds the backlog after a given step by 3 with probability at least 1 − O(exp(−Ω(ε2p)). We prove that our results are asymptotically optimal for constant ε, in the sense that no algorithms can achieve better bounds, up to constant factors in the backlog and in p. Moreover, we prove robustness results, demonstrating that our randomized algorithms continue to behave well even when placed in bad starting states.

KW - Cup emptying

KW - Deamortization

KW - Discretized scheduling

KW - Parallelism

KW - Processor sharing

KW - Smoothed analysis

UR - http://www.scopus.com/inward/record.url?scp=85068662651&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068662651&partnerID=8YFLogxK

U2 - 10.1145/3313276.3316342

DO - 10.1145/3313276.3316342

M3 - Conference contribution

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1148

EP - 1157

BT - STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

A2 - Charikar, Moses

A2 - Cohen, Edith

PB - Association for Computing Machinery

ER -

Bender MA, Farach-Colton M, Kuszmaul W. Achieving optimal backlog in multi-processor cup games. In Charikar M, Cohen E, editors, STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2019. p. 1148-1157. (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/3313276.3316342