%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                 Chapter 3: Asynchronous Complexity theorem               %
%                           Created: 4/13/97                               %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The Asynchronous Complexity Theorem}
\label{section: The Asynchronous Complexity Theorem}

The strength and usefulness of the NIIS model of computation comes
from the fact that each of its associated protocol complexes has a
nice, recursive structure. In fact, it turns out that any protocol
complex of NIIS is equal to some non-uniform iterated chromatic
subdivision of the input complex, and vice versa. This is the essence
of our main theorem, which we state and prove in this section.
 
The level of subdivision necessary for the existence of a simplicial
map from the input to the ouput complex of a decision task that agrees
with the task specification can be interpreted as a topological
measure of the task's time complexity. The following definition
introduces the concept of {\em mapability}, which is a useful
construct for reasoning about this topological measure.

\begin{definition}
\label{definition: mapable}
Given a decision task $\dtask$ and a non-negative integer $k$, we say
that $\wx^k(\cI)$ is a {\em mapable} subdivision of the input complex,
and $k$ is a {\em mapable} level of subdivision if there exists some
chromatic simplicial map $\mu$ from $\wx^k(\cI)$ to $\cO$ such that
for all $T$ in $\wx^k(\cI)$, $\mu(T) \in \Gamma(T)$.
\end{definition}

This definition extends naturally to individual simplexes as the map
induces different levels of subdivision on the individual simplexes in
accordance with the idea that, in order to solve a decision task, some
processes may have to do more computational work than others, and some
inputs may require more computation than others. We can now state our
main theorem:

\begin{theorem}[Time Complexity]
\label{thm: ACT}
\label{thm: main}
A decision task $\dtask$ has a wait-free protocol in the NIIS model
with worst case time complexity $k_S$ on inputs in $S$, where $S$ is a
simplex in $\cI$, if and only if there is a mapable non-uniform
iterated chromatic subdivision $\wx^k({\cal I}^n)$ with level $k_S$ on
$S$.
\end{theorem}

Keeping in style with Herlihy and Shavit \cite{HS93, HS94}, the theorem
simply states that solvability of a decision task $\dtask$ in the IIS
model is equivalent to the existence of a chromatic simplicial map
$\mu$ from some non-uniform chromatic subdivision
$\wx^k({\cal I})$ to ${\cal O}$ that agrees with the task
specification $\Gamma$, that is, for all $T$ in $\wx^k({\cal I})$,
$\mu(T^m) \in \Gamma(T)$. The level $k_S$ is a lower bound on
the worst case time complexity of solving this task with inputs in
$S$ in the IIS model.

The theorem also immediately provides a matching upper bound given the
subdivision and simplicial mapping. Simply run the normal form
protocol of Figure~\ref{fig: NIISprotocol}. Since each process can
locally store the subdivision and mapping, the termination predicate
vmap $\tau$ just needs to test if the \ls variable is equal to some
node $v$ in the subdivison and if so return $\mu(v)$.

In the remainder of this section, we will give a proof of our
asynchronous time complexity theorem. We first state and prove a lemma
about the protocol complex of a protocol in the IIS model with only
one available IS object, which we call the {\em 1-Shot IS model}.

\begin{lemma}
\label{lemma: protocol complex of level 1 IS}
Let $\cA$ be an input complex in the 1-Shot IS model. The
corresponding protocol complex is isomorphic to $\cX(\cA)$.
\end{lemma}

\begin{proof}
We will construct an isomorphism $\Psi$ from the abstract complex
$\P(\cA)$ to the abstract complex (vertex scheme) $\cX(A)$. Let $\vv =
\ang{i, S_i}$ be any vertex in $\P(\cA)$. Then $\Psi(\vv) = \ang{i,
T_i}$, where $T_i$ is the simplex in $\cA$ such that for all $j$,
$S_i[j] = v_j$ if and only if $\ang{j, v_j} \in T_i$. Notice that this
isomorphism is chromatic, that is, the id of a vertex equals the id of
its image under $\Psi$.

We must show that a set of vertexes $\vv_0, \ldots, \vv_m$ in
$skel^0(\P(\cA))$, where $m \leq n$, form a simplex in $\P(\cA)$ if
and only if the set of vertexes $\Psi(\vv_0), \ldots, \Psi(\vv_m)$ in
$skel^0(\cX(\cA))$ form a simplex in $\cX(\cA)$. Suppose without loss
of generality that for all $i$, where $0 \leq i \leq m$, $\vv_i =
\ang{i, S_i}$, where $S_i \in \vartheta(D_I)$, and $D_I$ is the input
data type (that is, the id of the $i$-th vertex is $i$).

