2023/06/03 by Rutten, Daan, Zubeldia, Martin, Mukherjee, Debankur
#68M20 (Primary) 68Q25 #68W15 (Secondary) #C.2.4 #C.4 #FOS: Mathematics #G.1.6 #Optimization and Control (math.OC) #Probability (math.PR)
paper · doi:10.48550/arxiv.2306.02215
We consider a large-scale parallel-server system, where each server independently adjusts its processing speed in a decentralized manner. The objective is to minimize the overall cost, which comprises the average cost of maintaining the servers' processing speeds and a non-decreasing function of the tasks' sojourn times. The problem is compounded by the lack of knowledge of the task arrival rate and the absence of a centralized control or communication among the servers. We draw on ideas from stochastic approximation and present a novel rate scaling algorithm that ensures convergence of all server processing speeds to the globally asymptotically optimum value as the system size increases. 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 system, where each server has a distinct processing speed, which might be of independent interest.