Optimal Load Balancing with Locality Constraints

Wentao Weng, Xingyu Zhou, R. Srikant

Research output: Contribution to journalArticlepeer-review


Applications in cloud platforms motivate the study of efficient load balancing under job-server constraints and server heterogeneity. In this paper, we study load balancing on a bipartite graph where left nodes correspond to job types and right nodes correspond to servers, with each edge indicating that a job type can be served by a server. Thus edges represent locality constraints, i.e., an arbitrary job can only be served at servers which contain certain data and/or machine learning (ML) models. Servers in this system can have heterogeneous service rates. In this setting, we investigate the performance of two policies named Join-The-Fastest-of-The-Shortest-Queue (JFSQ) and Join-The-Fastest-of-The-Idle-Queue (JFIQ), which are simple variants of Join-The-Shortest-Queue and Join-The-Idle-Queue, where ties are broken in favor of the fastest servers. Under a "well-connected'' graph condition, we show that JFSQ and JFIQ are asymptotically optimal in the mean response time when the number of servers goes to infinity. In addition to asymptotic optimality, we also obtain upper bounds on the mean response time for finite-size systems. We further show that the well-connectedness condition can be satisfied by a random bipartite graph construction with relatively sparse connectivity.

Original languageEnglish (US)
Pages (from-to)49-50
Number of pages2
JournalPerformance Evaluation Review
Issue number1
StatePublished - Jun 2021


  • asymptotic optimality
  • cloud computing
  • delay performance
  • load balancing

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Optimal Load Balancing with Locality Constraints'. Together they form a unique fingerprint.

Cite this