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