%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                 Chapter 2: Topological Framework                         %
%                           Created: 4/6/97                                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{A Topological Framework}
\label{section: math}
In this section we first introduce some known tools from the field of
algebraic topology and show how they may be used to model decision
tasks and protocols in the NIIS model of computation. We then
introduce a new tool for analyzing complexity in this setting, called
the non-uniform iterated chromatic subdivision.

\subsection{Basic Topological Definitions and Concepts}
\label{subsubsection: basic topology}
This subsection introduces the basic topological definitions and concepts
that we shall need for modeling decision tasks and wait-free protocols
in the NIIS model. Some of these definitions are fairly standard, and
are mainly taken from popular textbooks on algebraic topology
\cite{Munkres, Spanier}, whilst others are due to Herlihy and Shavit
\cite{HS93, HS94}. Some of the figures used in this subsection are also 
adopted from Herlihy and Shavit's work \cite{HS93, HS94}.

A {\em vertex} $\vv$ is a point in a high-dimensional Euclidian space
$R^l$.  A set $\{\vv_0, \ldots, \vv_n \}$ of vertexes is {\em
geometrically independent} if and only if the set of vectors $\{\vv_i
- \vv_0 \}_{i=1}^n$ is linearly independent. We can now define the
concept of a geometric simplex, or simplex for short.

\begin{definition}
\label{def: simplex}
Let $\{\vv_0, \ldots, \vv_n \}$ be a geometrically independent set of vertexes
in $R^l$. We define the $n$-simplex $S$ spanned by $\vv_0, \ldots, \vv_n$ to
be the set of all points $x$ such that $x = \sum_{i=0}^n t_i\vv_i$ where
$\sum_{i=0}^n t_i =1$ and $t_i \geq 0$ for all $i$.
\end{definition}

For example, a $0$-simplex is a vertex, a $1$-simplex a line segment,
a $2$-simplex a solid triangle, and a $3$-simplex a solid
tetrahedron. For an example of a $2$-simplex see Figure ~\ref{fig:
simplex}. For simplicity, we often denote the simplex spanned by a set
$\{\vv_0, \ldots, \vv_n \}$ of geometrically independent vertexes as
$(\vv_0, \ldots,\vv_n)$. The number $n$ is called the {\em dimension}
of the simplex $S$, and is often denoted by $\dim(S)$.  For clarity,
we sometimes will include the number $n$ as an explicit superscript
when referring to a simplex, that is, we will write $S^n$ to refer to
the simplex spanned by the vertexes in $\{\vv_0, \ldots,
\vv_n \}$.

Any simplex $T$ spanned by a subset of $\{\vv_0, \ldots, \vv_n \}$
is called a {\em face} of $S$.  The faces of $S$ different from
$S$ itself are called the {\em proper} faces of $S$. The simplex
spanned by the vertexes $\{\vv_0, \vv_1\}$ is a proper face of the
$2$-simplex in Figure ~\ref{fig: simplex}.

\input{simplex}

The union of the proper faces of $S$ is called the {\em boundary} of
$S$, and is denoted $Bd(S)$. The interior of $S$, denoted
$Int(S)$, is defined by the set equation $Int(S) = S - Bd(S)$.

We will use a vertex to model the state of a single process, and a
simplex to model consistent states of all the processes involved in
solving a decision task or in running a wait-free protocol. To model a
collection of such states we need the concept of a geometric,
simplicial complex, or complex for short, which is defined below.

\begin{definition}
\label{def: complex}
A geometric simplicial complex $\cK$ in the Euclidean space $R^l$ is a
collection of geometric simplexes in $R^l$ such that

\begin{itemize}
\item Every face $T$ of every simplex $S$ in $\cK$, where $\dim(T) \leq \dim(S)$,
is contained in $\cK$.
\item The intersection $U$ of any two simplexes $S$, $T$ in $K$, where
$\dim(U) \leq \dim(S),\dim(T)$, is contained in $\cK$.
\end{itemize}
\end{definition}

In this paper we will only consider finite complexes.  The {\em
dimension} of a complex $\cK$, often denoted by $\dim(\cK)$, is the
highest dimension of any of its simplexes, and is also sometimes
indicated explicitly by a superscript.  An $n$-dimensional complex (or
$n$-complex) is {\em pure} if every simplex is a face of some
$n$-simplex.  All complexes considered in this paper are pure, unless
stated otherwise. A simplex $S$ in $\cK$ with dimension $\dim(S) =
\dim(\cK)$ is called a {\em maximal} simplex.

Given a simplex $S$, let $\cS$ denote the complex of all faces of $S$,
and let $\Sdot$ denote the complex consisting of all proper faces of
$S$. We note that, since $\Sdot$ contains all faces of $S$ except $S$
itself, $\dim(\Sdot) = \dim(S) -1$. An example of a pure,
$2$-dimensional simplicial complex, which we call $\cK$, is shown in
Figure ~\ref{fig: complex}. This complex equals the union of $\Sdot$ and
$\Tdot$, where $S$ is the $2$-simplex spanned by $\{\vv_0, \vv_1,
\vv_2\}$, and $T$ is the $2$-simplex spanned by $\{\vv_0, \vv_1,
\vv_3\}$. Both $S$ and $T$ are maximal simplexes in this example.

If $\cL$ is a subcollection of $\cK$ that is closed under containment
and intersection, where $\dim(\cL) \leq \dim(\cK)$, then $\cL$ is a
complex in its own right. It is called a {\em subcomplex} of
$\cK$. For example, the complex $\Sdot$ of faces of $S$ is a
subcomplex of $\cK$ in Figure ~\ref{fig: complex}

One subcomplex of a complex $\cK$ of particular interest is the
subcomplex of all simplexes in $\cK$ of dimension at most $p$, where
$p$ is some integer between $0$ and $\dim(\cK)$. We call this
subcomplex the $p$-th {\em skeleton} of a $\cK$, denoted
$\skel^p(\cK)$. The elements of the collection $\skel^0(\cK)$ are
called the {\em vertexes} of $\cK$. The $0$-skeleton of the complex
$\cK$ in Figure ~\ref{fig: complex} is the collection of vertexes
$\{\{\vv_0\},\ldots,
\{\vv_3\}\}$. Similarly, the $1$-skeleton of $\cK$ is the union of
the $0$-skeleton described above and the collection $\{\{\vv_0,
\vv_1\}, \ldots \{\vv_0, \vv_3\}, \{\vv_1,
\vv_2\}, \{\vv_1, \vv_3\}\}$.

\input{complex}

Let $|K|$ be the subset $\bigcup_{S \in \cK} S$ of $R^l$ that is
the union of the simplexes of $\cK$. Giving each simplex its natural
topology as a subspace of $R^l$, we topologize $|\cK|$ by declaring
a subset $A$ of $|\cK|$ to be closed iff $A \cap S$ is closed for all
$S \in \cK$. This space is called the {\em polytope} of
$\cK$. Conversely, $\cK$ is called a {\em triangulation} of
$|\cK|$.

In practice, the geometric representations we have given for simplexes
and complexes are not always convenient, since the analytic geometry
involved can get quite involved. Therefore, we introduce the notions
of {\em abstract simplexes} and {\em abstract complexes}.

\begin{definition}
\label{def: abstract simplex}
An abstract simplex $S$ is a finite, nonempty set.
\end{definition}

