  In this paper, we consider a load balancing system under a general pull-based
policy. In particular, each arrival is randomly dispatched to one of the
servers whose queue lengths are below a threshold, if there are any; otherwise,
this arrival is randomly dispatched to one of the entire set of servers. We are
interested in the fundamental relationship between the threshold and the delay
performance of the system in heavy traffic. To this end, we first establish the
following necessary condition to guarantee heavy-traffic delay optimality: the
threshold will grow to infinity as the exogenous arrival rate approaches the
boundary of the capacity region (i.e., the load intensity approaches one) but
the growth rate should be slower than a polynomial function of the mean number
of tasks in the system. As a special case of this result, we directly show that
the delay performance of the popular pull-based policy Join-Idle-Queue (JIQ)
lies strictly between that of any heavy-traffic delay optimal policy and that
of random routing. We further show that a sufficient condition for
heavy-traffic delay optimality is that the threshold grows logarithmically with
the mean number of tasks in the system. This result directly resolves a
generalized version of the conjecture by Kelly and Laws.
