\section{Introduction}
% improves herlihy and gafni
% gives simple intuitive proofs
% complexity of IIS related to other models
% 
As we enter the 21st century, computers are being used more and more
as coordination devices, making standard (Turing) notions of
computability and complexity insufficient for evaluating their
behaviour in our mostly asynchronous world.  In the last few years,
techniques of modeling and analysis based on classical algebraic
topology
\cite{AttiyaR95,BGSIMM,CHLT93,GafniK95,HR94,HerlihyR95,HerlihyR96,HS93,HS94,HS95,SaksZaharoglou}
in conjunction with distributed simulation methods
\cite{BGSIMM,BorowskyGafni,BorowskyGafniPODC,LynchR95} have brought
about significant progress in our understanding of computability
problems in an asynchronous distributed setting.  We feel the time is
ripe to extend these techniques to address {\it asynchronous
complexity}.

This paper studies the class of problems called {\it decision tasks},
input/output problems in which $N$ asynchronous processes start with
input values, communicate via shared memory and halt with private
output values.  We focus on %a memory model that is a variant of 
a generalized version of
Borosky and Gafni's Iterated Immediate Snapshot (IIS) model
\cite{BGSIMM}, called the Non-uniform Iterated Immediate Snapshot (NIIS)
 Model. The IIS model has already been successfully used by Borowsky
and Gafni \cite{BGSIMM} as part of their new simplified proof of the
asynchronous computability theorem \cite{HS95}. The model is a
restriction of atomic snapshot memory that guarantees that processes'
scan operations return views that contain non-decreasing sets of the
participating processes' inputs. We believe it is a good first
candidate for topological modeling since it has a particularly nice
geometric representation, and hence easily lends itself to topological
analysis.
%Moreover, a new result 
%by Hoest, Lynch, and Shavit \cite{HLS97} 
%shows that any time complexity lower bound in the IIS model 
%is also a lower bound in the Multi-reader Multi-writer register model (MRMW)
%\cite{VitanyiA86,Lynch-book} 
%and the Atomic Snapshot model (AS)  \cite{AfekADGMS90-sub,Anderson}. 

Keeping in style with Herlihy and Shavit's topological computability
framework \cite{HS95}, our theorem states that the worst case time
complexity for solving a decision task in the NIIS model is equivalent
to the minimal number of non-uniform chromatic subdivisions of the
input complex necessary to allow a simplicial map from the input
complex to the output complex.  The theorem also immediately provides
a matching upper bound given the subdivision and mapping.

The non-uniform chromatic subdivisions we introduce (See
Figure~\ref{Fig2} for examples) are a looser and more general form of
standard chromatic subdivisions \cite{HS95}.  Unlike the iterated
standard chromatic subdivisions used in the computability work of
\cite{HS95,BGSIMM}, they allow individual simplices in a complex to be
subdivided a different number of times, while assuring that the
subdivision of the complex as a whole remains consistent.
Non-uniformity is a necessary property when analyzing complexity,
since the time complexity and hence the level of subdivision of an
input simplex may differ from one set of inputs to the
next. Considering just the complexity of the worst case execution over
all input sets would in many cases make a complexity theorem useless,
since for example, for the approximate agreement problem Aspnes and
Herlihy
\cite{AH} have shown that for any $k$ one can find a set of inputs that will
require time $k$ in the worst case.

The power of our theorem lies in its ability to allow one to reason
about the complexity of problems in a purely topological setting. As
we show, the subdivisions of a complex are a clean and higher level
way of thinking about the multitude of different length executions of
a concurrent protocol. We found this topological representation
helpful and are sure that it will prove to be an invaluable tool for
designing and analyzing concurrent algorithms.

%As we show in Sections~\ref{section: approximate agreement}
%and \ref{section: renaming}, w
%Borowski and Gafni recently provided a simulation of atomic snapshot
%memory from iterated immediate snapshot memory \cite{BGSIMM}, that
%provides a simple alternative to the lower bound part of the proof of
%Herlihy and Shavit's asynchronous computability theorem
%\cite{HS93,HS94}. Since non-uniform subdivisions are a generalization of 
%standard chromatic subdivions, the proof of our main theorem is the first published 
%proof 

