In this paper the authors study the dynamic randomized load balancing model, which is often referred to as the supermarket model. Speciﬁcally, they study two load balancing policies for the supermarket model. In each case, jobs arrive at the bank of N servers according to a rate αN Poisson process, with α < 1. The servers each employ the same service discipline and the service times are iid with a given arbitrary distribution F(·) having mean 1. Service at each queue is assumed to be non-idling. The Join the Shortest Queue policy SQ(D) assigns each arrival to the shortest of D queues chosen independently and uniformly at random, where the shortest queue means the queue with the least number of jobs. With the Join the Last Loaded Queue policy LL(D) the arrival is instead assigned to the queue with the smallest amount of remaining work, or workload. In both cases, the D queues are chosen without replacement, from among the CN,D possible sets. Ties are assumed to be broken randomly, with the arriving job being assigned with equal probability to each of the queues. In this context the authors deﬁne an approach to analyze the limiting behavior of the equilibrium distribution, at a given queue, as N →∞, formulating a general statement (an ansatz). They consider several settings under which they are able to prove this ansatz and they state and prove three theorems that correspond to those settings. Leonardo Pasini

### Matematica Review atout: (Bramson, Maury ; Lu, Yi ; Prabhakar, Balaji - "Asymptotic independence of queues under randomized load bilancing"- Queueing Syst. 71 (2012), no.3, 247–292.)

#### Abstract

In this paper the authors study the dynamic randomized load balancing model, which is often referred to as the supermarket model. Speciﬁcally, they study two load balancing policies for the supermarket model. In each case, jobs arrive at the bank of N servers according to a rate αN Poisson process, with α < 1. The servers each employ the same service discipline and the service times are iid with a given arbitrary distribution F(·) having mean 1. Service at each queue is assumed to be non-idling. The Join the Shortest Queue policy SQ(D) assigns each arrival to the shortest of D queues chosen independently and uniformly at random, where the shortest queue means the queue with the least number of jobs. With the Join the Last Loaded Queue policy LL(D) the arrival is instead assigned to the queue with the smallest amount of remaining work, or workload. In both cases, the D queues are chosen without replacement, from among the CN,D possible sets. Ties are assumed to be broken randomly, with the arriving job being assigned with equal probability to each of the queues. In this context the authors deﬁne an approach to analyze the limiting behavior of the equilibrium distribution, at a given queue, as N →∞, formulating a general statement (an ansatz). They consider several settings under which they are able to prove this ansatz and they state and prove three theorems that correspond to those settings. Leonardo Pasini
##### Scheda breve Scheda completa Scheda completa (DC)
2012
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11581/330781`
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• ND
• ND