The power-of-two-choices technique can be applied to a load-balancing
problem known as the \emph{supermarket system}. The model is as
follows: there are $n$ servers, each maintaining its own FIFO queue of
waiting customers. The arrival of customers is modeled as a Poisson
process with mean $\lambda n$ ($\lambda < 1$), and the service time
for each customer as an exponential distribution with mean 1.

If each customer chooses a server at random, then this is simply a set
of $n$ servers, each of which receives a new customer as a Poisson
process with mean $\lambda$, and exponentially-distributed service
time. This is a standard model referred to as the \textsf{M/M/1} model, and
has been extensively studied in the realm of queuing theory. In
particular, it is well known that the system reaches a steady state,
and once it does, the average time a customer spends
in the system (including both waiting in line and being serviced) is
$\frac{1}{1-\lambda}$ \cite{ferrier99:_queuin_theor}.

This seems quite reminiscent of the balls-and-bins problem --- though
now customers are sometimes removed from queues --- which suggests a
power-of-two-choices approach. Indeed, we can improve on this result
if instead each customer chooses $d$ servers at random, and selects
the least-loaded one to wait in the queue for. Mitzenmacher showed
that this system also converges to a steady state, and the average
time in the system is $T_D(\lambda) = \sum_{i=1}^\infty
\lambda^\frac{d^i - d}{d - 1}$ in the steady state
\cite{mitzenmacher01:_power_two_choic_random_load_balan}. Note that
the value of the summands decreases doubly-exponentially with $i$,
since $i$ is in the exponent of the exponent. Taking limits shows that
this complicated summation is indeed the dramatic improvement we have
come to expect from applying the power of two choices: it is
$\bigO{\log \frac{1}{1-\lambda}}$, and in fact as $\lambda$ approaches
1, it converges to $\log_d \frac{1}{1-\lambda}$.

To prove this result, we define $s_i(t)$ to be the fraction of servers
with queues containing $i$ or more customers. We can view this as th
estate space of a Markov chain, as in
Section~\ref{sec:power-of-two-choices:fluid-limit}; unlike the
one-dimensional example in
Section~\ref{sec:power-of-two-choices:fluid-limit}, however, this
state space is \emph{infinite}-dimensional. Nevertheless, we can still
use the same technique of finding a differential equation that
captures the evolution of the system for infinite $n$.

Suppose there are $n$ queues, and consider the change in $m_i$, the
number of queues with at least $i$ customers, over some infinitesimal
time segment. The probability that a new customer arrives is $\lambda
n$. $m_i$ increases only if this new customer selects $d$ queues that
have at least $i-1$ customers, and not all of them have at least $i$
customers. So the increase in $m_i$ is $\lambda n
\left(s_{i-1}^d - s_i^d\right)$. Since the service time for each
customer is exponentially-distributed, a customer will be removed from
the queue with constant probability. $m_i$ decreases only when a
customer is removed from a queue of size exactly $i$, so the expected
decrease is $n\left(s_i - s_{i+1}\right)$. This gives us the
differential equation
\begin{equation}
  \label{eq:queue-diffeq}
  \der{m_i}{t} = \lambda n \left(s_{i-1}^d - s_i^d\right)
  - n\left(s_i - s_{i+1}\right)
\end{equation}£
or, noting that $m_i = n s_i$ and scaling,
\begin{equation}
  \label{eq:queue-diffeq-scaled}
  \der{s_i}{t} = \lambda \left(s_{i-1}^d - s_i^d\right)
  - \left(s_i - s_{i+1}\right)
\end{equation}
These equations apply for $i>0$; the base case is $s_0 = 1$, i.e. all
queues always contain at least 0 elements.

We can now identify the steady-state behavior of the system by finding
a fixed point of the differential equation system in
\eqref{eq:queue-diffeq-scaled}:

\begin{theorem}
  \label{thm:queue-fp}
  For $d \ge 2$, the system in \eqref{eq:queue-diffeq-scaled}
  has a finite fixed point $s_i = \lambda^\frac{d^i - 1}{d - 1}$.