We provide two example applications of our theorem. In
Section~\ref{section: approximate agreement} we show tight upper and
lower bounds on the time to achieve $N$ process approximate
agreement. The best known results, due to Aspnes and Herlihy
\cite{AH}, imply an $O(\log_2 N)$ upper bound and an $\Omega(\log_3
N)$ lower bound %for approximate agreement in our model of
computation, which will be specified in Section ~\ref{section: The
Iterated Immediate Snapshot Model}.  We close this gap, proving
matching upper and lower bounds of $\floor{\log_d
\frac{input-range}{\epsilon}}$ where $d=3$ for two processes and $d=2$
for 3 or more.
%Since 
%any lower bound in the IIS model is a lower bound in the MRMW model
% \cite{HLS97}, our results refine and improve the 
%$\Omega(\log_2 \frac{\mbox{\it input-range\/}}{\epsilon})$ lower bound of 
%Schenk \cite{schenk} which applied only to single bit
%MRMW registers.  


Our second result, in Section~\ref{section: renaming}, is the first
upper bound result for the $N$-process renaming problem
\cite{Renaming} of Attiya et. al that provides a
tradeoff between the number of available names and the time
complexity.  We show that there exists an algorithm in the NIIS model
with time complexity $\mbox{\it time\/}(N)$ and number of names
$\mbox{\it names\/}(N)$ if:
$$
\frac{N(N+1)}{2} - \overset{\mbox{\it time\/}(N)}{\underset{i=2}{
\sum} N-i} \leq
\mbox{\it names\/}(N) < \frac{N(N+1)}{2} - \overset{\mbox{\it time\/}(N)-1}{\underset{i=2}{
\sum} N-i}
$$
\noindent where 
$$2N-1 \leq \mbox{\it names\/}(N) \leq N(N+1)/2 $$
\noindent and 
$$1 \leq \mbox{\it time\/}(N) \leq N-1.$$ This formula quantifies an
interesting arithmetic relationship between the number of names and
the computation time used by a protocol solving $N$ process
renaming. It conforms with the $2N-1 \leq
\mbox{\it names\/}(N)$ lower bound due to Herlihy and Shavit
\cite{HS95} and extends the $\mbox{\it time\/}(N) = N$ upper bound of
Borowsky and Gafni
\cite{BorowskyGafniPODC} using $2N-1$ names. Table \ref{table: one}
shows several examples of how the time complexity and number of names
vary for different values of $N$ based on our formula.  We derive the
class of algorithms implied by the formula and their proofs in a
purely geometric way \footnote{We believe the upper bound formula is
tight, and are currently working on a matching lower bound.}.

Our formula implies a $\mbox{\it time\/}(N) = 1$ 
algorithm when $\mbox{\it names\/}(N) = N(N+1)/2 $. Though optimal in our model, this
falls short of the $O(N)$
bound of Anderson and Moir  \cite{AndersonM} in the Multi-reader Single-writer register model (MRSW)
\cite{L86b},
since known implementations of IIS from MRSW take
$\Theta(N^2)$ time. 

\begin{table}
\begin{center}
\begin{tabular}{||l||r|r|r|r|r||} 
\hline
 time= &1 & 2 & 3 & 4 & 5\\
\hline 
 N=2 & 3 & 3 & 3 & 3 & 3\\
 N=3 & 6 & 5 & 5 & 5 & 5\\
N=4 & 10 & 8 & 7 & 7 & 7\\
 N=5 & 15 & 12 & 10 & 9 & 9\\
\hline
\end{tabular}
\end{center}
\caption{Number of names of solution as a function of N and %and     
time.}
\label{table: one}
\end{table}


Since we must introduce quite a bit of mathematical machinery in order
to present our main theorem, we start out by describing 
it on an intuitive
level.
\subsection{A Bit of Intuition}
It is perhaps best to explain our theorem by way of a simple example.
Consider any comparison-based protocol solving the two-process version
of the renaming problem with 3 names. The left hand side of
Figure~\ref{Fig2} describes the input and output complexes. Recall
that the name space of processes is very large, that is, the input
complex contains many vertices corresponding to many possible process
names. However, since this is a comparison-based protocol, they can be
represented by two vertices $p$ and $q$ and two edges (1-simplices)
between them representing the case where $p>q$ and the case where
$p<q$. The output complex is a cycle of 1-simplices the describes all
the possible combinations of legal output values in two-process
executions of renaming with three output names.

