CSTIO Seminar with Dr Sanidhay Bhambay (Durham University)

The power of two choices with load comparison errors

Abstract

We consider a system with n unit-rate servers where jobs arrive according a Poisson process with rate nλ (λ < 1). In the standard Power-of-two or Po2 scheme, for each incoming job, a job dispatcher samples two servers uniformly at random and sends the incoming job to the least loaded of the two sampled servers. However, in practice, the load information may not be accurate at the job dispatcher. In this paper, we analyze the effects of erroneous load comparisons on the performance of the Po2 scheme. Specifically, we consider load-dependent and load-independent errors. In the load-dependent error model, an incoming job is sent to the server with the larger queue length among the two sampled servers with an error probability ε if the difference in the queue lengths of the two sampled servers is less than or equal to a constant g; no error is made if the queue-length difference is higher than g. For this type of errors, we show that, in the large system limit, the benefits of the Po2 scheme are retained for all values of g and ε as long as the system is heavily loaded, i.e., λ is close to 1. In the load-independent error model, the incoming job is sent to the sampled server with the maximum load with an error probability of ε independent of the loads of the sampled servers. For this model, we show that the performance benefits of the Po2 scheme are retained only if ε ≤ 1/2; for ε > 1/2 we show that the stability region of the system reduces and the system performs poorly in comparison to the random scheme. To prove our stability results, we develop a generic approach to bound the drifts of Lyapunov functions for any state-dependent load balancing scheme. Furthermore, the mean-field analysis in our paper uses a new approach to characterise fixed points which do not admit a recursion.

About the speaker

Sanidhay is an INFORMED AI Hub Research Associate based at Durham University. He is working with Neil Walton and Thiru Vasantam. He earned his Ph.D. in computer science from the University of Warwick, UK in 2024. He completed his M.Tech. (Research) degree in electrical engineering from the Indian Institute of Science, Bengaluru, India, in 2018. His research interests encompass queuing theory, performance analysis of large complex networks, applied probability, stochastic modelling, and limits of stochastic processes.