On the Asymptotic Insensitivity of the Supermarket Model in Processor Sharing Systems
- 4 June 2021
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 5 (2), 1-28
- https://doi.org/10.1145/3460089
Abstract
The supermarket model is a popular load balancing model where each incoming job is assigned to a server with the least number of jobs among d randomly selected servers. Several authors have shown that the large scale limit in case of processor sharing servers has a unique insensitive fixed point, which naturally leads to the belief that the queue length distribution in such a system is insensitive to the job size distribution as the number of servers tends to infinity. Simulation results that support this belief have also been reported. However, global attraction of the unique fixed point of the large scale limit was not proven except for exponential job sizes, which is needed to formally prove asymptotic insensitivity. The difficulty lies in the fact that with processor sharing servers, the limiting system is in general not monotone. In this paper we focus on the class of hyperexponential distributions of order 2 and demonstrate that for this class of distributions global attraction of the unique fixed point can still be established using monotonicity by picking a suitable state space and partial order. This allows us to formally show that we have asymptotic insensitivity within this class of job size distributions. We further demonstrate that our result can be leveraged to prove asymptotic insensitivity within this class of distributions for other load balancing systems.Keywords
Funding Information
- FWO (G033119N)
This publication has 14 references indexed in Scilit:
- On the Power-of-d-choices with Least Loaded Server SelectionProceedings of the ACM on Measurement and Analysis of Computing Systems, 2018
- A Fair Comparison of Pull and Push Strategies in Large Distributed NetworksIEEE/ACM Transactions on Networking, 2013
- Asymptotic independence of queues under randomized load balancingQueueing Systems, 2012
- Load balancing via random local search in closed and open systemsACM SIGMETRICS Performance Evaluation Review, 2010
- A mean field model of work stealing in large-scale systemsACM SIGMETRICS Performance Evaluation Review, 2010
- Chapter 4 Monotone Dynamical SystemsPublished by Elsevier BV ,2006
- The power of two choices in randomized load balancingIEEE Transactions on Parallel and Distributed Systems, 2001
- Markov ProcessesWiley Series in Probability and Statistics, 1986
- A comparison of receiver-initiated and sender-initiated adaptive load sharingPerformance Evaluation, 1986
- A Generalization of Erlang's Loss System to State Dependent Arrival and Service RatesMathematics of Operations Research, 1978