  We consider a heterogeneous distributed service system, consisting of $n$
servers with unknown and possibly different processing rates. Jobs with unit
mean and independent processing times arrive as a renewal process of rate
$\lambda n$, with $0<\lambda<1$, to the system. Incoming jobs are immediately
dispatched to one of several queues associated with the $n$ servers. We assume
that the dispatching decisions are made by a central dispatcher endowed with a
finite memory, and with the ability to exchange messages with the servers.
  We study the fundamental resource requirements (memory bits and message
exchange rate) in order for a dispatching policy to be {\bf maximally stable},
i.e., stable whenever the processing rates are such that the arrival rate is
less than the total available processing rate. First, for the case of Poisson
arrivals and exponential service times, we present a policy that is maximally
stable while using a positive (but arbitrarily small) message rate, and
$\log_2(n)$ bits of memory. Second, we show that within a certain broad class
of policies, a dispatching policy that exchanges $o\big(n^2\big)$ messages per
unit of time, and with $o(\log(n))$ bits of memory, cannot be maximally stable.
Thus, as long as the message rate is not too excessive, a logarithmic memory is
necessary and sufficient for maximal stability.
