% $Log:	abstract.tex,v $
% Revision 1.1  93/05/14  14:56:25  starflt
% Initial revision
% 
% Revision 1.1  90/05/04  10:41:01  lwvanels
% Initial revision
% 
%
%% The text of your abstract and nothing else (other than comments) goes here.
%% It will be single-spaced and the rest of the text that is supposed to go on
%% the abstract page will be generated by the abstractpage environment.  This
%% file should be \input (not \include 'd) from cover.tex.
In this thesis, we introduce 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 iterated immediate snapshot (IIS) model of
Borowsky and Gafni. We do so by introducing a novel form of span
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 a task's input
complex to its output complex.

To show the power of our theorem, we use it to derive two new
results. The first includes tight upper and lower bounds on the time
to acheive $n$ process approximate agreement. Our bound of
$\floor{\log_d \frac{input-range}{\epsilon}}$ where $d=3$ for two
processes and $d=2$ for 3 or more shows that the intriguing gap
between the known lower and upper bounds %and  
implied by the work of Aspnes and Herlihy is not a technical
coincidence.  The second is a simple and purely geometric proof
that the time complexity of solving the $k$ process renaming problem
of Attiya et al. when the number of names is $k(k+1)/2$ or more is
$O(1)$. 

More than the new bounds themselves, 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.






