Skip to main content

Research Repository

Advanced Search

The Power of Two Choices with Load Comparison Errors

Bhambay, Sanidhay; Mukhopadhyay, Arpan; Vasantam, Thirupathaiah

The Power of Two Choices with Load Comparison Errors Thumbnail


Authors

Sanidhay Bhambay

Arpan Mukhopadhyay



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, October). The Power of Two Choices with Load Comparison Errors. Presented at MobiHoc '23: The Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, Washington, DC

Presentation Conference Type Conference Paper (published)
Conference Name MobiHoc '23: The Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
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

Files





You might also like



Downloadable Citations