Distributed Speed Scaling in Large-Scale Service Systems

• 成果类型: Article; Early Access
• 署名作者: Rutten, Daan; Zubeldia, Martin; Mukherjee, Debankur
• 署名单位: University System of Georgia; Georgia Institute of Technology; University of Minnesota System; University of Minnesota Twin Cities
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2024.1012
• 发表日期: 2025
• 关键词: stochastic-approximation; load distribution; optimization

摘要

We consider a large-scale parallel-server loss system with an unknown arrival rate, where each server is able to adjust its processing speed. The objective is to minimize the system cost, which consists of a power cost to maintain the servers' processing speeds and a quality of service cost depending on the tasks' processing times among others. We draw on ideas from stochastic approximation to design a novel speed-scaling algorithm and prove that the servers' processing speeds converge to the globally asymptotically optimum value. Curiously, the algorithm is fully distributed and does not require any communication between servers. Apart from the algorithm design, a key contribution of our approach lies in demonstrating how concepts from the stochastic approximation literature can be leveraged to effectively tackle learning problems in large-scale distributed systems. En route, we also analyze the performance of a fully heterogeneous parallel-server loss system, where each server has a distinct processing speed, which might be of independent interest.