The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting
The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting
复制标题
在线暂停和恢复问题：最优算法和碳感知负载转移的应用
DOI：
10.1145/3626776
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Shenoy, Prashant
中科院分区：
文献类型：
--
作者：
Lechowicz, Adam;Christianson, Nicolas;Zuo, Jinhang;Bashir, Noman;Hajiesmaili, Mohammad;Wierman, Adam;Shenoy, Prashant
介绍并研究了在线暂停和恢复问题。在这个问题中，玩家试图在一个固定长度T的序列中找到k个最低（或者最高）的价格，该序列按顺序显示。在每一个时间步，参与者都有一个价格，并决定是否接受或拒绝它。每当他们的决定在连续的时间步发生变化时，参与者就会产生转换成本，即，每当他们暂停或恢复购买。这个在线问题的动机是碳感知负载转移的目标，其中工作负载可以在高碳强度期间暂停，并在低碳强度期间恢复，并且在保存或恢复其状态时产生成本。它与在线优化文献中研究的现有问题有很强的联系，尽管它引入了独特的技术挑战，阻止了现有算法的直接应用。扩展以前的工作基于阈值的算法，我们引入了双阈值算法的最小化和最大化的变种这个问题。我们进一步表明，这些算法实现的竞争比是最好的任何确定性在线算法实现。最后，我们实证验证我们提出的算法，通过案例研究碳意识负荷转移的应用，使用真实的碳跟踪数据和现有的基线算法。
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.
登录
查看更多内容
涉及兰伯特 W 函数的某些不等式
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
S. Stewart
通讯作者：
S. Stewart
对冲您的赌注：通过混合虚拟机购买选项来优化长期云成本
DOI：
10.1109/ic2e48712.2020.00018
发表时间：
2020
期刊：
2020 IEEE International Conference on Cloud Engineering (IC2E
影响因子：
--
作者：
Ambati, Pradeep;Bashir, Noman;Irwin, David;Hajiesmaili, Mohammad;Shenoy, Prashant
通讯作者：
Shenoy, Prashant
DOI：
10.1145/3428336
发表时间：
2020-10
期刊：
Proceedings of the ACM on Measurement and Analysis of Computing Systems
影响因子：
--
作者：
Bo Sun;Ali Zeynali;Tongxin Li;M. Hajiesmaili;A. Wierman;D. Tsang
通讯作者：
Bo Sun;Ali Zeynali;Tongxin Li;M. Hajiesmaili;A. Wierman;D. Tsang
DOI：
--
发表时间：
2011
期刊：
Global Communications Conference
影响因子：
--
作者：
Zexi Yang;Meng;Z. Niu;Dawei Huang
通讯作者：
Dawei Huang
随机?服务器猜想是错误的！
DOI：
--
发表时间：
2022
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Sébastien Bubeck;Christian Coester;Y. Rabani
通讯作者：
Y. Rabani