Suppose that the vertexes $\vv_0, \ldots, \vv_m$ do form a simplex $V$
in in $\P(\cA)$. This output simplex corresponds to some execution
$\alpha$ in the 1-shot IS model, with corresponding input simplex $U$
in $\cA$. Each vertex in $U$ is labeled with a process id $i$ and an
input value $v_i \in D_I$. Notice that $\dim(V) \leq \dim(U)$, since
some participating processes may not decide, that is, they may fail
before executing a \finish action.

From Lemma~\ref{lemma: IS self-containment}, we have that, for any
vertex $\vv_i = \ang{i, S_i}$ in $V$, $S_i[i] = v_i$. This implies
that $\ang{i, v_i}$ is in $T_i$.  From Lemma~\ref{lemma: IS snapshot},
we have that, for any two vertexes $\vv_i = \ang{i, S_i}$ and $\vv_j =
\ang{j, S_j}$ in $V$, either $S_i$ is a prefix of $S_j$ or vice
cersa. Suppose without loss of generality that $S_j$ is a prefix of
$S_i$. Then for all $x$, where $0 \leq x \leq n$, if $S_i[x] = \bot$,
then $S_j[x] = \bot$, and if $S_j[x] \neq \bot$< then $S_i[x] =
S_j[x]$. It follows that if $\ang{x, v_x}$ is in $T_j$ it is also in
$T_i$, and if $x$ is not in $\ids(T_i)$, then it is also not in
$\ids(T_j)$ This implies that $T_j$ is a face of $T_i$.  From
Lemma~\ref{lemma: IS immediacy}, it follows that, if $S_i[j] = v_j$,
then $S_j$ is a prefix of $S_i$. This means that, if $\ang{j, v_j}$ is
in $T_i$, then $T_j$ is a face of $T_i$.

Now suppose that the vertexes $\Psi(\vv_0), \ldots, \Psi(\vv_m)$ in
$skel^0(\cX(\cA))$ form a simplex $V$ in $\cX(\cA)$. We will construct
an execution $\alpha$ with corresponding output simplex $U$ such that
$\Psi(U) = V$. Let $W = carrier(V)$.  Partition the set $\ids(V)$
into a collection of nonempty {\em concurrency classes} of process
ids, $\cC_1$, $\ldots$, $\cC_k$ for some $k \ge 0$, such that any two
process indices $i, j$ are in the same concurrency class if and only
if $T_i = T_j$.

We can define a total order $\prec$ on this collection of concurrency
classes as follows.  Let $\cC_x, \cC_y$ be distinct concurrency
classes.  Then $\cC_x \cap \cC_y = \emptyset$.  Since both classes are
nonempty, we can pick an element from each, say $i \in \cC_x$ and $j
\in \cC_y$. By assumption, $T_i \neq T_j$.  Then be 
Lemma~\ref{lemma: standard X 2}, either $T_i$ is a face of $T_j$ or
$T_j$ is a face of $T_i$. In the first case, let $\cC_x \prec \cC_y$,
and in the second case, let $\cC_y \prec \cC_x$. The faces of a
simplex are totally ordered, and hence $\prec$ is a total order of the
concurrency classes.

Now use this ordered partition of the participating processes in
$\alpha$ to define a second partition $\cC'_1, \ldots, \cC'_k$ of
the set $\ids(W)$ as follows. For each concurrency class $\cC$ of
$\ids(V)$, define a concurrency class $\cC'$ of $\ids(W)$ as
follows. $\cC'$ is the union of $\cC$ and all $i \in
\ids(W)-\ids(V)$ such that $\cC$ is the least concurrency class (as
determined by $\prec$) such that for all $j \in \cC$, $i \in
T_j$. Note that this is a partition of all of $\ids(W)$ since $W =
carrier(S)$. This partition gives us a new collection of concurrency
classes $\cC'_1$, $\ldots$, $\cC'_k$.

We are now ready to construct $\alpha$. First position
$update_{\cC'_i}$ actions in increasing order according to the $\prec$
ordering. For each concurrency class $\cC'_x$, position the
{\mbox{{\it inv\_writeread($v$)$_{i,IS_1}$ \/}}} actions of all $i$
such that $i \in \cC_x$ immediately before the $update_{\cC'_x}$
action (their internal ordering does not matter).  Similarly, position
the {\mbox{{\it ret\_writeread($v$)$_{i,IS_1}$ \/}}} actions of all
$i$ such that $i \in \cC_x$ and $i \in \ids(V)$ immediately after the
$update_{\cC'_x}$ action, but before the {\mbox{{\it
inv\_writeread($v$)$_{i,IS_1}$ \/}}} actions associated with the next
concurrency class $\cC_j'$. Processes $i$ whose index is not in
$\ids(W)$ do not participate and hence take no steps in
$\alpha$. Processes $i$ whose index is not in $\ids(V)$ do not execute
a {\mbox{{\it ret\_writeread($v$)$_{i,IS_1}$ \/}}}action.  By
construction, each deciding process $i$ decides $S_i$ in $\alpha$, as
required. The lemma follows.
\end{proof}  

