Title of the talk: Load balancing in queues with redundancy
Speaker: Dr. Tejas Bodas, Assistant Professor, IIT Dharwad.
Day, Date and Time: Tuesday, August 10, 2021, 11 am to 12 pm.
Abstract of the talk: Load balancing refers to the process of distributing arriving jobs evenly across a set of parallel servers. Load balancing policies are widely used in large server farms such as cloud computing clusters,distributed storage systems, transportation and healthcare systems and in computer architecture. A simple policy that is often implemented in such systems is join shortest queue (JSQ), where the arriving jobs are made to join the queue with the least number of jobs. However, joining the queue with least amount of pending work, join shortest work (JSW) policy, is known to perform better than JSQ. While the superiority of JSW is attractive, obtaining the exact workload information in practical systems is known to be difficult and this makes the JSW policy difficult to implement.
In this talk, we will look at one possible method of implementing JSW via redundancy. For each arriving job, redundancy based policies first create multiple copies of the same job and assign these copies to a subset of servers. Extra copies of the job are cancelled, either according to the cancel-on-start (c.o.s.) policy or cancel-on-complete (c.o.c.) policy. In c.o.s. (or c.o.c), when one of the server starts (or completes) serving a copy, the other copies are cancelled. In this talk, we will see that the c.o.s. policy is equivalent to JSW and can be used to implement JSW without actually requiring the workload information. Towards its analysis, we introduce a generic token based queueing model that not only covers redundancy models but also subsumes a wide variety of Markovian queueing models including the popular multi-type job and server model of Visschers et al. (Queueing Systems 2012) and the order independent queueing model of Krzesinski (Queueing Networks, 2011). Our key result for the token based model shows that the stationary distribution of the underlying Markov chain has a product form which is desirable to gain better insights on the system performance.
This talk is based on a joint work with U. Ayesta and Maaike Verloop from the University of Toulouse and J.L. Dorsman from the University of Amsterdam.
About the Speaker: Tejas Bodas is an Assistant Professor at IIT Dharwad working in the area of Performance modeling for queueing systems. His research interests are in Stochastic processes, Mean-field approximations, Game theory, Reinforcement learning, and Markov decision processes. Prior to this, he was a CV Raman postdoc at IISc, a visiting postdoc at the University of Antwerp in Belgium, a postdoc at LAAS, CNRS in Toulouse, France, and a visiting fellow at TIFR, Mumbai. He has a Masters and Ph.D degree from IIT Bombay.