\documentclass[11pt,draft]{article}
\input{../../generic-preamble/generic-preamble}
\usepackage{url,clrscode}

\begin{document}
\title{On the Power of Two Choices: Theory and Applications}
\author{Dan Ports, Sarah Lieberman, and Galen Pickard\\
  \texttt{\{drkp,sarahl,gpickard\}@mit.edu}}
\maketitle
\begin{abstract}
  The power of two choices is a simple technique for randomized load
  balancing: to assign an item to a server, simply select two (or
  more) random servers, and assign it to the least heavily loaded.
  Nevertheless, it obtains a dramatic improvement over simply choosing
  one server at random: the maximum load drops by an exponential
  factor. We review this result, and provide a survey of variations on
  the technique that either improve its performance or generalize its
  applicability. In addition, we examine how it can be applied to
  several common problems.
\end{abstract}

\tableofcontents

\newpage

\section{Overview}
\label{sec:overview}
\input{intro}


\section{The Power of Two Choices}
\label{sec:power-of-two-choices}
\input{potc}

\subsection{The Fluid-Limit Approach}
\label{sec:power-of-two-choices:fluid-limit}
\input{fluid-limit}


\section{Variations}
\label{sec:variations}

The basic power-of-two-choices result has since been modified in
several ways, both to generalize it to variations on the same problem,
and to improve its performance further. In this section, we consider a
few of these changes.

\subsection{Geometric Generalization}
\label{sec:variations:geometry}
\input{geometry}

\subsection{Asymmetric Tie-breaking}
\label{sec:variations:asymmetry}
\input{asymmetry}

\subsection{Memory}
\label{sec:variations:memory}
\input{memory}


\section{Applications}
\label{sec:applications}

These results have direct applications to a number of load-balancing
problems. In this section, we will consider what needs to be done to
apply it to three problems, and what results are obtained. The
technique proves to be a useful load-balancing technique not just
asymptotically in theory, but also empirically in practice and
simulation.

\subsection{Supermarket Load Balancing}
\label{sec:applications:load-balancing}
\input{load-balancing}

\subsection{Distributed Hash Tables}
\label{sec:applications:p2p}
\input{p2p}

\subsection{Router IP Lookups}
\label{sec:applications:routers}
\input{routers}


\section{Conclusion}
\label{sec:conclusion}
\input{conclusion}

\nocite{*}
\bibliographystyle{ieeetr}
\bibliography{paper}
\end{document}