We now consider the protocol complex of a protocol in NIIS with time
complexity $1$ on the input complex $\cI$.

\begin{lemma}
\label{lemma: protocol complex of level 1 NIIS}
The protocol complex $\P(\cI)$ of any NIIS protocol of time complexity
$1$ with input complex $\cI$ is equal to some non-uniform chromatic
subdivision $\wx^1(\cI)$.
\end{lemma}

\begin{proof}
We will show how to construct the protocol complex $\P(\cI)$, and
prove this construction is in accordance with Definition~\ref{def:
non-uniform X}.

Consider any vertex $\vv$ in $\cI$. It is labeled with $\ang{i,v_i}$,
where $i$ is a process id and $v_i$ represents an input value to
process $i$. According to the specification of NIIS protocols in
Section~\ref{section: NIIS}, process $i$ will (provided it does not
fail), upon having received the input $v_i$, either execute an action
{\mbox{{\it inv\_writeread($v$)$_{i,IS_1}$ \/}}} or \finishi, depending on whether $\tau$(\ls) evaluates to true
or not. In this way, the predicate map $\tau$ induces a partition of
the vertexes of $\cI$ into two disjoint sets $A$ and $B$. Since the
time complexity of $\P$ on any input simplex in $\cI$ is $1$, the set
$A$ must be nonempty. We now construct complexes $\cA$ and $\cB$ as in
Definition~\ref{def: non-uniform X}, that is, a simplex $T$ in $\cI$
is in $\cA$ if and only if all its vertexes are in $A$, and it is in
$\cB$ if and only if all its vertexes are in $B$.

The vertexes in $A$ correspond to processes that, based on their input
values, execute an {\mbox{{\it inv\_writeread($v$)$_{i,IS_1}$ \/}}}
action with the object $IS_1$. By Lemma~\ref{lemma: protocol complex
of level 1 IS}, the protocol complex $\P(\cA)$ equals $\cX(\cA)$. A
simplex $U$ is in $\P(\cI)$ if and only if it corresponds to an output
vector of an execution $\alpha$ of the protocol. In any execution
$\alpha$ of the protocol, some of the participating, non-failing
processes decide on their input values (corresponding to vertexes in
$B$), while some decide on the snapshots they receive from the object
$IS_1$ (corresponding to vertexes in $\P(\cA)$).  It follows that
$\P(\cI)$ contains any simplex in $\cB$, any simplex in $\P(\cA) =
\cX(\cA)$, and any simplex of the form $S \star T$, where $S$ is in
$\cX(\cA)$, $T$ is in $\cB$, and $\carrier(S)\star T$ is in $\cI$. The
lemma follows.
\end{proof}

\begin{lemma}
For all $k>0$, the protocol complex $\P(\cI)$ of any protocol in the
NIIS model with time complexity $k$ on inputs in $\cI$ is equal to
some non-uniform chromatic subdivision $\wx^k(\cI)$.
\end{lemma}
 
\begin{proof}
We use induction on the time complexity $k$. By Lemma~\ref{lemma:
protocol complex of level 1 NIIS}, the result holds for $k=1$. Now
suppose $k>1$, and that the result holds for $1, \ldots,
k-1$. Consider the protocol complex $\P(\cI)$ of any protocol in the
NIIS model with time complexity $k$ on inputs in $\cI$. 

Any vertex $\vv$ in $\cI$ is labeled with $\ang{i,v_i}$, where $i$ is
a process id and $v_i$ represents an input value to process
$i$. According to the specification of NIIS protocols in
Section~\ref{section: NIIS}, process $i$ will, upon having received
the input $v_i$, either execute an action {\mbox{{\it
inv\_writeread($v$)$_{i,IS_1}$ \/}}} or \finishi, depending on whether
$\tau(v_i)$ evaluates to true or not. In this way, the predicate map
$\tau$ induces a partition of the vertexes of $\cI$ into two disjoint
sets $A$ and $B$. Since the time complexity of $\P$ on inputs in $\cI$
is $k$, the set $A$ must be nonempty. We now construct complexes $\cA$
and $\cB$ as in Definition~\ref{def: non-uniform X}, that is, a
simplex $T$ in $\cI$ is in $\cA$ iff all its vertexes are in $A$, and
it is in $\cB$ iff all its vertexes are in $B$.

