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

Jonatha Anselmi () and Francois Dufour ()
Additional contact information
Jonatha Anselmi: Université Grenoble Alpes, CNRS, INRIA, Grenoble INP, LIG, 38000 Grenoble, France; INRIA Bordeaux Sud Ouest, Team: CQFD, 33000 Bordeaux, France
Francois Dufour: Institut Polytechnique de Bordeaux, INRIA Bordeaux Sud Ouest, Team: CQFD, IMB, Institut de Mathématiques de Bordeaux, Université de Bordeaux, 33000 Bordeaux, France

Mathematics of Operations Research, 2020, vol. 45, issue 3, 862-888

Abstract: In multiserver distributed queueing systems, the access of stochastically arriving jobs to resources is often regulated by a dispatcher, also known as a 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 because of 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 λ is less than 1 − 1 d . If this condition is not satisfied, we show that queue lengths are bounded by ⌈ − log ( 1 − λ ) log ( λd + 1 ) ⌉ . This is in contrast with the classic version of the power-of- d -choice algorithm, in which, at the fluid scale, a strictly positive proportion of servers containing i jobs exists for all i ≥ 0 in equilibrium. Our results quantify and highlight the importance of using memory as a means to enhance performance in randomized load balancing.

Keywords: randomized load balancing; asymptotic optimality; fluid limit (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/moor.2019.1014 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:45:y:2020:i:3:p:862-888

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().