% -*- Mode:TeX -*-

%% The documentstyle options along with the pagestyle can be used to generate
%% a technical report, a draft copy, or a regular thesis.  You may need to
%% re-specify the pagestyle after you \include  cover.tex.  For more
%% information, see the first few lines of mitthesis.sty. 


\documentstyle[amstex, tgrind, gen, iohdr, boxedminipage, epsf, tmacros, psfig]{esub2acm}
%\pagestyle{plain} 

%%This bit allows you to either specify only the files which you wish to
%% process, or `all' to process all f
%% Krishna Sethuraman (1990).

\include{com}
\begin{document}
\begin{titlepage}
\title{Towards a Topological Characterization of Asynchronous
Complexity \\ {\large\it (Latest Draft -- Do Not Distribute)}}

\author{Gunnar Hoest \\ {\it M.I.T.\/} \and Nir Shavit \\ {\it
Tel-Aviv University and M.I.T. \/}}

%\maketitle 
\begin{abstract}  
This paper introduces the use of topological models and methods,
formerly used to analyze computability, as tools for the
quantification and classification of {\it asynchronous complexity}.
We present the first {\it asynchronous complexity theorem}, applied to
decision tasks in the IIS memory model of Borowsky and Gafni.  We do
so by introducing a novel form of topological tool called the {\it
non-uniform chromatic subdivision}. Building on the framework of
Herlihy and Shavit's topological computability model, our theorem
states that the time complexity of any asynchronous algorithm is
directly proportional to the level of non-uniform chromatic
subdivisions necessary to allow a simplicial map from the complex
representing a task's inputs to the one representing its outputs.

To show the power of our theorem, we use it to derive two new
results. The first is a tight upper/lower bound on the time to acheive
$N$ process approximate agreement: $\floor{\log_d
\frac{\mathit{input\_range}}{\epsilon}}$ where $d=3$ for two processes
and $d=2$ for 3 or more.  The second is the first {\it
time-complexity/number-of-names} upper bound tradoff for the renaming
problem:
$$
       \frac{N(N+1)}{2} - \Sigma_{i=2}^{\mbox{\it time\/}(N)} N-i \leq
\mbox{\it names\/}(N) < \frac{N(N+1)}{2} - \Sigma_{i=2}^{\mbox{\it
time\/}(N)-1} N-i.
$$ This upper bound formula quantifies an interesting non-linear
relationship between the number of names and the computation time used
to solve $N$ process renaming. %Our theorem provides the matching
%algorithm directly from the problem's geometric representation.

More than the new bounds themselves, we beleive the importance of our
asynchronous complexity theorem is that the algorithms and lower
bounds it allows us to derive are intuitive and simple, with
topological proofs that require no mention of concurrency at all.
\end{abstract} % end of abstract 
\maketitle

%\begin{bottomstuff}
%Contact author: Nir Shavit, \begin{verbatim}shanir@theory.lcs.mit.edu.\end{verbatim} 
%\end{bottomstuff}
\end{titlepage}
\markboth{G. Hoest and N. Shavit}
{A Characterization of Asynchronous Complexity}

%\include{cover}
%\pagestyle{plain}
%\include{contents}
\include{introduction}
\include{c1_model}
\include{c2_math}
\include{c3_theorem}
\include{c4_applications}
\include{c5_renaming}
%\appendix
%\include{appa}
%\include{appb}
\include{biblio}
\end{document}


