BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/734
DTSTAMP:20230914T125936Z
SUMMARY:Universality of Power-of-$d$ Load Balancing in Many-Server Systems
DESCRIPTION:Speaker: Debankur Mukherjee (Technische Universiteit Eindhoven\
nDepartment of Mathematics and Computer Science\n5612 AZ Eindhoven\nNether
lands)\n\nAbstract: \nWe consider a system of $N$~parallel single-server q
ueues with unit exponential service rates and a single dispatcher where ta
sks arrive as a Poisson process of rate $\\lambda(N)$.\nWhen a task arrive
s\, the dispatcher assigns it to a server with the shortest queue among $d
(N)$ randomly selected servers ($1 \\leq d(N) \\leq N$). This load balanci
ng strategy is referred to as a JSQ($d(N)$) scheme\, marking that it subsu
mes the celebrated Join-the-Shortest Queue (JSQ) policy as a crucial speci
al case for $d(N) = N$.\nWe construct a stochastic coupling to bound the d
ifference in the queue length processes between the JSQ policy and a schem
e with an arbitrary value of $d(N)$. We use the coupling to derive the flu
id limit in the regime where $\\lambda(N) / N \\to \\lambda < 1$ as $N \\t
o \\infty$ with $d(N) \\to\\infty$\, along with the associated fixed point
. The fluid limit turns out not to depend on the exact growth rate of $d(N
)$\, and in particular coincides with that for the ordinary JSQ policy. We
further leverage the coupling to establish that the diffusion limit in th
e critical regime where $(N - \\lambda(N)) / \\sqrt{N} \\to \\beta > 0$ as
$N \\to \\infty$ with $d(N)/(\\sqrt{N} \\log (N))\\to\\infty$ corresponds
to that for the JSQ policy. These results indicate that the optimality of
the JSQ policy can be preserved at the fluid-level and diffusion-level wh
ile reducing the overhead by nearly a factor O($N$) and O($\\sqrt{N}/\\log
(N)$)\, respectively.\n
URL:https://www.tcs.tifr.res.in/web/events/734
DTSTART;TZID=Asia/Kolkata:20161221T160000
DTEND;TZID=Asia/Kolkata:20161221T170000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR