EUVIMEDEUVIMED entdecken
Crossref

The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting

Adam Lechowicz, Nicolas Christianson, Jinhang Zuo, Noman Bashir, Mohammad Hajiesmaili, Adam Wierman, Prashant Shenoy

Proceedings of the ACM on Measurement and Analysis of Computing Systems · 07.12.2023 · 7 (3) · 1-32

DOI: 10.1145/3626776 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Measurement and Analysis of Computing Systems, online erschienen am 12.12.2023. Verfasst von Adam Lechowicz und 6 weiteren Autor:innen. Die Arbeit wurde bisher 23-mal zitiert (Crossref) und nennt 54 Literaturangaben. Gefördert von: National Science Foundation, U.S. Department of Energy.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We introduce and study the online pause and resume problem. In this problem, a player attempts to find the k lowest (alternatively, highest) prices in a sequence of fixed length T, which is revealed sequentially. At each time step, the player is presented with a price and decides whether to accept or reject it. The player incurs aswitching cost whenever their decision changes in consecutive time steps, i.e., whenever they pause or resume purchasing. This online problem is motivated by the goal of carbon-aware load shifting, where a workload may be paused during periods of high carbon intensity and resumed during periods of low carbon intensity and incurs a cost when saving or restoring its state. It has strong connections to existing problems studied in the literature on online optimization, though it introduces unique technical challenges that prevent the direct application of existing algorithms. Extending prior work on threshold-based algorithms, we introducedouble-threshold algorithms for both the minimization and maximization variants of this problem. We further show that the competitive ratios achieved by these algorithms are the best achievable by any deterministic online algorithm. Finally, we empirically validate our proposed algorithm through case studies on the application of carbon-aware load shifting using real carbon trace data and existing baseline algorithms.

Förderung

  • National Science Foundation
  • U.S. Department of Energy

Zitieren

APA

Lechowicz, A., Christianson, N., Zuo, J., Bashir, N., Hajiesmaili, M., Wierman, A., & Shenoy, P. (2023). The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(3), 1-32. https://doi.org/10.1145/3626776

Vancouver

Lechowicz A, Christianson N, Zuo J, Bashir N, Hajiesmaili M, Wierman A, et al. The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 2023;7(3):1-32. doi:10.1145/3626776

BibTeX
@article{Lechowicz2023,
  author = {Lechowicz, Adam and Christianson, Nicolas and Zuo, Jinhang and Bashir, Noman and Hajiesmaili, Mohammad and Wierman, Adam and Shenoy, Prashant},
  title = {The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting},
  journal = {Proceedings of the ACM on Measurement and Analysis of Computing Systems},
  year = {2023},
  volume = {7},
  number = {3},
  pages = {1--32},
  doi = {10.1145/3626776}
}
Kostenlos starten →