\documentclass[12pt,twoside]{mitthesis}
\usepackage{url}
\usepackage{amsmath,amssymb,amsfonts,amsthm}
% Use clrscode for \Proc. Probably a bit of overkill.
\usepackage{clrscode}
\usepackage{graphicx}
\usepackage[format=hang,font=small,labelfont=bf,textfont=it]{caption}
\usepackage{float}
\usepackage{nicefrac}
\usepackage{fancyhdr}
\usepackage[usenames]{color}
\usepackage{subfig}
\usepackage{boxedminipage}

% More algorithmic stuff
\newcommand{\bigO}[1]{\ensuremath{O\left(#1\right)}}
\newcommand{\littleO}[1]{\ensuremath{o\left(#1\right)}}
\newcommand{\bigTheta}[1]{\ensuremath{\Theta\left(#1\right)}}
\newcommand{\bigOmega}[1]{\ensuremath{\Omega\left(#1\right)}}
\newcommand{\littleOmega}[1]{\ensuremath{\omega\left(#1\right)}}

% Draftification
\newif\ifdraft
%\drafttrue
\draftfalse

\AtBeginDocument{
\ifdraft
\typeout{WARNING: margin notes visible}
\fi
}


\ifdraft
\usepackage[fancyhdr,short,revrange]{svninfo}
\fi


\pagestyle{fancy}

% Margin notes
\newcommand{\marnote}[1]{%
\ifdraft%
\setlength{\marginparwidth}{\oddsidemargin}%
\addtolength{\marginparwidth}{1in}%
\addtolength{\marginparwidth}{-\marginparsep}%
\marginpar{\color{red}\raggedright \scriptsize \em #1}%
\fi}

\begin{document}

\ifdraft
\svnInfo $Id$
\fi

\ifdraft
\pagestyle{fancy}
\fancyhead[LE,RO]{\slshape \rightmark} 
\fancyhead[LO,RE]{\slshape \leftmark} 
%\fancyhead[LO,LE]{*** DRAFT ***} 
\else
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{}
\rfoot{}
\pagestyle{plain}
\fi

\title{{\em Arpeggio}: Metadata~Indexing in a
  Structured~Peer-to-Peer~Network}
\author{Dan R. K. Ports}
\prevdegrees{S.\ B., Computer Science and Engineering\\
  Massachusetts Institute of Technology, 2005\vspace{0.5em}\\
  S.\ B., Mathematics\\
  Massachusetts Institute of Technology, 2005}

\department{Department~of~Electrical~Engineering~and~Computer~Science}
\degree{Master of Engineering in Electrical~Engineering and
  Computer~Science}
\degreemonth{February}
\degreeyear{2007}
\thesisdate{February 2, 2007}   % XXX
\supervisor{David R. Karger}{Professor of Electrical Engineering and
  Computer Science}
\chairman{Arthur C. Smith}{Chairman, Department Committee on Graduate
  Students}
\maketitle

\cleardoublepage

\setcounter{savepage}{\thepage}
\begin{abstractpage}
  Peer-to-peer networks require an efficient means for performing
  searches for files by metadata keywords. Unfortunately, current
  methods usually sacrifice either scalability or recall.
  \emph{Arpeggio} is a peer-to-peer file-sharing network that uses the
  Chord lookup primitive as a basis for constructing a
  \emph{distributed keyword-set index}, augmented with index-side
  filtering, to address this problem.  We introduce \emph{index
    gateways}, a technique for minimizing index maintenance overhead.
  Arpeggio also includes a content distribution system for finding
  source peers for a file; we present a novel system that uses Chord
  subrings to track live source peers without the cost of inserting
  the data itself into the network, and supports \emph{postfetching}:
  using information in the index to improve the availability of rare
  files. The result is a system that provides efficient query
  operations with the scalability and reliability advantages of full
  decentralization. We use analysis and simulation results to show
  that our indexing system has reasonable storage and bandwidth costs,
  and improves load distribution. 
\end{abstractpage}

\chapter*{Acknowledgments}
\input{acknowledgments.tex}

\cleardoublepage
\tableofcontents
\cleardoublepage
\listoffigures
\cleardoublepage
\listoftables


\chapter{Overview}
\label{chap:overview}
\input{introduction.tex}

\section{Outline}
\label{sec:outline}

The remainder of this thesis proceeds as
follows. Chapter~\ref{chap:background} provides necessary background
on indexing techniques and distributed hash
tables. Chapter~\ref{chap:indexing} discusses techniques for building
indexes for efficient searching in distributed systems. We discuss
various approaches to indexing, incrementally building up Arpeggio's
algorithm and comparing it to related
work. Chapter~\ref{chap:content-distribution} turns to the problem of
content distribution; we present two content distribution subsystems
that can be used in conjunction with our indexing system, one based on
BitTorrent and one designed from
scratch. Chapter~\ref{chap:implementation} presents our implementation
of the system, with commentary on its high-level architecture, and
discusses its user interface. Chapter~\ref{chap:evaluation} evaluates
the feasibility and effectiveness of the system in the contexts of
various sample applications, and Chapter~\ref{chap:conclusion}
concludes.

\chapter{Background and Related Work}
\label{chap:background}
\input{background.tex}


\chapter{Indexing Techniques}
\label{chap:indexing}
\input{indexing.tex}

\chapter{Content Distribution}
\label{chap:content-distribution}
\input{content-distribution.tex}

\chapter{Implementation Notes}
\label{chap:implementation}
\input{implementation.tex}

\chapter{Evaluation}
\label{chap:evaluation}
\input{evaluation.tex}

\chapter{Conclusion}
\label{chap:conclusion}
\input{conclusion.tex}





\bibliographystyle{plain}
\bibliography{bibliography/bibliography}
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-command-default: "rubber"
%%% End: