  The analysis of large-scale, parallel-server load balancing systems has
relied heavily on mean-field analysis. A pivotal assumption for this framework
is that the servers are exchangeable. However, modern data-centers have data
locality constraints, where tasks of a particular type can only be routed to a
small subset of servers. An emerging line of research, therefore, considers
load balancing algorithms on bipartite graphs where vertices in the two
partitions represent the task types and servers, respectively, and an edge
represents the server's ability to process the corresponding task type. Due to
the lack of exchangeability in this model, the mean-field techniques
fundamentally break down. Recent progress has been made by considering graphs
with strong edge-expansion properties, i.e., where any two large subsets of
vertices are well-connected. However, data locality often leads to spatial
constraints, where edges are local. As a result, these bipartite graphs do not
have strong expansion properties.
  In this paper, we consider the power-of-$d$ choices algorithm and develop a
novel coupling-based approach to establish mean-field approximation for a large
class of graphs that includes spatial graphs. As a corollary, we also show
that, as the system size becomes large, the steady-state occupancy process for
arbitrary regular bipartite graphs with diverging degrees, is indistinguishable
from a fully flexible system on a complete bipartite graph. The method extends
the scope of mean-field analysis far beyond the classical full-flexibility
setup. En route, we prove that, starting from suitable states, the occupancy
process becomes close to its steady state in a time that is independent of $N$.
Such a large-scale mixing-time result might be of independent interest.
Numerical experiments are conducted, which positively support the theoretical
results.