The {\em dimension} of $S$ is its cardinality. Each nonempty subset
$T$ of $S$ is called a {\em face} of $S$. Each element of $S$ is
called a {\em vertex} of $S$. There is a close relationship between
geometric simplexes and abstract simplexes; Any geometrically
independent set of vectors $\{\vv_0, \ldots, \vv_n\}$ not only span a
geometric simplex, they also form an abstract simplex.

\begin{definition}
\label{def: abstract complex}
An abstract complex $\cK_a$ is a collection of abstract simplexes, such
that if $S$ is in $\cK_a$, so is any face of $S$.
\end{definition} 

Most concepts defined for geometric complexes immediately carry over
to abstract complexes; The {\em dimension} of $\cK_a$, often denoted
by $\dim(\cK_a)$, is the highest dimension of any of its simplexes.
An $n$-dimensional abstract complex (or $n$-complex) is {\em pure} if
every simplex is a face of some $n$-simplex. If $\cL_a$ is a
subcollection of $\cK_a$ that is itself an abstract complex, then
$\cL_a$ is called a {\em subcomplex} of $\cK_a$. 

\begin{definition}
\label{def: vertex scheme}
Let $\cK$ be a geometric complex, and let $V$ be the vertex set of
$\cK$. Let $\cK_a$ be the collection of all subsets $S$ of $V$ such
that $S$ spans a simplex in $\cK$. Then $\cK_a$ is called the {\em
vertex scheme} of $\cK$.
\end{definition}

\begin{definition}
\label{def: isomorphism}
Two abstract complexes $\cK_a$ and $\cL_a$ are {\em isomorphic} if
there is a bijective correspondence $\psi$ between their vertex sets
such that a set $S$ of vertexes is in $\cK_a$ iff $\psi(S) \in
\cL_a$. The bijective correspondense $\psi$ is called an {\em isomorphism}.
\end{definition}

\begin{theorem}
\label{thm: embedding}
Every abstract complex $\cK_a$ is isomorphic to the vertex scheme of
some geometric complex $\cK$ in $\Bbb{R}$$^{2\dim(\cK_a)+1}$.
\end{theorem}

We will not prove this theorem here. For a proof, see any standard
textbook on algebraic topology \cite{Munkres, Spanier}. In the rest of
this paper, for convenience, we will often use abstract and geometric
representations of simplexes and complexes interchangeably. The
remainder of this subsection, however, which introduces a number of
important topological concepts, such as simplicial maps, subdivisions
and carriers, is set in the context of geometric complexes.

We first define the notions of simplicial vertex maps and simplicial
maps from one complex into another.

\begin{definition}
\label{def: simplicial map}
Let $\cK$ and $\cL$ be complexes, possibly of different dimensions,
and let $\mu: \skel^0(\cK) \rightarrow \skel^0(\cL)$ be a function
mapping vertexes to vertexes. Suppose that whenever the vertexes
$\vv_0, \ldots, \vv_n$ of $\cK$ span a simplex of $\cK$, the vertexes
$\mu(\vv_0), \ldots, \mu(\vv_n)$ span a simplex of $\cL$. Then $\mu$ is
called a simplicial vertex map from $\cK$ to $\cL$. $\mu$ can be
extended to a continuous map $\mu_*: |\cK|
\rightarrow |\cL|$ such that 
\begin{displaymath}
x = \sum_{i=0}^n t_i\vv_i \Rightarrow \mu_*(x) = \sum_{i=0}^n t_i\mu_*(\vv_i)
\end{displaymath}
This continuous extension is called a simplicial map from $\cK$ to
$\cL$.
\end{definition}

For simplicity, we henceforth refer to the simplicial vertex map $\mu$
as the simplicial map, without actual reference to the continous
extension $\mu_*$, which is less relevant for our purposes. As a
further abuse of notation, we usually write $\mu: \cK \rightarrow
\cL$ when we refer to the simplicial vertex map, glossing over the fact that this
map is in fact only defined on the vertexes of $\cK$, and that the
image of the map is a subset of the vertex set of $\cL$. Henceforth,
unless stated otherwise, all maps between complexes are assumed to be
simplicial. An example of a simplicial map is given in Figure
~\ref{fig: simplicial}

We note that a simplex and its image under a simplicial map need not
have the same dimension. A simplicial map $\mu: \cK \rightarrow \cL$
is {\em non-collapsing} if it preserves dimension, that is, for all $S
\in \cK$: $\dim(\mu(S)) =\dim(S)$. 

% Two complexes $\cK$ and $\cL$ are
%{\em isomorphic} if there exist simplicial maps $\mu: \cK \rightarrow
%\cL$ and $\mu': \cL \rightarrow \cK$, called  {\em isomorphisms}, such 
%that $\mu \cdot \mu'$ and $\mu' \cdot \mu$ are identity maps. This definition is e%qui

\input{simplicial}

\begin{definition}
\label{def: coloring}
A {\em coloring} of an $n$-dimensional complex $\cK$ is a
non-collapsing simplicial map $\chi: \cK \rightarrow \cS$, where
$S$ is an $n$-simplex.
\end{definition}

Intuitively, a coloring corresponds to a labeling of the vertexes of
the complex such that no two neighbouring vertexes (connected by a
$1$-simplex) have the same label. A {\em chromatic complex} $(\cK,
\chi)$ is a complex $\cK$ together with a coloring $\chi$ of $\cK$.
An example of a chromatic complex is given in Figure ~\ref{fig:
chromaticcomplex}, where the colors are the values $\{1,2,3\}$. When
it is clear from the context, we specify the chromatic complex $(\cK,
\chi)$ simply as the complex $\cK$, omitting explicit mention of the
coloring $\chi$.

Let $(\cK,\chi_{\cK})$ and $(\cL,\chi_{\cL})$ be chromatic complexes,
and let $\mu: \cK \rightarrow \cL$ be a simplicial map. We say that
$\mu$ is {\em chromatic} if, for every vertex $\vv \in \cK$,
$\chi_{\cK}(\vv) = \chi_{\cL}(\mu(\vv))$, that is, if $\mu$ maps each
vertex in $\cK$ to a vertex in $\cL$ of the same color.  All the
simplicial maps we consider in this paper are chromatic.

We can now define the concepts of a {\em subdivision} of a
complex, and the {\em carrier} of a simplex in a subdivision.

\input{chromaticcomplex}

\begin{definition}
\label{def: subdivision}
Let $\cK$ be a complex in $R^l$. A complex $\sigma(\cK)$ is said to be a {\em
subdivision} of $\cK$ if the following two conditions hold:

\begin{itemize}
\item Each simplex in $\sigma(\cK)$ is contained in a simplex in $\cK$.
\item Each simplex of $\cK$ equals the union of finitely many simplexes in
$\sigma(\cK)$.
\end{itemize}
\end{definition}
 
An example of a complex and its subdivision is given in Figure
~\ref{fig: subdivision}.

\input{subdivision}

\begin{definition}
\label{def: carrier}
If $S$ is a simplex of $\sigma(\cK)$, the {\em carrier} of $S$,
denoted $\carrier(S)$ is the unique smallest $T \in \cK$ such that $S
\subset |T|$.
\end{definition}

The concept of a carrier of a simplex is illustrated in Figure
\ref{fig: carrier}. The original complex is shown on the right, and 
the subdivided complex is shown on the left.  A simplex $S$ in the
subdivision and the corresponding carrier $carrier(S)$ in the original
complex are highlighted in the figure.

