Delay, memory, and messaging tradeoffs in distributed service systems

DOI10.1287/STSY.2017.0008zbMATH Open1446.60066arXiv1709.04102OpenAlexW2788690370WikidataQ130200907 ScholiaQ130200907MaRDI QIDQ5113878FDOQ5113878

John N. Tsitsiklis, David Gamarnik, Martin Zubeldia

Publication date: 18 June 2020

Published in: Stochastic Systems (Search for Journal in Brave)

Abstract: We consider the following distributed service model: jobs with unit mean, exponentially distributed, and independent processing times arrive as a Poisson process of rate $lambdan$, with $0<lambda<1$, and are immediately dispatched by a centralized dispatcher to one of $n$ First-In-First-Out queues associated with $n$ identical servers. The dispatcher is endowed with a finite memory, and with the ability to exchange messages with the servers. We propose and study a resource-constrained "pull-based" dispatching policy that involves two parameters: (i) the number of memory bits available at the dispatcher, and (ii) the average rate at which servers communicate with the dispatcher. We establish (using a fluid limit approach) that the asymptotic, as $noinfty$, expected queueing delay is zero when either (i) the number of memory bits grows logarithmically with $n$ and the message rate grows superlinearly with $n$, or (ii) the number of memory bits grows superlogarithmically with $n$ and the message rate is at least $lambdan$. Furthermore, when the number of memory bits grows only logarithmically with $n$ and the message rate is proportional to $n$, we obtain a closed-form expression for the (now positive) asymptotic delay. Finally, we demonstrate an interesting phase transition in the resource-constrained regime where the asymptotic delay is non-zero. In particular, we show that for any given $alpha>0$ (no matter how small), if our policy only uses a linear message rate $alphan$, the resulting asymptotic delay is upper bounded, uniformly over all $lambda<1$; this is in sharp contrast to the delay obtained when no messages are used ($alpha=0$), which grows as $1/(1-lambda)$ when $lambdauparrow1$, or when the popular power-of-$d$-choices is used, in which the delay grows as $log(1/(1-lambda))$.

Full work available at URL: https://arxiv.org/abs/1709.04102

Recommendations

• A lower bound on the queueing delay in resource constrained load balancing
• Stability, memory, and messaging trade-offs in heterogeneous service systems
• Power-of-d-Choices with Memory: Fluid Limit and Optimality
• On the power of (even a little) resource pooling
• Asymptotic optimality of power-of-\(d\) load balancing in large-scale systems

zbMATH Keywords

queueing theorylarge-scale systemsload balancingperformance tradeoffs

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Large loss networks
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Decay of tails at equilibrium for FIFO join the shortest queue networks
• Title not available (Why is that?)
• On the Stochastic Matrices Associated with Certain Queuing Processes
• Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions
• State space collapse with application to heavy traffic limits for multiclass queueing networks
• Chebyshev-Haar systems in the theory of discontinuous Kellogg kernels
• Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers
• Pull-based load distribution in large-scale heterogeneous service systems
• Large-scale join-idle-queue system with general service times

Cited In (10)

• Self-Learning Threshold-Based Load Balancing
• Information and Memory in Dynamic Resource Allocation
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Stability, Memory, and Messaging Trade-Offs in Heterogeneous Service Systems
• Join-Up-To\((m)\): improved hyperscalable load balancing
• Near equilibrium fluctuations for supermarket models with growing choices
• Zero-wait load balancing with sparse messaging
• Performance Analysis of Joining the Shortest Queue Model Among a Large Number of Queues
• A lower bound on the queueing delay in resource constrained load balancing
• Economies-of-Scale in Many-Server Queueing Systems: Tutorial and Partial Review of the QED Halfin--Whitt Heavy-Traffic Regime

This page was built for publication: Delay, memory, and messaging tradeoffs in distributed service systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113878)