Paper Info
Title
Multiple Server SRPT With Speed Scaling Is Competitive
Abstract
Can the popular shortest remaining processing time (SRPT) algorithm achieve a constant competitive ratio on multiple servers when server speeds are adjustable (speed scaling) with respect to the flow time plus energy consumption metric? This question has remained open for a while, where a negative result in the absence of speed scaling is well known. The main result of this paper is to show that multi-server SRPT with speed scaling can be constant competitive, with a competitive ratio that only depends on the power-usage function of the servers, but not on the number of jobs/servers or the job sizes (unlike when speed scaling is not allowed). When all job sizes are unity, we show that round-robin routing is optimal and can achieve the same competitive ratio as the best known algorithm for the single server problem. Finally, we show that a class of greedy dispatch policies, including policies that route to the least loaded or the shortest queue, do not admit a constant competitive ratio. When job arrivals are stochastic, with Poisson arrivals and i.i.d. job sizes, we show that random routing and a simple gated-static speed scaling algorithm achieves a constant competitive ratio.
Year
DOI
Venue
2020
10.1109/TNET.2020.2993142
IEEE/ACM Transactions on Networking
Keywords
DocType
Volume
Speed scaling,Shortest Remaining Processing Time (SRPT),parallel servers,competitive ratio
Journal
28
Issue
ISSN
Citations 
4
1063-6692
2
PageRank 
References 
Authors
0.37
0
2
Name
Order
Citations
PageRank
Rahul Vaze146345.64
Jayakrishnan Nair27220.59