Achieving optimal backlog in multi-processor cup games

DOI10.1145/3313276.3316342MaRDI QIDQ5212854zbMATH OpenOpenAlexFDO

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

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.02861

zbMATH Keywords

parallelismprocessor sharingsmoothed analysisdeamortizationcup emptyingdiscretized scheduling

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Applications of game theory (91A80) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: The single- and multi- processor cup games can be used to model natural problems in areas such as processor scheduling, deamortization, and buffer management. At the beginning of the single-processor cup game, $n$ cups are initially empty. In each step of the game, 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. It is known that the greedy algorithm (i.e., empty the fullest cup) achieves backlog $O(logn)$, and that no deterministic algorithm can do better. We show that the performance of the greedy algorithm can be greatly improved with a small amount of randomization: After any step $i$, and for any $kgeOmega(logepsilo{n}^{-1})$, the emptier achieves backlog at most $O(k)$ with probability at least $1-O(2^{-2^k})$. Whereas bounds for the single-processor cup game have been known for more than fifteen years, proving nontrivial bounds on backlog for the multi-processor extension has remained open. We present a simple analysis of the greedy algorithm for the multi-processor cup game, establishing a backlog of $O(epsilo{n}^{-1}logn)$, as long as $delta$, the game's other speed-augmentation constant, is at least $1/poly(n)$. Turning to randomized algorithms, we encounter an unexpected phenomenon: When the number of processors $p$ is large, the backlog after each step drops to emph{constant} with large probability. Specifically, we show that if $delta$ and $epsilon$ satisfy reasonable constraints, then there exists an algorithm that bounds the backlog after a given step by three or less with probability at least $1-O(exp(-Omega(epsilo{n}^{2}p))$. We further extend the guarantees of our randomized algorithm to consider larger backlogs.

Recommendations

• Achieving Optimal Backlog in the Vanilla Multi-Processor Cup Game
• On the optimization of multitasking process with multiplayer
• Pareto-optimal algorithms for scheduling games on parallel-batching machines with activation cost
• Computing the Price of Anarchy in Processor Load Balancing Game with Linear Delays
• A coordination mechanism for a scheduling game with parallel-batching machines
• scientific article; zbMATH DE number 1929944
• Optimizing Routing and Backlogs for Job Flows in a Distributed Computing Environment
• The winning ways of concurrent games

Cited in

(5)

• The variable-processor cup game
• Perpetual maintenance of machines with different urgency requirements
• The matroid cup game
• Perpetual scheduling with explorable uncertainty
• Cutting bamboo down to size

This page was built for publication: Achieving optimal backlog in multi-processor cup games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212854)