\begin{figure}[htbp]
\centerline{\psfig{figure=carrier.ps,height=2.0in}}
\caption{The Carrier of a Simplex}
\label{fig: carrier}
\end{figure}

A {\em chromatic subdivision} of $(\cK,\chi_{\cK})$ is a chromatic
complex $\sigma(\cK),\chi_{\sigma(\cK)})$ such that $\sigma(\cK)$ is a
subdivision of $\cK$, and for all $S$ in $\sigma(\cK)$,
$\chi_{\sigma(\cK)}(S)
\subseteq \chi_{\cK}(\carrier(S))$.  A simplicial map $\mu: \sigma_1(\cK)
\rightarrow \sigma_2(\cK)$ between chromatic subdivisions of $\cK$ is {\em
carrier preserving} if for all $S \in \sigma_1(\cK)$, $\carrier(S) =
\carrier(\mu(S))$. All subdivisions we consider in this paper will
be chromatic, unless explicitly stated otherwise.

\subsection{Topological Modeling of Decision Tasks}
\label{subsection: topological modeling of decision tasks}
Earlier in this subsection, we defined the notion of a decision task in
terms of input and output vectors.  That definition was intended to
help the reader understand what a decision task is, but it lacks the
mathematical structure necessary to prove interesting results.  We now
reformulate this definition in terms of simplicial complexes.

To illustrate our constructions, we will use the well-known Unique-Id
task as an informal example. We will give a formal, topological
definition of decision tasks later. The Unique-Id task was introduced
earlier, but we restate it here for convenience.

\begin{example}
The $n+1$-process Unique-Id task is defined as follows:
\begin{itemize}
\item $I = \{[0, \ldots, n]\}$.
\item $O = \{[x_1, \ldots, x_n] \mid \forall i,j: x_i \in \Bbb(Z)$$_{n+1} \cup
\{\bot\} \wedge (x_i = x_j) \Rightarrow (x_i = \bot)\}$.
\item $\forall \vI \in I: \vO \in \gamma(\vI)$ iff for all $i,j$, $(\vO[i] = \vO[j]) \Rightarrow (\vO[i] = \bot)$.
\end{itemize}
\end{example}

We represent the (unique) $n+1$-dimensional input vector $\vI = [0,
\ldots, n]$ to the Unique-Id task as a simplex $S$, called an {\em
input simplex}, with dimension $0 \leq \dim(S) \leq n$. The dimension
of $S$ equals the number of non-$\bot$ elements in the vector. Each
vertex $\vv$ in $S$ is labeled with a process id and an input value:
$\ang{i,v_i}$, where $\vI[i]=v_i$. We use $\ids(S)$ to denote the
simplex's set of process ids, and $\vals(S)$ to denote the multiset of
values.  If $\vJ$ is a prefix of $\vI$, then the simplex corresponding
to $\vJ$ is a face of $S$. The set $I$ of input vectors is thus
modeled as a complex $\cI$ of input simplexes, called the {\em input
complex}.

Similarly, we represent each $n+1$-dimensional output vector $\vO =
[x_1, \ldots, x_n]$, where for all $i, j$, either $x_i=\bot$ or $0
\leq x_i \leq n$ and $(x_i=x_j) \Rightarrow (x_i = \bot)$, as a
simplex $T$, called an {\em output simplex}, with dimension $0 \leq
\dim(T) \leq n$. Each vertex $\vv$ in $T$ is labeled with a process id
and an output value: $\ang{i,v_i}$, where $\vO[i]=v_i$. We use
$\ids(T)$ to denote the simplex's set of process ids, and $\vals(T)$
to denote the multiset of values.  If $\vP$ is a prefix of $\vO$, then
the simplex corresponding to $\vP$ is a face of $T$. The set $O$ of
input vectors is thus modeled as a complex $\cO$ of output simplexes,
called the {\em output complex}.

The task specification map $\gamma$ induces a {\em topological task
specificatin map} $\Gamma$ for the Unique-Id task in the natural way,
mapping each input simplex $S \in \cI$ to a set $\Gamma(S)$ of output
simplexes in $\cO$, with the property that for all $T \in \Gamma(S)$,
the set $\vals(T)$ contains no non-$\bot$ duplicates.

We can now give an alternative, topological representation of the
Unique-Id decision task by simply specifying it as a tuple $\dtask$
consisting of an input complex $\cI$, and output complex $\cO$, and a
topological task specification map, $\Gamma$.

Figure~\ref{fig: unique-id} shows two triangles ($2$-simplexes) corresponding
to two distinct outputs for the $3$-process Unique-Id task, one given by
the output vector $\vO_1 = [0,1,2]$, the other given by the output
vector $\vO_2 = [3,1,2]$. Notice that the vertexes of each simplex are
colored by the appropriate process ids.

This topological representation gives an alternative interpretation of
the notion of ``similar'' system states.  The processes corresponding
to vertexes on the common boundary of the two simplexes cannot
distinguish between the two global output sets based on their own
output values.  Unlike graph-theoretic models (e.g.,
\cite{BMZ}), simplicial complexes capture in a natural way the notion
of the {\em degree} of similarity between the two global output sets:
it is the dimension of the intersection of the two $2$-simplexes.

\input{unique-id}

%\begin{figure}[htbp]
%\centerline{\psfig{figure=uniqueid.ps,height=2.0in}}
%\vspace{0.25in}
%\caption{A piece of the output complex in the $3$-process Unique-Id task.}
%\label{figure: unique-id}
%\end{figure}
%
%We represent the set of all compatible sets of initial or final states
%for a decision task as a chromatic complex colored by process ids.
%For example, Figure \ref{figure: renaming} shows the output complex
%for the three-process renaming task using four names.  Note that the
%output complex's polyhedron is homeomorphic (topologically equivalent)
%to a torus.  To see why, notice that the vertexes on edges of the
%complex are the same, so the edges can be ``glued together'' in the
%direction of the arrows.
%
%\begin{figure}[htbp]
%\centerline{\psfig{figure=torus.ps,width=6.0in}}
%\caption{Output Complex for 3-Process Renaming with 4 Names}
%\label{figure: renaming}
%\end{figure}

We now give a formal procedure for how to specify a given decision
task $\dt2$ topologically. We first construct a representation using
abstract simplexes and complexes, and then use Theorem~\ref{thm:
embedding} to construct a representation using geometric simplexes and
complexes.

\begin{definition}
\label{def: input simplex}
Let $\vI \in I$ be an input vector. The {\em input simplex}
corresponding to $\vI$, denoted $S(\vI)$, is the abstract simplex
$(\ang{i_0, v_{i_0}}, \ldots, \ang{i_m, v_{i_m}})$, where for all
$i_j$, where $i_0 \leq i_j \leq i_m$, $i_j \in \{0, \ldots, n\} \wedge
\vI[i_j] \neq \bot$, and for all $i$, 
$(\vI[i] = \bot) \Rightarrow (i \not \in \{i_0, \ldots, i_m\})$.
\end{definition}

\begin{definition}
\label{def: output simplex}
Let $\vO \in O$ be an output vector. The {\em output simplex}
corresponding to $\vO$, denoted $T(\vO)$, is the abstract simplex
$(\ang{i_0, v_{i_1}}, \ldots, \ang{i_m, v_{i_m}})$, where for all
$i_j$, where $i_0 \leq i_j \leq i_m$, $i_j \in \{0, \ldots, n\} \wedge
\vO[i_j] \neq \bot$, and for all $i$, 
$(\vO[i] = \bot) \Rightarrow (i \not \in \{i_0, \ldots, i_m\})$.
\end{definition}

