  We consider a system of $N$ servers inter-connected by some underlying graph
topology $G_N$. Tasks arrive at the various servers as independent Poisson
processes of rate $\lambda$. Each incoming task is irrevocably assigned to
whichever server has the smallest number of tasks among the one where it
appears and its neighbors in $G_N$. Tasks have unit-mean exponential service
times and leave the system upon service completion.
  The above model has been extensively investigated in the case $G_N$ is a
clique. Since the servers are exchangeable in that case, the queue length
process is quite tractable, and it has been proved that for any $\lambda < 1$,
the fraction of servers with two or more tasks vanishes in the limit as $N \to
\infty$. For an arbitrary graph $G_N$, the lack of exchangeability severely
complicates the analysis, and the queue length process tends to be worse than
for a clique. Accordingly, a graph $G_N$ is said to be $N$-optimal or
$\sqrt{N}$-optimal when the occupancy process on $G_N$ is equivalent to that on
a clique on an $N$-scale or $\sqrt{N}$-scale, respectively.
  We prove that if $G_N$ is an Erd\H{o}s-R\'enyi random graph with average
degree $d(N)$, then it is with high probability $N$-optimal and
$\sqrt{N}$-optimal if $d(N) \to \infty$ and $d(N) / (\sqrt{N} \log(N)) \to
\infty$ as $N \to \infty$, respectively. This demonstrates that optimality can
be maintained at $N$-scale and $\sqrt{N}$-scale while reducing the number of
connections by nearly a factor $N$ and $\sqrt{N} / \log(N)$ compared to a
clique, provided the topology is suitably random. It is further shown that if
$G_N$ contains $\Theta(N)$ bounded-degree nodes, then it cannot be $N$-optimal.
In addition, we establish that an arbitrary graph $G_N$ is $N$-optimal when its
minimum degree is $N - o(N)$, and may not be $N$-optimal even when its minimum
degree is $c N + o(N)$ for any $0 < c < 1/2$.
