Skip to main content

Research Repository

Advanced Search

The impact of load comparison errors on the power-of-d load balancing

Bhambay, Sanidhay; Mukhopadhyay, Arpan; Vasantam, Thirupathaiah

The impact of load comparison errors on the power-of-d load balancing Thumbnail


Sanidhay Bhambay

Arpan Mukhopadhyay


We consider a system with 𝑛 unit-rate servers where jobs arrive according a Poisson process with rate π‘›πœ† (πœ† < 1). In the standard Power-of-𝑑 or Pod scheme with 𝑑 β‰₯ 2, for each incoming job, a dispatcher samples 𝑑 servers uniformly at random and sends the incoming job to the least loaded of the 𝑑 sampled servers. However, in practice, load comparisons may not always be accurate. In this paper, we analyse the effects of noisy load comparisons on the performance
of the Pod scheme. To test the robustness of the Pod scheme against load comparison errors, we assume an adversarial setting where, in the event of an error, the adversary assigns the incoming job to the worst possible server, i.e., the server with the maximum load among the 𝑑 sampled servers. We consider two error models: load-dependent and load-independent errors. In the load-dependent error model, the adversary has limited power in that it is able to cause an
error with probability πœ– ∈ [0, 1] only when the difference in the minimum and the maximum queue lengths of the 𝑑 sampled servers is bounded by a constant threshold 𝑔 β‰₯ 0. For this type of errors, we show that, in the large system limit, the benefits of the Pod scheme are retained even if 𝑔 and πœ– are arbitrarily large as long as the system is heavily loaded, i.e., πœ† is close to 1. In the load-independent error model, the adversary is assumed to be more powerful in that it can cause an error with probability πœ– independent of the loads of the sampled servers. For this model, we show that the performance benefits of the Pod scheme are retained only if πœ– ≀ 1βˆ•π‘‘; for πœ– > 1βˆ•π‘‘
we show that the stability region of the system reduces and the system performs poorly in comparison to the random scheme. Our mean-field analysis uses a new approach to characterise fixed points which neither have closed form solutions nor admit any recursion. Furthermore, we develop a generic approach to prove tightness and stability for any state-dependent load balancing scheme.


Bhambay, S., Mukhopadhyay, A., & Vasantam, T. (2024). The impact of load comparison errors on the power-of-d load balancing. Performance Evaluation, 164, Article 102408.

Journal Article Type Article
Acceptance Date Feb 22, 2024
Online Publication Date Feb 28, 2024
Publication Date 2024-05
Deposit Date May 15, 2024
Publicly Available Date May 15, 2024
Journal Performance Evaluation
Print ISSN 0166-5316
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 164
Article Number 102408
Public URL


You might also like

Downloadable Citations