Having defined input and output simplexes, we can define
input and output complexes.

\begin{definition}
\label{def: input complex}
The {\em input complex} corresponding to $I$, denoted $\cI$,
is the collection of input simplices $S(\vI)$ corresponding to the
input vectors of $I$.
\end{definition}

\begin{definition}
\label{def: output complex}
The {\em output complex} corresponding to $O$, denoted $\cO$,
is the collection of output simplices $T(\vO)$ corresponding to the
output vectors of $O$.
\end{definition}

We have to prove that these definitions make sense topologically, that
is, that the input and output complexes thus defined are in fact
abstract complexes. We will do the proof for input complexes in the
lemma below. The proof relies on the requirement that the sets of
input vectors we consider are prefix-closed.

\begin{lemma}
\label{lemma: input complex}
Given a set $I$ of input vectors. The corresponding input
complex $\cI$, as defined in Definition~\ref{def: input complex}, is
an abstract, chromatic complex.
\end{lemma}

\begin{proof}
Clearly, $\cI$ as defined above is a collection of abstract
simplexes. We must show that this collection satisfies the
requirements of Definition~\ref{def: abstract complex}, that is, we
must establish that $\cI$ is closed under containment.

Let $S(\vI)=(\vs_0, \ldots, \vs_m)$ be an abstract simplex of $\cI$,
and let $T=(\vt_0, \ldots, \vt_{m'})$, where $m' \leq m$, be a face of
$S(\vI)$. It follows that $skel^0(T) \subseteq
skel^0(S(\vI))$. Consider the vector $\vJ$, the $i$-th entry of which
is $\bot$ iff $i \not \in \ids(T)$, and otherwise $\val(\vt_j)$, where
$i = \id(\vt_j)$. We claim that this vector is a prefix of
$\vI$. Suppose $\vI[i]= \bot$. Then $i \not \in \ids(S(\vI))$, and
hence $i \not \in \ids(T)$. It follows that $\vJ[i]=\bot$. Now suppose
that $vJ[i] \neq \bot$. Then there is a vertex $\vt_j$ in $T$ with
$\id(\vt_j)=i$ and $\val(\vt_j)=\vJ[i]$. Since $skel^0(T) \subseteq
skel^0(S(\vI))$, this vertex is also a vertex of $S(\vI)$, and so it
follows that $\vI[i]=\val(\vt_j)=\vJ[i]$. It follows that $\vJ$ is a
prefix of $\vI$. Since we only consider prefix-closed sets of input
vectors, $\vJ$ must be in $I$. The simplex corresponding to $\vJ$,
denoted $S(\vJ)$ is equal to $T$, and hence $T$ is in $\cI$. 

It follows that $\cI$ is an abstract complex. Moreover, let $S=
(\vs_0, \ldots, \vs_n)$ be any $n$-simplex. Then the map $\chi:\cI
\rightarrow \cS$ defined by $\chi(\vv) = \vs_i$, where $i = \id(\vv)$
is a chromatic and simplicial map from $\cI$ to $\cS$, and hence $\cI$
is a chromatic, abstract complex, as required.
\end{proof}

\begin{lemma}
\label{lemma: output complex}
Given a set $O$ of output vectors. The corresponding output
complex $\cO$, as defined in Definition~\ref{def: input complex}, is an
abstract, chromatic complex.
\end{lemma}

The proof is identical to the proof of Lemma~\ref{lemma: input
complex}, and will be omitted here. Given a pair of (abstract) input
and output complexes, we may apply Theorem~\ref{thm: embedding} to
construct a corresponding pair of geometric chromatic input and output
complexes by embedding the abstract complexes in $\Bbb{R}$$^{2n+1}$.
As discussed in Subsection~\ref{subsection: basic topology}, the abstract
and geometric representations of a complex are equivalent up to linear
isomorphism, and thus we will work with both interchangeably in the
remainder of this paper.

We now construct a topological equivalent of the task specification
map $\gamma: I \rightarrow O$.

\begin{definition}
\label{def: topological task specification}
The {\em topological task specification map} corresponding to
$\gamma$, denoted $\Gamma$, is the map carrying each simplex $S(\vI)$
of $\cI$ to a non-empty set of simplexes of $\cO$ defined as follows.

$$ T(\vO) \in \Gamma(S(\vI)) \Longleftrightarrow \vO \in \gamma(\vI)$$
\end{definition}

Usually, we simply refer to a topological task specification map as a
``task specification map''. We now prove two crucial properties of
such maps.

\begin{lemma}
\label{lemma: bot carries}
For all $S(\vI) \in \cI$, and all $i$, $i \not \in
\ids(S(\vI))$ iff for all $T(\vO) \in \Gamma(S(\vI))$, $i \not \in
\ids(T(\vO))$.
\end{lemma}

\begin{proof}
Suppose $i \not \in \ids(S(\vI))$. Then $\vI[i] =
\bot$ by Definition~\ref{def: input simplex}, and hence by 
Definition~\ref{def: task specification}, $\vO[i]=\bot$. It follows
from Definition~\ref{def: output simplex} that $i \not \in
\ids(T(\vO))$.
\end{proof}

\begin{lemma}
\label{lemma: task spec chromatic}
The map $\Gamma$ as defined above preserves process ids: for any
simplex $S$ in $\cI$, and all $T$ in $\Gamma(T)$, $\ids(T) \subseteq
\ids(S)$.
\end{lemma}

\begin{proof}
Let $S(\vI)$ be any simplex in $\cI$, and let $T(\vO) \in
\Gamma(S(\vI))$. Then $\vO \in \gamma(\vI)$. It follows from Definition 
\ref{def: task specification} that, for all $i$,  
$\vI[i]=\bot \Rightarrow \vO[i] = \bot$.  Suppose $i \in
\ids(T(\vO))$. Then $\vO[i] \neq \bot$, and hence $\vI[i] \neq
\bot$. It follows from the construction of $S(\vI)$ that $i \in
\ids(S(\vI))$. The claim follows.
\end{proof}

An illustration of a pair of input and output complexes, together with
a task specification map relating them, is given in Figure
\ref{fig: task spec}.

\begin{definition}
\label{def: decision task topological}
Given a decision task $\dt2$, the corresponding {\em topological
representation} of the task, denoted $\dtask$, consists of an input
complex $\cI$ corresponding to $I$, and output complex $\cO$
corresponding to $O$, and a task specification map $Gamma$
corresponding to $\gamma$.
\end{definition}

\begin{figure}[htbp]
\centerline{\psfig{figure=spec.ps,height=2.5in}}
\caption{A Decision Task}
\label{fig: task spec}
\end{figure}

In the remainder of this paper, we will specify decision tasks using
both Definition~\ref{def: decision task} and Definition~\ref{def:
decision task topological} interchangeably. A set of inputs or outputs
may thus be specified as either a vector or as a simplex the vertexes
of which are lebeled with process ids and values.
 
\subsection{Topological Modeling of NIIS Protocols}
\label{subsection: toplogical NIIS}
We model protocols in the NIIS model in much the same way that we
model decision tasks. As discussed in Section~\ref{section: model}, the
sets of inputs and outputs for any execution $\alpha$ of a protocol
$\P$ in the NIIS model can be modeled using $n+1$ process input and
output vectors. We denote the sets of input vectors and output vectors
of a protocol by $I$ and $O$, respectively. We are only interested in
protocols that solve decision tasks, so we may assume that the set $I$
of possible input vectors to a protocol is prefix-closed. The
following lemma states that for any protocol in the NIIS model, the
set $O$ of possible output vectors must necessarily be prefix-closed.

\begin{lemma}
\label{lemma: protocol prefix-closed}
Let $O$ be the set of possible output vectors of a protocol $\P$ in
the NIIS model, with corresponding set of input vectors $I$. Then $O$
is prefix-closed.
\end{lemma}

\begin{proof}
Let $\vO$ be an output vector produced by the execution $\alpha_O$,
and let $\vP$ be a prefix of $\vO$. We construct an execution
$\alpha_P$ as follows: For each $i$ such that $\vO[i] = v_i
\neq \bot = \vP[i]$, remove the action \finishi from $\alpha_O$, 
where $S$ is the snapshot returned by that action (meaning that
process $i$ fail-stopped before finishing). Clearly, the execution
thus obatined is a possible execution of $\P$, and its output vector
is $\vP$. Hence $\vP$ is in $O$, and $O$ is prefix-closed.
\end{proof}

Given that both the set of input vectors $I$ and the set of output
vectors $O$ associated with a protocol $\P$ are prefix-closed sets of
vectors, we can construct corresponding input and output complexes,
denoted $\cI$ and $\P(\cI)$, respectively. These complexes are
constructed in the same way as the complexes corresponding to input
and output sets of vectors for decision tasks, and the proofs that
they are indeed chromatic complexes are also identical. The output
complex $\P(\cI)$ is called a {\em protocol complex}.

Let $\cJ$ be a subcomplex of the input complex $\cI$. The set of
possible outputs when the protocol is given inputs corresponding to
simplexes in $\cJ$ is denoted $\P(\cJ)$.

\begin{lemma}
\label{lemma: subcomplex carries}
Let $\cJ$ be a subcomplex of $\cI$. Then $\P(\cJ)$ is a subcomplex of
$\P(\cI)$.
\end{lemma}

\begin{proof}
It suffices to show that $\P(\cJ)$ is a complex, since $\P(\cJ)$ is
clearly a subset of $\P(\cI)$. We simply look at the set of vectors
$J$ corresponding to the subcomplex $\cJ$ in isloation, as the set of
input vectors to the protocol $\P$. This set is prefix-closed since
$\cJ$ is a complex, and hence closed under containment. Hence the set
$P$ of output vectors given input vecors in $J$ is prefix-closed by
Lemma~\ref{lemma: protocol prefix-closed}. It follows from
Lemma~\ref{lemma: output complex} that $\P(\cJ)$, the complex
corresponding $P$, is a complex, and hence a subcomplex of $\P(\cI)$.
\end{proof}

In the remainder of this paper, we will specify protocols in NIIS
using both its formal specification from Subsection~\ref{subsection: NIIS}
as well as protocol complexes as described in this subsection
interchangeably. A set of inputs or outputs may thus be specified as
either a vector or as a simplex the vertexes of which are lebeled with
process ids and values.

\subsection{Subdivisions}
\label{subsection: subdivisions}
The standard chromatic subdivision was introduced by Herlihy and Shavit
\cite{HS93,HS94}, and has since been used by a number of researchers. It is
essentially a chromatic generalization of the standard barycentric
subdivision from classical algebraic topology \cite{Munkres,
Spanier}. In this subsection, we will present the first complete, formal
definition of the iterated standard chromatic subdivision, together
with a proof that this definition does indeed correspond to a
chromatic subdivision of a given complex. We also introduce the
concept of a {\em non-uniform chromatic subdivision}, a generalization
of the standard chromatic subdivision, in which the different
simplexes of a complex are not necessarily subdivided the same number
of times.  Informally, a non-uniform chromatic subdivision of level
$1$ of a complex $\cK$, denoted by $\wx^1(\cK)$, is constructed by
choosing, for each $n$-simplex in $\cK$, a {\em single\/} face of the
simplex (a face can be of any dimension and could also be the whole
simplex) to which we apply the standard chromatic subdivision. We then
induce the subdivision onto the rest of the simplex. This is best seen
in Figure~\ref{fig: non-uniform X}. Its right hand side shows a valid
non-uniform chromatic subdivision of a complex where, for example, the
simplex $(b,c,d)$'s subdivision is the result of subdividing the
1-face $(c,d)$ once and then inducing this subdivision onto the rest
of the simplex. The left hand side structure is not a legal
subdivision (it is in fact not even a complex). A $k$-th level
non-uniform chromatic subdivision of a complex $\cK$, denoted by
$\wx^k(\cK)$, is generated by repeating this process $k$ times, where
only simplexes in faces that were subdivided in round $k-1$ can be
subdivided in phase $k$. The complex on the right hand side of
Figure~\ref{fig: non-uniform X} is an example of a non-uniform chromatic
subdivision of level $2$, since the face $(a,d)$ is subdivided twice.

\input{non-uniformX}

%\begin{figure}[htb]
%%\vspace{2.5in}
%\centerline{\psfig{file=fig1.eps,width=5in,height=1.8in}}
%\caption{Valid and Invalid Non-uniform Subdivisions}
%\label{Fig1}
%\end{figure}

Later, we will show that these structures correspond in a natural way
to the set of protocol complexes in the NIIS model of computation. In
fact, it turns out that each non-uniform standard chromatic
subdivision is equal to some NIIS protocol complex (up to
isomorphism).

\subsection{The Standard Chromatic Subdivision}
\label{subsection: standard X}
In this subsection we define the {\em standard chromatic subdivision}, and
prove that this definition does indeed specify a chromatic subdivision
of a given complex.

Let $\cK$ be a pure, $n$-dimensional, chromatic geometric complex,
where the colors are the numbers in $\Bbb{Z}$$_{n+1}$. Label each
vertex $\vec{v}$ in $\cK$ with $\langle i, v_i \rangle$, where $i$ is
the color of $\vv$, and $v_i$ is a value in some set $D_I$ chosen such
that no two vertexes in $\cK$ have the same label. In order to define
the standard chromatic subdivision of $\cK$, we inductively define a
sequence of subdivisions $\cL_p$ of the skeletons of $\cK$, where $0
\leq p \leq n$ as follows. Let $\cL_0 = skel^0(\cK)$.  Now suppose
that $\cL_{p-1}$ is a chromatic subdivision of the $p-1$-skeleton of
$\cK$. Each vertex $\vv$ in $\cL_{p-1}$ is labeled $\langle i, S_i
\rangle$, where $S_i$ is the vertex scheme of some  simplex in 
$skel^{p-1}(\cK)$. The labels $\ang{i,S_i}$ are such that any $T =
(\vec{t_0}, \ldots, \vec{t_r})$, where $r \leq p-1$, is a simplex in
$\cL_{p-1}$ iff $ids(T) \subseteq ids(carrier(T)$ and the following
conditions hold for all $1 \leq i,j
\leq r$:


\begin{itemize}
\item $id(t_i) \neq id(t_j)$.
\item $id(\vec{t_i}) \in ids(val(\vec{t_i}))$
\item $val(\vec{t_i})$ is a face of $val(\vec{t_j})$ or vice versa
\item $id(\vec{t_j}) \in ids(val(\vec{t_i})) \Rightarrow
  val(\vec{t_j})$ is a face of $val(\vec{t_i})$
\end{itemize}

Let $S = (\vec{s_0}, \ldots, \vec{s_p})$ be a $p$-simplex in $\cK$.
The set $Bd(S)$ is the polytope of a subcomplex of the $p-1$-skeleton
of $\cK$, and hence of a subcomplex of $\cL_{p-1}$, which we denote
$\cL_ {Bd(S)}$.  Let $\vec{b}$ be the barycenter of $S$, and let
$\delta$ be some positive real number such that $0 < \delta < 1$. For
each $1 \leq i \leq p$, define $\vec{m_i}$ to be the point
$(1+\delta)\vec{b} - \delta \vec{s_i}$.  These points are called the
midpoints of $S$. Label $\vec{m_i}$ with $\langle i, S\rangle$, $S$
here being the vertex scheme of the geometric simplex $S$.  Let
$M_{S}$ be the set of midpoints of $S$. We define $\cL_{S}$ to be the
union of $\cL_{Bd(S)}$ and all the faces of all chromatic
$p$-simplexes $T = (\vec{t_0}, \ldots, \vec{t_p})$, such that for all
$1 \leq i,j \leq p:\,$ $\vec{t_i} \in skel^0(\cL_{Bd(S)}) \cup M_{S}$,
and the following conditions hold:\\
 
\begin{itemize}
\item $id(t_i) \neq id(t_j)$.
\item $id(\vec{t_i}) \in ids(val(\vec{t_i}))$
\item $val(\vec{t_i})$ is a face of $val(\vec{t_j})$ or vice versa
\item $id(\vec{t_j}) \in ids(val(\vec{t_i})) \Rightarrow val(\vec{t_j})$ is a face of
  $val(\vec{t_i})$
\end{itemize}

We now define $\cL_p$ to be the complex consisting of the union of the
complexes $\cL_{S}$, as $S$ ranges over all the $p$-simplexes of
$\cK$. We now prove that this structure makes sense mathematically,
that is, that it is in fact a subdivision of the $p$-skeleton of
$\cK$.

\begin{lemma}
\label{lemma: Lp chromatic subdivision}
For all $0 \leq p \leq n$, $\cL_p$ is a chromatic subdivision of $skel^p(\cK)$.
\end{lemma}
 
\begin{proof}
%(of Lemma~\ref{lemma: chromatic subdivision})

 We argue by induction. The case $p=0$ is trivial. So suppose $p >0$,
 and suppose the claim holds for $\cL_0, \ldots, \cL_{p-1}$. We will
 first prove that $\cL_p$ is a chromatic simplicial complex. To that
 end, we prove the following auxiliary lemma.

\begin{lemma}
For all $p$-simplexes $S$ in $\cK$, $\cL_{S}$ is a chromatic complex.
\end{lemma}
 
\begin{proof}
We must show that $\cL_{S}$ is closed under containment and
intersection.  Let $U$ be a simplex in $\cL_{S}$, and let $V$ be a
face of $U$, where $0 \leq \dim(V) \leq \dim(U) \leq p$. If $U$ is in
$\cL_{Bd(S)}$, then so is $V$, since $\cL_{Bd(S)}$ is a complex (since
$\cL_p$ is a subdivision and hence a complex by assumption). Hence $V$
is in $\cL_{S}$. Suppose $U$ is not contained in $\cL_{Bd(S)}$.  Then
$U$ must be the face of a $p$-simplex $T$ as described above. By
definition of $\cL_{S}$, all the faces of $T$, and hence all faces of
$U$, must be in $\cL_{S}$. It follows that $\cL_{S}$ is closed under
containment.

Let $U$, $V$ be simplexes in $\cL_{S}$, and suppose their
intersection, denoted by $W$, is nonempty. If $U$, $V$ are both in
$\cL_{Bd(S)}$, it follows immediately that $V^r$ is in $\cL_{Bd(S)}$
and hence in $L_{S}$.  Similarly, if $U$ is in $\cL_{Bd(S)}$ but $V$
is not, then $W = U \cap V = U \cap (V \cap |\cL_{Bd(S)}|)$. Note that
$V \cap |\cL_{Bd(S)}|$ is a simplex in $\cL_{Bd(S)}$, since all the
criteria given above are satisfied. Hence it follows that $W$ is in
$\cL_{Bd(S)}$, and hence in $\cL_{S}$. If neither $U$ nor $V$ is in
$\cL_{Bd(S)}$, then since all faces of $U$ and $V$ are in $\cL_{S}$,
then so is $W$. It follows that $\cL_{S}$ is closed under
intersection, and hence is a complex. That $\cL_{S}$ is
chromatic follows from the fact that we only include chromatic
simplexes in $\cL_{S}$ in our construction (note that $\cL_{p-1}$ and
hence $\cL_{Bd(S)}$ are chromatic by assumption).
\end{proof}

Notice that for all distinct $p$-simplexes $S, T$ we have that
$|\cL_{S}| \cap |\cL_{T}| = S \cap T$, which is a simplex in
$skel^{p-1}(\cK)$, and hence is the polytope of a subcomplex of
$\cL_{p-1}$, and hence of both $\cL_{S}$ and $\cL_{T}$. It follows
that $\cL_p$ is a simplicial complex \cite{Munkres}. It remains to
show that $\cL_p$ is a chromatic subdivision. To this end, we must
first show that every simplex in $\cL_p$ is contained in some simplex
in $skel^p(\cK)$, and that every simplex in $skel^p(\cK)$ is the union
of finitely many simplexes in $\cL_p$. Now, it is clear from our
construction that any simplex $T_q$ in $\cL_p$ is contained in some
simplex $S$ in $skel^p(\cK)$. Also, since for all simplexes $S$ in
$skel^p(\cK)$, the set of midpoints is finite, and $\cL_{p-1}$ is a
subdivision of $skel^{p-1}(\cK)$ by assumption, it follows that $S$ is
the union of finitely many simplexes in $\cL_p$. Hence $\cL_p$ is a
subdivision. This subdivision is chromatic, since $\cL_{p-1}$ is
chromatic by assumption, since the colors used to color the midpoints
of any simplex $S$ are exactly the colors used to color $S$, and since
any simplex in $\cL_p$ including midpoints must satisfy the
requirement that no two vertexes have the same color (id).
\end{proof}

We are now ready to give our definition of the standard chromatic
subdivision of a complex $\cK$.

\begin{definition}
\label{def: standard X}
The {\em standard chromatic subdivision} of $\cK$, denoted ${\cal
X}(\cK)$, is the complex $\cL_n$.
\end{definition}

An example of a complex and its standard chromatic subdivision is
given in Figure~\ref{fig: standard chromatic}.

\input{standardX}

Applying the standard chromatic subdivision $k$ times, where $k>1$,
yields a subdivision ${\cal X}^k(\cK) = {\cal X}({\cal
X}^{k-1}(\cK))$, which we call the $k$th iterated standard chromatic
subdivision \cite{HS93, HS94}. Since the standard chromatic
subdivision of a complex is again a complex, and a chromatic
subdivision of a chromatic subdivision of $\cK$ is itself a chromatic
subdivision of $\cK$, ${\cal X}^k(\cK)$ is a chromatic subdivision of
$\cK$. The number $k$ is called the {\em level} of the subdivision.

We will mostly use the vertex scheme representation of the standard
chromatic subdivision, as it has a particularly compact
representation, as stated in the lemma below.

\begin{lemma}
\label{lemma: standard X 2}
Let $\cK$ be a pure, chromatic complex of dimension $n$. The vertex
scheme of $\cX(\cK)$ is the closure under containment of the set of
all $n$-simplexes of the form $S= (\ang{0, S_0}, \ldots, \ang{n,
S_n})$, where for all $i$, $S_i$ is the vertex scheme of some face of
a simplex $S$ in $\cK$, and the following conditions hold for all $i$, $j$:
\begin{itemize}
\item $i \in \ids(S_i)$.
\item $S_i$ is a face of $S_j$ or vice versa.
\item If $j \in \ids(S_i)$, then $S_j$ is a face of $S_i$.
\end{itemize}
\end{lemma}

\begin{proof}
We argue by induction on $k$, where $0 \leq k \leq n$. It is immediate
that the simplexes of $\cX(\cK)$ lying in the subdivision $\cL_0$ of
$skel^0(\cK)$ are of this form (each such simplex is a vertex of $\cK$
labeled with a process id and a value), and the requirements above are
all satisfied trivially.

Now suppose the claim holds for $0, \ldots, k-1$. Consider a simplex
$T$ lying in the subdivision $\cL_k$ of $skel^k(\cK)$ and not in
$\cL_{k-1}$. Then $T = U \star V$, where $U$ is a simplex in
$\cL_{k-1}$, and $V$ is a simplex each vertex of which is one of the
midpoints in $M_S$, where $S= carrier(T)$. By assumption, $V$ is
non-trivial, meaning that there is at least one vertex in
$V$. Howeover, $U$ may be trivial. For each vertex $\vv$ in $V$,
$\val(\vv) = S$, the vertex scheme of $S$. Hence for $i,j$ in
$\ids(V)$, since $\ids(V) \subseteq \ids(S)$, all the conditions
listed above are clearly satisfied. For $i,j$ in $\ids(U)$, the
conditions are satisfied by induction. Now suppose $i$ is in
$\ids(U)$, while $j$ is in $\ids(V)$. Notice that $S_i = carrier(U)$,
and $S_j = carrier(V) = S$.

The first condition follows by induction (for $i$) and since $\ids(V)
\subseteq \ids(S) = \vals(V)$ (for $j$).  Since $carrier(U)$ is a face
of $S$, it follows that $S_i$ is a proper face of $S$, and hence of
$S_j$, which equals the vertex scheme of $S$, and so the second
condition is satisfied. It is clear that $i$ is in $\ids(S_j)$, since
$S_j$ equals the vertex scheme of $S$, and $i$ is in
$\ids(carrier(U))$, which is a subset of $\ids(S)$. That $S_i$ is a
face of $S_j$ has already been established. It follows that, since
$\cX(\cK)$ is chromatic, $\ids(U) \cap \ids(V) = emptyset$, $\ids(S_i)
\subseteq \ids(carrier(U))$, and $j$ is not in $\ids(carrier(U))$, $j$
cannot be in $\ids(S_i)$. It follows that the third condition is
satisfied.
\end{proof}

In the remainder of this paper, we will usually work with this
description of the standard chromatic subdivision, and refer to it as
$\cX(\cK)$. Whenever the distinction between the geometric and abstract
representations of $\cX(\cK)$ is significant, it will be mentioned
explicitly.

\subsection{The Non-Uniform Chromatic Subdivision}
\label{non-uniform X}

In this subsection, we define the {\em non-uniform chromatic
subdivision}, and prove that this definition does indeed specify a
chromatic subdivision of a given complex.

\begin{definition} 
\label{def: non-uniform X}
Let $\cK$ be a pure $n$-dimensional chromatic complex, where the
colors are the numbers in ${\cal Z}_{n+1}$. We will give a recursive
definition of a {\em non-uniform chromatic subdivision} of $\cK$. In
general, we denote a $k$-level non-uniform chromatic subdivision of a
complex $\cK$ by $\wx^k(\cK)$, for $k \geq 0$.

If $\dim(\cK)=0$, then for all $k \ge 0$, $\wx^k(\cK)$ is $\cK$
itself. Now suppose $\dim(\cK)>0$. Then $\wx^0(\cK)$ is $\cK$
itself. For $k>0$, $\wx^k(\cK)$ is given by the following procedure:
Partition the vertexes of $\cK$ into two disjoint sets, $A$ and $B$,
where $\cA$ is nonempty. From these sets we construct two complexes,
denoted by $\cA$ and $\cB$, respectively, as follows: A simplex $S$ in
$\cK$ is in $\cA$ if the vertexes spanning $S$ are all in $A$, and it
is in $\cB$ if its spanning vertexes are all in $\cB$. The subdivision
$\wx^k(\cK)$ is the complex consisting of all simplexes in $\cB$, all
simplexes in $\wx^{k-1}(\cX(\cA))$, and all simplexes of the form $S
\star T$, where $S$ is a simplex in $\wx^{k-1}(\cX(\cA))$, $T$ is a 
simplex in $\cB$, and $\carrier(S)\star T$ is a simplex in $\cK$.
%%
%
%
%For each maximal simplex $T$ in $\cK$, decompose its complex of faces
%$\cT$ into two disjoint, arbitrarily chosen subcomplexes $\cC_T$ and
%$\cS_T$, such that $\cT = \cC \star \cS$.  The vertexes in $\cC$ are
%refered to as {\em continuing}, and those in $\cS$ as {\em
%stopped}. We require that these subcomplexes be chosen such that for
%all maximal simplexes $T_1$, $T_2$ in $\cK$, we have that ${\cal C}_1
%\cap {\cal T}_2 \subseteq {\cal C}_2$.  We also require that there is
%at least one simplex $T$ in $\cK$ for which the set of continuing
%vertexes is nonempty. A non-uniform chromatic subdivision of $\cK$ of
%level $1$, denoted by $\wx^1(\cK)$ is defined as
%Now suppose that $\cK$ has $V>2$ vertexes, and that for $2, \ldots,
%V-1$, and all $k \leq 1$, the set of non-uniform chromatic
%subdivisions of any $\cK$ with $V$ vertexes has been defined.
%We decompose $\cK$ into two disjoint complexes
%$\cC$ and $\cS$, such that $\cK = \cC \star \cS$, and for all maximal
%simplexes $T_1$, $T_2$ in $\cK$, we have that $\cC \cap\cap {\cal
%T}_2 \subseteq {\cal C}_2$.  We also require that there is at least
%one simplex $T$ in $\cK$ for which the set of continuing vertexes is
%nonempty. The collection $\bigcup_{T\in \cK} \cC
%Anon-uniform chromatic
%subdivision of $\cK$ of level $1$, denoted by $\wx^1(\cK)$ is defined
%as
%\begin{displaymath}
%\wx^1(\cK) = \bigcup_{T \in \cK} \cS \star \cX(\cC)
%\end{displaymath}                                  
\end{definition}

%\begin{definition}
%\label{def: non-uniform chromatic X level k}
%A non-uniform chromatic subdivision of $\cK$ of level $k$, which we
%typically denote $\wx^k(\cK)$, can be obtained by applying the
%procedure described in Definition~\ref{def: non-uniform X} iteratively
%$k$ times, in such a way that, at each step, none of the continuing
%vertexes are part of the set of stopped vertexes from the previous
%step.
%\end{definition}

Informally speaking, a non-uniform chromatic subdivision of level $k$
is one in which there is some simplex in $\cK$ which is subdivided $k$
times, but no simplex that is subdivided more than $k$ times. Note
that the $k$ level standard chromatic subdivision is a special case of
the $k$ level non-uniform chromatic subdivision. Hence for all $k
\geq 0$, there exists some non-uniform chromatic subdivision of level
$k$. Our definition of non-uniform chromatic subdivisions is designed
to easily model protocol complexes of the NIIS model. At any level of
the recursion, the vertexes in $\cA$ can be thought of as
corresponding to processes that continue computing given their current
local state, while the vertexes in $\cB$ correspond to processes that
decide. An example of a level $1$ non-uniform chromatic subdivision of
a $2$-complex $\cK$ is given in Figure~\ref{fig: nu-subdiv1}, and an
example of a level $2$ non-uniform chromatic subdivision of a slightly
bigger $2$-complex $\cL$ is given in Figure~\ref{fig:
nu-subdiv2}. Note that in Figure~\ref{fig: nu-subdiv2} the complex
$\cA$ for the second level of recursion is isomorphic to the complex
$\cA$ for the first level of recursion in Figure~\ref{fig:
nu-subdiv1}.

\input{nu-subdiv1}

\input{nu-subdiv2}

\begin{lemma}
\label{lemma: non-uniform chromatic X}
Any non-uniform chromatic subdivision $\wx^k(\cK)$ is a chromatic
subdivision of $\cK$.
\end{lemma}

\begin{proof}
We first note that $\wx^k(\cK)$ is well-defined, since each recursive
step lowers the level of subdivision by $1$, and $\wx^0(\cK)$ is
defined for all $\cK$. We will prove that $\wx^k(\cK)$ is a chromatic
subdivision by induction on $k$.

The case where $k=0$ is trivial, since $\wx^0(\cK)=\cK$. Now suppose
that $k>0$, and that for $0 \leq l \leq k-1$, and any complex $\cK$,
$\wx^l(\cK)$ is a chromatic subdivision of $\cK$. If $B = \emptyset$,
the result follows by induction and by Lemma~\ref{lemma: Lp chromatic
subdivision}. So suppose that $B$ is nonempty.

We first show that $\wx^k(\cK)$ is closed under containment. Let $U$
be a simplex in $\wx^k(\cK)$, and let $V$ be a face of $U$. If $U$ is
in $\cB$, then so is $V$, since $\cB$ is a complex. Hence $V$ is in
$\wx^k(\cK)$. Similarly, if $U$ is in $\wx^{k-1}(\cX(\cA))$, then so
is $V$, since $\wx^{k-1}(\cX(\cA))$ is a complex by our induction
hypothesis. Now suppose $U=S\star T$ for some $S$ in
$\wx^{k-1}(\cX(\cA))$, $T$ in $\cB$. Then $S \cap V$ is in
$\wx^{k-1}(\cX(\cA))$, and $T \cap V$ is in $\cB$. It follows that $V
= (S \cap V) \star (T \cap V)$, where $\carrier(S \cap V)\star (T \cap
V)$ is a simplex in $\cK$. By Definition~\ref{def: non-uniform X}, $V$
is in $\wx^k(\cK)$. It follows that $\wx^k(\cK)$ is closed under
containment.

Let $U$, $V$ be simplexes in $\wx^k(\cK)$, and let $W$ be their
intersection. If both $U$, $V$ are in $\cB$, then so is $W$, since
$\cB$ is closed under intersection. Similarly, if both $U$ and $V$ are
in $\wx^{k-1}(\cX(\cA))$, then so is $W$, since $\wx^{k-1}(\cX(\cA))$
is closed under intersection. If $U$ is in $\cB$ and $V$ is in
$\wx^{k-1}(\cX(\cA))$, or vice versa, then $U \cap V = \emptyset$, and
so containment under intersection holds vacuosly. We now consider the
case where either $U$ or $V$ is not contained in either complex, that
is, suppose $U=S\star T$ for some $S$ in $\wx^{k-1}(\cX(\cA))$, $T$ in
$\cB$, and $V=X\star Y$ for some $X$ in $\wx^{k-1}(\cX(\cA))$, $Y$ in
$\cB$. Now, $U \cap V = (S\star T) \cap (X\star Y)$, and $(S\star T)
\cap (X\star Y) = (S \cap X) \star (T \cap Y)$ \cite{Munkres}. If $S
\cap X = \emptyset$ or $T \cap Y = \emptyset$, then one of the cases
discussed above applies, and $V$ is in $\wx^k(\cK)$. So suppose now
that $S$, $T$, $X$, $Y$, and the intersections $S \cap X$ and $Y \cap
T$ are all nonempty. Since $\carrier(S \cap X)$ is a face of both
$\carrier(S)$ and $\carrier(X)$, it follows that $\carrier(S \cap X)
\star T$ and $\carrier(S \cap X) \star Y$ are simplexes in $\cK$, and
so is their intersection $\carrier(S \cap X) \star (T \cap Y)$, since
$\cK$ is a complex. It follows that $V$ is in$\wx^k(\cK)$. This
concludes the proof that $\wx^k(\cK)$ is a complex. That it is a
chromatic complex follows directly from Lemma~\ref{lemma: Lp chromatic
subdivision}.

We now prove that $\wx^k(\cK)$ is a chromatic subdivision. Given a
simplex $U$ in $\wx^k(\cK)$. If $U$ is in $\cB$ then $U$ is clearly
contained in a simplex in $\cK$, namely itself, and that the colors of
$U$ are contained in the set of colors of its carrier. If $U$ is in
$\wx^{k-1}(\cX(\cA))$, it follows by induction and Lemma~\ref{lemma:
Lp chromatic subdivision} that $U$ is contained in some some simplex
$\carrier(U)$ in $\cA$, and hence in $\cK$, and that the colors of $U$
are a subset of the colors of its carrier. Now suppose $U=S\star T$,
where $\carrier(S) \star T$ is in $\cK$. Then $U$ is contained in
$\carrier(S) \star T$, and the colors of $U$ are a subset of the
colors of $\carrier(S) \star T$. Now consider any simplex $U$ in
$\cK$. We can decompose it into two disjoint faces $S$ and $T$, such
that $S \in \cA$ and $T \in \cB$. The simplex $S$ is subdivided
according to $\wx^{k-1}(\cX(\cA))$, which by induction and
Lemma~\ref{lemma: Lp chromatic subdivision} consists of finitely many
simplexes. The simplex $T$ is not subdivided at all. It follows that
the subdivision $\wx^k(\cK)$ subdivides $U$ into finitely many
simplexes (those in $\wx^{k-1}(\cX(\cS)) \star T$). This completes the
proof that $\wx^k(\cK)$ is a chromatic subdivision.
\end{proof}

A non-uniform subdivision $\wx^k(\cK)$ of a complex induces a
non-uniform chromatic subdivision of any subcomplex $\cL$ of
$\cK$. The level of the induced subdivision of $\cL$ may vary from
subcomplex to subcomplex.

\begin{definition}
\label{definition: level of subdivision}
Let $\cK$ be a chromatic complex, $\cL$ a subcomplex or simplex of
$\cK$, and let $\wx^k(\cK)$ be a non-uniform iterated chromatic
subdivision of $\cK$. We denote its restriction to simplexes in $\cL$
for $\wx^k(\cL)$. The {\em level} of $\wx^k(\cK)$ on $\cL$ is the
maximal level of subdivision of $\wx^k(\cL)$, which we denote by
$k_{\cL}$.
\end{definition}

It is clear that for any subcomplex or simplex $\cL$ of
$\cK$, it must be the case that the level of $\wx^k(\cK)$ on
$\cL$ is less than or equal to $k$.