Our complexity theorem says that the complexity of any protocol
solving the renaming problem in the NIIS model is exactly the number
of non-uniform chromatic subdivisions necessary to allow a simplicial
map
\footnote{Meeting the problem restrictions -- i.e. the map must be
symmetric for all cases where processes have the same relative id
order.} from the subdivided input complex to the output complex. And
indeed a single subdivision will allow such a map as depicted on the
right hand side.  Hence this problem is solvable in the NIIS model in
exactly one step by each process.

As will be shown in great detail later, the idea is that the added
nodes of the subdivision actually capture the possible different
executions that may result from processes accessing an IS object.
This can be seen in the labeling of the vertices that correspond to whether 
they saw the other process in the view returned from the IS object.
The implied symmetric protocol appears in the middle of Figure~\ref{Fig2}.

\begin{figure}[b]
%\vspace{2.5in}
\centerline{\psfig{file=fig2.eps,width=3.3in,height=1.6in}}
\caption{Two Process Renaming}
\label{Fig2}
\end{figure}

What happens when we go to three processes? Well, a single subdivision
of a 2-simplex looks like the left hand side of Figure~\ref{Fig3}.
Notice that, with 6 possible output names, we can label this complex
so that all 2-simplices are labeled with 3 different names, one for
each vertex. In general, as we show in Section~\ref{section:
renaming}, one can label a subdivided $n$-simplex corresponding to the
$N=n+1$ process executions of a protocol with $N(N+1)/2$ names. Such a
labeling corresponds to a simplicial map from the subdivided input
complex to the output complex satisfying the task requirements. By our
complexity theorem, this implies that one can solve renaming in this
case with a single IS object (one step in the NIIS model). This offers
a partial explanation for Anderson and Moir's ability to beat all
known renaming upper bounds for the case where there are $N(N+1)/2$
names
\cite{AndersonM}.

\begin{figure}[htb]
%\vspace{2.5in}
\centerline{\psfig{file=fig3.eps,width=3.3in,height=1.6in}}
\caption{Three Process Renaming with Five and Six Names}
\label{Fig3}
\end{figure}

However, if we only have $5$ names, the readers can convince themselves
that one needs to subdivide once more in order to subdivide the
2-simplex so that all subsimplices can be labeled with different names
so as to satisfy the task requirement. The right hand side of
Figure~\ref{Fig3} shows how this can be done, and is an example of a
non-uniform subdivision -- some simplices are subdivided more than
others \footnote{One could also in this case provide a
uniform/canonical chromatic subdivision, but it would be significantly
more complicated and the implied algorithm would have all processes
take the two steps.}  This figure implies that with 5 names the time
complexity of solving 3 process renaming is two. As with the two
process case, the various ``stacked'' subdivided 2-simplexes in the
figure correspond to the many possible input simplexes with different
orders among the processes. The subdivision completely describes the
solution algorithm \footnote{We choose in Figure~\ref{fig: alg three
processes} to make the unique process be the one with highest id, but
it could just as well be the one with smallest id or any other such
quantification based only on comparison of ids.},  which is presented
in Figure~\ref{fig: alg three processes}.  Extending this reasoning to
higher dimensions allows us to derive our upper bound formula.

Finally, consider the approximate agreement problem, which we discuss
in detail in Section~\ref{section: approximate agreement}.  We are
able to explain and close the upper/lower bound gap implied by Aspnes
and Herlihy's approximate agreement work \cite{AH}.  Consider
Figure~\ref{Fig4}, which shows the subdivisions induced by a three
process approximate agreement protocol on some given input set.
Aspnes and Herlihy derive their lower bound for any $N$ process
algorithm from a ``bad'' execution in which only the two processes
with inputs farthest apart participate.  Such an execution in the
figure corresponds to a sequence of subdivisions of the edge between
$P$ and $Q$. Since each subdivision introduces two new vertices and
splits the edge in three, one can only get a $\log_3$ bound in this
way.  However, note that if one considers three processes, a 2-simplex
rather than just an edge must be subdivided, and as we show, no matter
how one subdivides it, there will always be a path between $P$ and $Q$
that includes vertices of $R$ (marked by a darker color in the figure)
that will be cut by at most a half in each subdivision, implying a
tight $\log_2$ lower bound.





