Power-of-d-Choices with Memory: Fluid Limit and Optimality

DOI10.1287/MOOR.2019.1014MaRDI QIDQ3387905zbMATH OpenOpenAlexFDO

Authors Jonatha Anselmi, F. Dufour

Publication date 8 January 2021

Published in Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic optimalityfluid limitrandomized load balancing

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Queues and service in operations research (90B22)

Abstract: In multi-server distributed queueing systems, the access of stochastically arriving jobs to resources is often regulated by a dispatcher, also known as load balancer. A fundamental problem consists in designing a load balancing algorithm that minimizes the delays experienced by jobs. During the last two decades, the power-of-$d$-choice algorithm, based on the idea of dispatching each job to the least loaded server out of $d$ servers randomly sampled at the arrival of the job itself, has emerged as a breakthrough in the foundations of this area due to its versatility and appealing asymptotic properties. In this paper, we consider the power-of-$d$-choice algorithm with the addition of a local memory that keeps track of the latest observations collected over time on the sampled servers. Then, each job is sent to a server with the lowest observation. We show that this algorithm is asymptotically optimal in the sense that the load balancer can always assign each job to an idle server in the large-system limit. This holds true if and only if the system load $lambda$ is less than $1-frac1d$. If this condition is not satisfied, we show that queue lengths are tightly bounded by $leftlceil-fraclog(1-lambda)log(lambdad+1)ightceil$. This is in contrast with the classic version of the power-of-$d$-choice algorithm, where at the fluid scale a strictly positive proportion of servers containing $i$ jobs exists for all $ige0$, in equilibrium. Our results quantify and highlight the importance of using memory as a means to enhance performance in randomized load balancing.

Recommendations

• Stochastic choice with limited memory
• A full-information best-choice problem with finite memory
• Optimal selection with randomly fading memory
• The power of choice for random satisfiability
• Stochastic choice with bounded processing capacity
• On the complexity of finite memory policies for Markov decision processes
• Asymptotically optimal hypothesis testing with memory constraints
• Memory bounds for the experts problem
• A SEQUENTIAL DECISION PROBLEM WITH A FINITE MEMORY

Cites work

• Asymptotic independence of queues under randomized load balancing
• Asymptotic optimality of balanced routing
• Averaging over fast variables in the fluid limit for Markov chains: Application to the supermarket model with memory
• Balanced Allocations
• On the optimal assignment of customers to parallel servers
• On the power of (even a little) resource pooling
• Optimality of the shortest line discipline
• Pull-based load distribution in large-scale heterogeneous service systems
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Randomized longest-queue-first scheduling for large-scale buffered systems
• Redundancy-\(\mathbf{d}\): the power of \(\mathbf{d}\) choices for redundancy
• State space collapse with application to heavy traffic limits for multiclass queueing networks
• The power of slightly more than one sample in randomized load balancing

Cited in

(8)

• Throughput and delay optimality of power-of-\(d\) choices in inhomogeneous load balancing systems
• A lower bound on the queueing delay in resource constrained load balancing
• Asymptotic optimality of power-of-\(d\) load balancing in large-scale systems
• Delay, memory, and messaging tradeoffs in distributed service systems
• Universality of power-of-d load balancing in many-server systems
• Stability, memory, and messaging trade-offs in heterogeneous service systems
• Join-Up-To\((m)\): improved hyperscalable load balancing
• Distributed dispatching in the parallel server model

This page was built for publication: Power-of-d-Choices with Memory: Fluid Limit and Optimality

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