Document Open Access Logo

The Variable-Processor Cup Game

Authors William Kuszmaul, Alek Westover

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.16.pdf
  • Filesize: 0.52 MB
  • 20 pages

Document Identifiers

Author Details

William Kuszmaul
  • CSAIL, MIT, Cambridge, MA, USA
Alek Westover
  • CSAIL, MIT, Cambridge, MA, USA

Funding

This research was sponsored in part by National Science Foundation Grants XPS-1533644 and CCF-1930579, and in part by the United States Air Force Research Laboratory and was accomplished under Cooperative Agreement Number FA8750-19-2-1000. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the United States Air Force or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
  • Kuszmaul, William: Funded by a Hertz Fellowship and an NSF GRFP fellowship.

Acknowledgements

Portions of this work were completed at the Second Hawaii Workshop on Parallel Algorithms and Data Structures. The authors would like to thank Nodari Sitchinava for organizing the workshop, and John Iacono for several helpful discussions relating to the variable-processor cup game.

Cite AsGet BibTex

William Kuszmaul and Alek Westover. The Variable-Processor Cup Game. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.16

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parallel algorithms
Keywords
  • scheduling
  • cup games
  • online algorithms
  • lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Micah Adler, Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul Goldberg, and Mike Paterson. A proportionate fair scheduling rule with good worst-case performance. In Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 101-108, 2003. URL: https://doi.org/10.1145/777412.777430.
  2. Amihood Amir, Martin Farach, Ramana M. Idury, Johannes A. La Poutré, and Alejandro A. Schäffer. Improved dynamic dictionary matching. Inf. Comput., 119(2):258-282, 1995. URL: https://doi.org/10.1006/inco.1995.1090.
  3. Amihood Amir, Gianni Franceschini, Roberto Grossi, Tsvi Kopelowitz, Moshe Lewenstein, and Noa Lewenstein. Managing unbounded-length keys in comparison-driven data structures with applications to online indexing. SIAM Journal on Computing, 43(4):1396-1416, 2014. Google Scholar
  4. Yossi Azar and Arik Litichevskey. Maximizing throughput in multi-queue switches. Algorithmica, 45(1):69-90, 2006. Google Scholar
  5. Amotz Bar-Noy, Ari Freund, Shimon Landa, and Joseph (Seffi) Naor. Competitive on-line switching policies. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 525-534, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545452.
  6. Amotz Bar-Noy, Aviv Nisgav, and Boaz Patt-Shamir. Nearly optimal perfectly periodic schedules. Distributed Computing, 15(4):207-220, 2002. Google Scholar
  7. S. K. Baruah, N. K. Cohen, C. G. Plaxton, and D. A. Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15(6):600-625, June 1996. URL: https://doi.org/10.1007/BF01940883.
  8. Sanjoy K Baruah, Johannes E Gehrke, and C Greg Plaxton. Fast scheduling of periodic tasks on multiple resources. In Proceedings of the 9th International Parallel Processing Symposium, pages 280-288, 1995. Google Scholar
  9. Michael Bender, Rathish Das, Martín Farach-Colton, Rob Johnson, and William Kuszmaul. Flushing without cascades. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020. Google Scholar
  10. Michael Bender, Martín Farach-Colton, and William Kuszmaul. Achieving optimal backlog in multi-processor cup games. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), 2019. Google Scholar
  11. Michael Bender and William Kuszmaul. Randomized cup game algorithms against strong adversaries. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021. Google Scholar
  12. Michael A Bender, Rezaul A Chowdhury, Rathish Das, Rob Johnson, William Kuszmaul, Andrea Lincoln, Quanquan C Liu, Jayson Lynch, and Helen Xu. Closing the gap between cache-oblivious and cache-adaptive analysis. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pages 63-73, 2020. Google Scholar
  13. Michael A Bender, Rezaul A Chowdhury, Rathish Das, Rob Johnson, William Kuszmaul, Andrea Lincoln, Quanquan C Liu, Jayson Lynch, and Helen Xu. Closing the gap between cache-oblivious and cache-adaptive analysis. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pages 63-73, 2020. Google Scholar
  14. Michael A Bender, Roozbeh Ebrahimi, Jeremy T Fineman, Golnaz Ghasemiesfeh, Rob Johnson, and Samuel McCauley. Cache-adaptive algorithms. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 958-971. SIAM, 2014. Google Scholar
  15. Peter Damaschke and Zhen Zhou. On queuing lengths in on-line switching. Theoretical computer science, 339(2-3):333-343, 2005. Google Scholar
  16. Paul Dietz and Daniel Sleator. Two algorithms for maintaining order in a list. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC), pages 365-372, 1987. URL: https://doi.org/10.1145/28395.28434.
  17. Paul F. Dietz and Rajeev Raman. Persistence, amortization and randomization. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 78-88, 1991. URL: http://dl.acm.org/citation.cfm?id=127787.127809.
  18. Johannes Fischer and Paweł Gawrychowski. Alphabet-dependent string searching with wexponential search trees. In Annual Symposium on Combinatorial Pattern Matching (CPM), pages 160-171, 2015. Google Scholar
  19. Rudolf Fleischer and Hisashi Koga. Balanced scheduling toward loss-free packet queuing and delay fairness. Algorithmica, 38(2):363-376, February 2004. URL: https://doi.org/10.1007/s00453-003-1064-z.
  20. H Richard Gail, G Grover, Roch Guérin, Sidney L Hantler, Zvi Rosberg, and Moshe Sidi. Buffer size requirements under longest queue first. Performance Evaluation, 18(2):133-140, 1993. Google Scholar
  21. Leszek Gasieniec, Ralf Klasing, Christos Levcopoulos, Andrzej Lingas, Jie Min, and Tomasz Radzik. Bamboo garden trimming problem (perpetual maintenance of machines with different attendance urgency factors). In International Conference on Current Trends in Theory and Practice of Informatics, pages 229-240. Springer, 2017. Google Scholar
  22. Michael H. Goldwasser. A survey of buffer management policies for packet switches. SIGACT News, 41(1):100-128, 2010. URL: https://doi.org/10.1145/1753171.1753195.
  23. Michael T Goodrich and Paweł Pszona. Streamed graph drawing and the file maintenance problem. In International Symposium on Graph Drawing, pages 256-267. Springer, 2013. Google Scholar
  24. Nan Guan and Wang Yi. Fixed-priority multiprocessor scheduling: Critical instant, response time and utilization bound. In 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum, pages 2470-2473. IEEE, 2012. Google Scholar
  25. Tsvi Kopelowitz. On-line indexing for general alphabets via predecessor queries on subsets of an ordered list. In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 283-292, 2012. Google Scholar
  26. William Kuszmaul. Achieving optimal backlog in the vanilla multi-processor cup game. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020. Google Scholar
  27. Andrea Lincoln, Quanquan C Liu, Jayson Lynch, and Helen Xu. Cache-adaptive exploration: Experimental results and scan-hiding for adaptivity. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, pages 213-222, 2018. Google Scholar
  28. Ami Litman and Shiri Moran-Schein. On distributed smooth scheduling. In Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 76-85, 2005. Google Scholar
  29. Ami Litman and Shiri Moran-Schein. Smooth scheduling under variable rates or the analog-digital confinement game. Theor. Comp. Sys., 45(2):325-354, June 2009. URL: https://doi.org/10.1007/s00224-008-9134-x.
  30. Ami Litman and Shiri Moran-Schein. On centralized smooth scheduling. Algorithmica, 60(2):464-480, 2011. Google Scholar
  31. Chung Laung Liu. Scheduling algorithms for multiprocessors in a hard real-time environment. JPL Space Programs Summary, 1969, 1969. Google Scholar
  32. Chung Laung Liu and James W Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM (JACM), 20(1):46-61, 1973. Google Scholar
  33. Richard T Mills, Andreas Stathopoulos, and Dimitrios S Nikolopoulos. Adapting to memory pressure from within scientific applications on multiprogrammed cows. In Proc. 8th International Parallel and Distributed Processing Symposium (IPDPS), page 71, 2004. Google Scholar
  34. Mark Moir and Srikanth Ramamurthy. Pfair scheduling of fixed and migrating periodic tasks on multiple resources. In Proceedings of the 20th IEEE Real-Time Systems Symposium, pages 294-303, 1999. Google Scholar
  35. Christian Worm Mortensen. Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 618-627, 2003. Google Scholar
  36. Michael Rosenblum, Michel X Goemans, and Vahid Tarokh. Universal bounds on buffer size for packetizing fluid policies in input queued, crossbar switches. In Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), volume 2, pages 1126-1134, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact