The Power of Two Choices with Load Comparison Errors

Bhambay, Sanidhay; Mukhopadhyay, Arpan; Vasantam, Thirupathaiah

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.

Citation

Bhambay, S., Mukhopadhyay, A., & Vasantam, T. (2023). The Power of Two Choices with Load Comparison Errors. In MobiHoc '23: Proceedings of the Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing (121-130). https://doi.org/10.1145/3565287.3610259

• Conference Name: MobiHoc '23: The Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
• Conference Location: Washington, DC
• Start Date: Oct 23, 2023
• End Date: Oct 26, 2023
• Acceptance Date: Jul 14, 2023
• Online Publication Date: Oct 16, 2023
• Publication Date: 2023-10
• Deposit Date: Aug 4, 2023
• Publicly Available Date: Oct 25, 2023
• Publisher: Association for Computing Machinery (ACM)
• Pages: 121-130
• Book Title: MobiHoc '23: Proceedings of the Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
• ISBN: 9781450399265
• DOI: https://doi.org/10.1145/3565287.3610259
• Public URL: https://durham-repository.worktribe.com/output/1712137