The vertexes in $A$ correspond to processes that, based on their input
values, execute an {\mbox{{\it inv\_writeread($v$)$_{i,IS_1}$
\/}}}action with the object $IS_1$. By Lemma~\ref{lemma: protocol
complex of level 1 IS}, the output protocol complex on inputs in $\cA$
after the first IS access equals $\cX(\cA)$. The final protocol
complex $\P(\cA)$ is given by applying $\cX(\cA)$ as an input complex
to the Protocol. Since the complexity of the protocol on inputs in
$\cI$, and hence on inputs in $\cA$, is $k$, the complexity of the
protocol on inputs in $\cX(\cA)$ must be $k-1$. It follows by
induction that the protocol complex $\P(\cA)$ equals some non-uniform
chromatic subdivision $\wx^{k-1}(\cX(\cA))$ of $\cX(\cA)$.  A simplex
$U$ is in $\P(\cI)$ iff it corresponds to a valid set of outputs of an
execution $\alpha$ of the protocol. In any execution $\alpha$ of the
protocol, some of the participating, non-failing processes decide on
their input values, while some decide on the snapshots they receive
from some IS object.  It follows that $\P(\cI)$ contains any simplex
in $\cB$, and simplex in $\P(\cA) =
\wx^{k-1}(\cX(\cA))$, and any simplex of the form $S \star T$, where $S$ is in
$\wx^{k-1}(\cX(\cA))$, $T$ is in $\cB$, and $\carrier(S)\star T$ is in
$\cI$. It follows from Definition~\ref{def: non-uniform X} that the
protocol complex $\P(\cI)$ equals some non-uniform chromatic
subdivision $\wx^k(\cI)$ of $\cI$.
\end {proof}

We must also prove that, for any non-uniform chromatic subdivision
$\wx^k(\cI)$ of an input complex $\cI$, there is a matching protocol
$\P$ in the NIIS model.

\begin{lemma}
For any non-uniform chromatic subdivision $\wx^k(\cI)$ of an input
complex $\cI$, there is a matching protocol $\P$ in the NIIS model
such that the protocol complex $\P(\cI) = \wx^k(\cI)$.
\end{lemma}

\begin{proof}
Given a vertex $\vv$ in $\cI$. The definition of the subdivision
$\wx^k(\cI)$ induces a sequence of non-uniform chromatic subdivisions
$\cI, \wx^1(\cI), \ldots, \wx^k(\cI)$, and corresponding sequences
$\cA_0, \ldots, \cA_{k-1}$ and $\cB_0, \ldots, \cB_{k-1}$ of
complexes, the former sequence specifying the subcomplex to be
subdivided further at each level of recursion. 

In order to construct a protocol for $n+1$ processes, we must specify
the function $\tau: \bigcup_{l = 0}^k \vartheta^l(D) \rightarrow
\{{\tt true, false}\}$.  We specify $\tau$ to be {\tt true} for all 
values $v$ such that there is a vertex $\vv$ in one of the complexes
$\cA_0, \ldots, \cA_{k-1}$ with $\val(\vv) = v$, and $\tau$ to be {\tt
false} for all values $v$ such that there is a vertex $\vv$ in one of
the complexes $\cB_0, \ldots, \cB_{k-1}$ with $\val(\vv) = v$. For all
other values $v$, $\tau$ evaluates to {\tt false}. This definition is
well-formed, since for all $p$, where $0 \leq p \leq k$, it follows
from Definition~\ref{def: standard X} and Definition~\ref{def:
non-uniform X} that there are no two vertexes in $\wx^p(\cI)$ with the
same process-value label pair, and for all $p,q$, where $0 \leq p,q
\leq k$ and $p \neq q$, $\cB_p$ and $\cB_q$ have no vertexes with common 
labels (process id {\em and} value label).
\end{proof}

We now give the proof of Theorem~\ref{thm: main}.

\begin{proof}(Of Theorem~\ref{thm: main})
  Given a decision task $\dtask$.  It follows immediately from the
  previous lemma that any non-uniform protocol complex $\cP^k$ with
  worst case complexity $k_{S}$ on input $S$ and decision map
  $\delta: \cP^k \rightarrow \cO^n$ that agrees with $\Gamma$
  corresponds to a non-uniform chromatic subdivision
  $\wx^k(\cI^n)$ with level $k_{S}$ on $S$ together with a
  simplicial map $\mu: \wx^k(\cI^n) \rightarrow \cO^n$ that agrees
  with $\Gamma$, and vice versa. The theorem follows. 
\end{proof}



