TY - JOUR
T1 - Join Idle Queue with Service Elasticity
T2 - Large-Scale Asymptotics of a Nonmonotone System
AU - Mukherjee, Debankur
AU - Stolyar, Alexander
N1 - Funding Information:
D. Mukherjee was supported by The Netherlands Organization for Scientific Research (NWO) through Gravitation Networks [Grant 024.002.003] and TOP-GO [Grant 613.001.012].
Publisher Copyright:
© 2019 The Author(s).
PY - 2019/12
Y1 - 2019/12
N2 - We consider the model of a token-based joint autoscaling and load-balancing strategy, proposed in a recent paper by Mukherjee et al. [Mukherjee D, Dhara S, Borst SC, Van Leeuwaarden JSH (2017) Optimal service elasticity in large-scale distributed systems. Proc. ACM Measurement Anal. Comput. Systems 1(1):25:1–25:28.], which offers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers N → ∞. In the aforementioned work, the asymptotic results are obtained under the assumption that the queues have fixed-size finite buffers, and therefore, the fundamental question of stability of the proposed scheme with infinite buffers was left open. In this paper, we address this fundamental stability question. The system stability under the usual subcritical load assumption is not au-tomatic. Moreover, the stability may not even hold for all N. The key challenge stems from the fact that the process lacks monotonicity, which has been the powerful primary tool for establishing stability in load-balancing models. We develop a novel method to prove that the subcritically loaded system is stable for large enough N and establish convergence of steady-state distributions to the optimal one as N → ∞. The method goes beyond the state-of-the-art techniques; it uses an induction-based idea and a “weak monotonicity” property of the model. This technique is of independent interest and may have broader applicability.
AB - We consider the model of a token-based joint autoscaling and load-balancing strategy, proposed in a recent paper by Mukherjee et al. [Mukherjee D, Dhara S, Borst SC, Van Leeuwaarden JSH (2017) Optimal service elasticity in large-scale distributed systems. Proc. ACM Measurement Anal. Comput. Systems 1(1):25:1–25:28.], which offers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers N → ∞. In the aforementioned work, the asymptotic results are obtained under the assumption that the queues have fixed-size finite buffers, and therefore, the fundamental question of stability of the proposed scheme with infinite buffers was left open. In this paper, we address this fundamental stability question. The system stability under the usual subcritical load assumption is not au-tomatic. Moreover, the stability may not even hold for all N. The key challenge stems from the fact that the process lacks monotonicity, which has been the powerful primary tool for establishing stability in load-balancing models. We develop a novel method to prove that the subcritically loaded system is stable for large enough N and establish convergence of steady-state distributions to the optimal one as N → ∞. The method goes beyond the state-of-the-art techniques; it uses an induction-based idea and a “weak monotonicity” property of the model. This technique is of independent interest and may have broader applicability.
KW - fluid limit
KW - join idle queue
KW - load balancing
KW - mean-field limit
KW - stability
UR - http://www.scopus.com/inward/record.url?scp=85148618473&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85148618473&partnerID=8YFLogxK
U2 - 10.1287/stsy.2019.0030
DO - 10.1287/stsy.2019.0030
M3 - Article
AN - SCOPUS:85148618473
SN - 1946-5238
VL - 9
SP - 338
EP - 358
JO - Stochastic Systems
JF - Stochastic Systems
IS - 4
ER -