\end{theorem}
\begin{proof}
  At the fixed point, $\der{s_i}{t} = 0$ for all $i \ge 1$. Summing
  over $i \ge 1$, we obtain a telescoping sum
  \begin{align*}
    \lambda \sum_{i=1}^\infty \left(s_{i-1}^d - s_i^d\right)
    - \sum_{i=1}^\infty \left(s_i - s_{i+1}\right) &= 0 \\
    \lambda \left(s_0 - s_\infty\right) - \left(s_1 - s_\infty\right)
    &= 0
\end{align*}
But $s_0 = 1$ by definition, and $s_\infty$ goes to zero, since we
know that queue lengths stabilize at some finite value --- this is a
well-known result in queueing theory for the basic \textsf{M/M/1}
case, and applying the power-of-two-choices technique only improves
things. So $s_1 = \lambda$.

With this base case for $s_1$, a standard inductive argument using
\eqref{eq:queue-diffeq-scaled} now proves the claim that $s_i =
\lambda^\frac{d^i - 1}{d - 1}$.
\end{proof}

It is also necessary to show that the system actually converges to its
fixed point. This proof of the following theorem is quite technical,
so we shall omit the details:

\begin{theorem}
  \label{thm:queue-fp-convergence}
  Suppose the system begins in a finite state ($s_j(0) = 0$ for some
  $j$). Then for all time $t \ge 0$, the $s_i(t)$ always decrease
  doubly exponentially with respect to $i$. If the system begins in
  the empty state, then as $t \to \infty$,  $s_i(t)$ approaches
  $\lambda^\frac{d^i - 1}{d - 1}$ from below.
\end{theorem}
\begin{proof}
  See \cite{mitzenmacher01:_power_two_choic_random_load_balan}.
\end{proof}

We can now use this fixed point of the infinite-limit system to show
properties about our actual systems of finite size. This is done in
the same way as Section~\ref{sec:power-of-two-choices:fluid-limit},
though there are some more technical details (which we omit) relating
to the fact that we now have an infinite set of differential
equations.

\begin{theorem}
  Suppose we have a supermarket system with $n$ servers that begins
  with all queues empty. Then at steady-state, the expected time a
  customer spends in the system is
  \[ \sum_{i=1}^\infty \lambda^\frac{d^i - d}{d - 1} + \littleO{1} \]
\end{theorem}
\begin{proof}
  Suppose a customer arrives in the system at time $t$, and consider
  the probability that he becomes the $i$th customer in some
  queue. This happens only if he selects $d$ queues that have at least
  $i-1$ customers, but not all have at least $i$ customers, i.e.\
  $s_{i-1}(t) - s_i(t)$. We take the expected value by multiplying by
  $i$ and summing over all $i$:
  \begin{align*}
    \Exp{\text{queue time}} &= \sum_{i=1}^\infty i \left(s_{i-1}(t)^d -
      s_i(t)^d\right) \\
    &= \sum_{i=0}^\infty s_i(t)^d
  \end{align*}
  Theorems~\ref{thm:queue-fp} and \ref{thm:queue-fp-convergence} tell
  us that as $t$ grows and the system approaches its steady state,
  \[ \lim_{t\to\infty} \Exp{\text{queue time}} = \sum_{i=0}^\infty
  \lambda^\frac{d^i - d}{d - 1} \]
  Note that since the system starts with all queues empty, the
  expected queue time converges from below, by
  Theorem~\ref{thm:queue-fp-convergence}; i.e. it is always less than
  the limiting value.

  Now we use Kurtz's theorem to relate the result of the infinite
  system to the finite systems of which it is the limiting case. This
  introduces a $\littleO{1}$ term (with respect to $n$) that depends
  on the values of $T$ and $\lambda$, and proves the theorem.
\end{proof}

The above result applies for $d \ge 2$; if $d = 1$, we have the
standard \textsf{M/M/1} model and the expected time in the system is
$\frac{1}{1-\lambda}$, which we can write as $\sum_{i=0}^\infty
\lambda^i$. Notice that applying the power-of-two-choices technique
causes the summed terms to decrease doubly-exponentially rather than
exponentially (the $i$ is now in the exponent of the exponent). Hence,
the expected waiting time is reduced to $\bigO{\log_d
  \frac{1}{1-\lambda}}$. A dramatic improvement comes from allowing
even two choices.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "paper"
%%% End: