rep sour%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                 Chapter 4: Applications of ACT                           %
%                           Created: 4/13/97                               %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Approximate Agreement}
\label{section: approximate agreement}

As an application of Theorem~\ref{thm: main}, we will analyze the
well-known Approximate Agreement task \cite{DLPSW86}, in which each
process $i$ is given an input $x_i$ taken from some finite subset of
the real numbers, and is required to decide on some output $y_i$ such
that, for some predetermined $\epsilon > 0$, $\max_i y_i - \min_i y_i
< \epsilon$, and for all $i$, $y_i \in [\min_i x_i, \max_i
x_i]$. Aspnes and Herlihy \cite{AH} proved a lower bound that implies
a worst case time complexity of $\floor{\log_3 \frac{\max_i x_i -
\min_i x_i}{\epsilon}}$ and an upper bound of $\floor{\log_2
\frac{\max_i x_i - \min_i x_i}{\epsilon}}$ in the NIIS
model\footnote{Although their proofs are for the read/write register
model, they carry over to the NIIS model}. In this section, we will
show that this gap is not simply a technical fluke.  We specify the
finite $n+1$-process Approximate Agreement problem for $\epsilon >0$
as follows:
\begin{itemize}
\item $I = \{[x_0, \ldots, x_n] \mid x_i \in V \cup \{\bot\}\}$, where $V$ is a 
finite subset of $\Bbb{R}$.
\item $O = \{[y_0, \ldots, y_n] \mid y_i \in V \cup \{\bot\}, |y_i - y_j| \le \epsilon\}$.
\item $\gamma = \{(\vI, \vO) \mid \vO[i] \in [\min_i \vI[i], \max_i \vI[i]]\}$.
\end{itemize}

%Using our framework, we achieve a $\floor{\log_{d} \frac{\max x_i -
%\min x_i}{\epsilon}}$ lower bound for solving Approximate Agreement in
%both the IIS (and atomic snapshot models, where $n+1$ is the number of
%participating processes, and $d$ is the function ${\cal N} \rightarrow
%{\cal N}$ that takes on the value $2$ everywhere except at $n=1$,
%where it takes on the value $3$. and . . \\
%%% end of was removed

\begin{theorem}
\label{thm: approximate agreement}
Given $\epsilon >0$, there is a protocol $\P$ solving Approximate
Agreement with complexity $\floor{\log_{d} \frac{\max_i \vI[i] -
\min_i \vI[i]}{\epsilon}}$ on any input vector $\vI$, where $d=3$ if 
the size of the participating set of $\vI$ is $2$, and $d=2$ if the
size of the participating set of $\vI$ is $3$ or more. Moreover, this
protocol is optimal on each input vector.
\end{theorem}

Theorem~\ref{thm: main} provides both the upper bound protocol and the
matching lower bound. We hope to convince the reader that this is an
excellent example of how topological modelling exposes subtle points
which would otherwise be difficult to grasp.

\begin{figure}[htb]
%\vspace{2.5in}
\centerline{\psfig{file=approx.ps}}
\caption{Simplex Subdivided by an Approximate Agreement Protocol}
\label{fig: Approximate Agreement}
\end{figure}

The key intuition behind our ability to close the gap between the
upper and lower bounds for Approximate Agreement is depicted in
Figure~\ref{fig: Approximate Agreement}, which shows the subdivisions
induced by a three process protocol on the input vector
$[0,1,2]$. Aspnes and Herlihy \cite{AH} derive their lower bound for
any $n+1$ process algorithm from a ``bad'' execution in which only the
two processes with inputs farthest apart participate.  Such an
execution in our model corresponds to a sequence of chromatic
subdivisions of the edge between $\ang{0, 0}$ and $\ang{2,2}$.

In the end, the vertexes of each $1$-simplex in the non-uniform
chromatic subdivision of the edge connecting $\ang{0, 0}$ and
$\ang{2,2}$ must be mapped by a simplicial map to vertexes with output
values that are less than $\epsilon$ apart, and hence connected by a
simplex in the output complex. Since each subdivision introduces two
new vertexes and splits the edge in three, in $\log_3 2$ such steps one
can cut the distance among these vertexes to $\epsilon$.  However,
note that if one considers executions in which $3$ processes
participate, we run into a problem: No matter how we subdivide the
$2$-simplex, there is always a path of $1$-simplexes between $\ang{0,
0}$ and $\ang{2,2}$ that includes the vertex $\ang{1, (\ang{0,0},
\ang{1,1}, \ang{2,2})}$ (marked by a darker color). Hence, for $3$ 
process executions, only a single new vertex will be introduced to
this path between $\ang{0, 0}$ and $\ang{2,2}$, and so the maximum
distance between any two vertexes is cut by at most a half for each
level of subdivision. Hence our tight $\log_2$ lower bound.  Our upper
bounds follow directly from Theorem~\ref{thm: main} by specifying the
proper subdivision and map. The key thing to note about the proof of
Theorem~\ref{thm: approximate agreement} is that it does not involve
any mention of the actual executions; All we need to do is argue about
the topology of the inputs and outputs and then apply
Theorem~\ref{thm: main}.

\begin{proof}
We first recast the description of the Approximate Agreement in terms
of input and output complexes as follows:

\begin{itemize}
\item $\cI$ is the closure under containment of the collection of all 
simplexes of the form $(\ang{0, x_0}, \ldots, \ang{n, x_n})$, where
for all $i$, $x_i \in V \cup \{\bot\}$.
\item $\cO$ is the closure under containment of the collection of all 
simplexes of the form $(\ang{0, y_0}, \ldots, \ang{n,y_n})$,  where
for all $i,j$,  $y_i \in V \cup \{\bot\}$ and  $|y_i - y_j| \le \epsilon$.
\item $\Gamma = \{(S, T) \mid \vals(T) \subseteq [\min \vals(S) , \max \vals(S)]\}$.
\end{itemize}

Note that the size of the participating set for the input vector
corresponding to a simplex $S$ in $\cI$ equals $\dim(S)+1$.
Theorem~\ref{thm: approximate agreement} then states that, given
$\epsilon >0$, there is a protocol $\P$ solving Approximate Agreement
with complexity $\floor{\log_{d} \frac{\max \vals(S) - \min
\vals(S)}{\epsilon}}$ on any input simplex$S$, where $d=3$ if
$\dim(S)=1$, and $d=2$ if $\dim(S) \ge 1$. Moreover, this protocol is
optimal on each input simplex $S$.

We first establish the lower bound. Let $\P$ be a protocol that solves
Approximate Agreement with worst case complexity $k_S$ on $S$, where
$S$ is any input simplex of dimension $n \geq \dim(S) >0$. Let $D(S)=
\max_{\vv, \vu \in S} \val(\vv) - \val(\vu)$. Then Theorem~\ref{thm:
main} states that there is some mapable non-uniform chromatic
subdivision $\wx^k(\cI)$, with level $k_S$ on $S$. We will show that
$k_S \geq \floor{\log_{d} \frac{D(S)}{\epsilon}}$. The proof uses the
following lemma.

\begin{lemma} 
Let $l \leq k$. Label the vertexes of $\wx^l(S)$ with real numbers in
a way that agrees with the intial value labeling of $S$, and let $l_S$
be the level of $\wx^l(S)$. Then

\begin{displaymath}
  D(\wx^l(S)) \geq \frac{D(S)}{d^{l_S}} 
\end{displaymath}
\end{lemma}

\begin{proof}
Suppose without loss of generality that $l=l_S$.  We first give the
proof for the case of two participating processes and $d=3$. By
definition of $D(S)$, there is a $1$-simplex $U = (\vec{u_0},
\vec{u_1})$ in $\cS$ such that $D(U) = D(S)$. The complex $\wx^l(U)$
contains at most $3^l$ $1$-simplexes, denoted $U_1, \ldots, U_M$,
where $M \leq 3^l$.  These form a continuous path from $\vu_0$ to
$\vu_1$, the endpoints of which are labeled with $val(\vu_0)$ and
$val(\vu_1)$, respectively. So the best we can do is cut $D(U)$ in
$3^l$ pieces. The triangle inequality tells us that $D(U) \leq
\sum_{i=1}^M D(U_i) \leq M \max_i D(U_i) \leq 3^k \max_i D(U_i)$.
Hence $\max_i D(U_i) \geq D(U)/{3^l} = D(S)/{3^l}$. The lemma follows,
since $\max_i D(U_i) \leq D(\wx^l(S))$.

We now prove the case where the size of the participating set is
greater than $2$ (and hence $\dim(S)$ is greater than $1$) and
$d=2$. We argue by induction on $l$. The case $l=0$ is trivial. Now
suppose the claim is true for $l-1$.  By definition of
$D(\wx^{l-1}(S))$, there is a $1$-simplex $U = (\vec{u_0}, \vec{u_1})$
in $\wx^{l-1}(S)$ such that $D(U) = D(\wx^{l-1}(S))$.  $U$ is a face
of some $2$-simplex $U' = (\vec{u_0}, \vec{u_1}, \vu_2)$. Suppose
first that the next level of non-uniform chromatic subdivision does
not subdivide $U$ completely.  Then there is some $1$-simplex $T$ in
the level $l$ non-uniform subdivision of $U'$ with $D(T) \geq
D(U)/2$. Since $D(U) = D(\wx^{l-1}(S))$ and $D(T) \leq D(\wx^l(S))$,
the lemma follows by induction. Suppose instead that the next level of
subdivision does subdivide $U'$ completely. Then the level $l$
subdivision has an internal vertex $\vm_2$, colored with $id(\vu_2)$,
and two neighboring $1$-simplexes $T_0 =(\vu_0, \vm_2)$ and
$T_1=(\vm_2, \vu_1)$.  The triangle inequality then tells us that
$D(U) \leq D(T_0)+D(T_1) \leq 2\max_i D(T_i)$, where $i \in
\{0,1\}$. It follows that $D(\wx^l(S)) \geq D(\wx^{l-1}(S))/2$.  The
lemma follows by induction.
\end{proof}

Suppose now that there exists a chromatic simplicial map $\mu:
\wx^k(\cI) \rightarrow \cO$ such that, for all simplexes $T$ in
$\wx^k(\cI)$, $\mu(T) \in \Gamma(carrier(T))$. We can associate this
map with a labeling of the vertexes in $\wx^k(\cI)$ as follows. Label
each vertex $\vv$ in $\wx^k(\cI)$ with $\val(\mu(\vv))$. This labeling
agrees with the input value labeling of $\cI$, since for any vertex
$\vv$, the task specification requires that for any simplex $S_0$ that
contains $\vv$, it must be the case that $\mu(\vv) \in D(S_0)$. Choose
two neighboring simplexes $S_0$ and $S_1$ containing $\vv$ such that
$D(S_0) \cap D(S_1) = val(\vv)$. It follows that $\mu(\vv) =
val(\vv)$. Now let $T$ be any simplex in $\wx^k(\cI)$.  By definition
of $\mu$, $\mu(T)$ is a simplex in $\cO$, and hence $D(\mu(T)) <
\epsilon$. It follows that $D(T) = D(\mu(T)) <
\epsilon$, and hence that $D(\wx^k(\cI)) < \epsilon$, where
$D(\wx^k(\cI))$ is equal to $max_{T \in \wx^k(\cI)} D(T)$.  Clearly,
for any input simplex $S$, it follows that the labels on the
restriction of $\wx^k(\cI)$ to $S$, $\wx^k(S)$, have range less than
$\epsilon$.  The previous lemma then states that $\epsilon >
D(\wx^k(S)) \geq \frac{D(S)}{d^{k_S}}$. We conclude that

\begin{displaymath}
k_S \geq \floor{\log_{d} \frac{D(S)}{\epsilon}}
\end{displaymath}

To prove the upper bound, we construct a mapable non-uniform chromatic
subdivision $\wx^k(\cI)$ of the input complex with level $k_S =
\floor{\log_{d} \frac{D(S)}{\epsilon}}$ on each input simplex $S$, 
according to Definition~\ref{def: non-uniform X}. As argued above, the
requirement that the subdivision be mapable is equivalent to saying
that there is a vertex labeling of $\wx^k(\cI)$ that agrees with the
initial value labeling of $\cI$ with the additional property that
$D(\wx^k(\cI)) < \epsilon$.

For each level of subdivision $l \leq k$, a vertex $\vv$ is in $A$ if
there is another vertex $\vu$ such that $\val(\vv) - \val(\vu) >
\epsilon$, otherwise it is in $B$. Before applying the next level of
subdivision to $\cX(\cA)$ (as specified by Definition~\ref{def:
non-uniform X}), we relabel all new vertexes in $\cX(\cA)$ (those not
in $skel^0(\cA)$) as follows: If the dimension of $\cA$ is $1$, label
the new vertexes in $\cX(\cA)$ with $(2\min val(\cA) + \max
val(\cA))/3$ and $(\min val(\cA) + 2\max val(\cA))/3$,
respectively. This cuts the distance between the vertexes with values
apart in $3$. Otherwise, label the new vertexes with $(\min val(\cA) +
\max val(\cA))/2$. This cuts the distance between the values furthest
apart in $2$.

It is clear from this construction that, at each level of recursion,
for all simplexes $S$ in $\cI$ we have that, if $D(\wx^l(S)) >
\epsilon$, then either $D(\wx^{l+1}(S)) = D(\wx^l(S))/d)$, or
$D(\wx^{l+1}(S)) < \epsilon$. It follows that the level $k_S$ of
$\wx^k(\cI)$ on $S$ is $\floor{\log_{d}\frac{D(S)}{\epsilon}}$, where
$d=3$ if $\dim(S)=1$, and $d=2$ if $\dim(S) >1$. We conclude from
Theorem~\ref{thm: main} that there is a wait-free protocol that solves
Approximate Agreement with worst case time complexity $\floor{\log_{d}
\frac{D(S)}{\epsilon}}$ on input $S$, where $d=3$ for two participating 
processes and $d=2$ for three or more.
\end{proof}

