\section{Renaming}
\label{section: renaming}
In this section we use the asynchronous complexity theorem to analyze
the complexity of the renaming task of Attiya et al. \cite{Renaming},
in which at most $N=n+1$ processes are given unique input names taken
from a large name space, and must choose unique output names taken
from a smaller name space.

A protocol is {\em comparison-based} if the only operations
a process can perform on process ids is to test for equality and
order; that is, given two process ids $P$ and $Q$, a process can test
for $P = Q$, $P \leq Q$, and $P \geq Q$, but cannot examine the
structure of the identifiers in any more detail (e.g., it cannot test
whether $P$ is prime). We will only consider comparison-based
protocols in this section.

Let $\cA$ and $\cB$ be complexes where each vertex is labeled with a
process id,and possibly with a value.  $\cB$ is a {\em recoloring} of
$\cA$ if there exists a bijective simplicial map ({\em not}
color-preserving)
$$
\rho: \cA \rightarrow \cB
$$ that is (1) order-preserving on process ids: if $id(\vu) < id(\vv)$
then $id(\rho(\vu)) < id(\rho(\vv))$, and (2) value-preserving: if
$val(\vv)$ is defined then $val(\vv) = val(\rho(\vv))$.

\begin{theorem}[Comparison-Based Time Complexity]
%\label{theorem: ACT}
\label{theorem: comp}
A decision task $\dtask$ has a wait-free protocol in the $IIS$ model
with worst case time complexity $k_{S^m}$ on input $S^m$ iff there is
a mapable non-uniform chromatic subdivision $\wx^k({\cal
  I}^n)$ with level $k_{S^m}$ on $S^m$ such that any recoloring $\rho:
\wx^k(S^m_0) \rightarrow \wx^k(S^m_1)$ induces a recoloring $\rho':
\mu(\wx^k(S^m_0)) \rightarrow \mu(\wx^k(S^m_1))$ such that for every
face $T$ of $S^m_0$, $\rho'(\mu(\wx^k(T))) =
\mu(\rho(\wx^k(T)))$.
\end{theorem}

The additional condition captures the notion that the behavior of
comparison-based protocols does not change if processes are renamed in
an order-preserving way.  The proof of this theorem is almost
identical to the proof of Theorem~\ref{theorem: main}, except that it
is necessary to check at each step that the
equivalence-under-recoloring property continues to hold.

\begin{theorem}
\label{theorem: renaming}
There exists a wait-free protocol for $N$ process Renaming in the
   comparison-based 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.$$
\end{theorem}
Similar bounds follow immediately for the AS and MRSW models since Borowsky and Gafni
 \cite{BorowskyGafniPODC} show that one can
implement IIS in the AS model in $\Theta(n)$ time and
in time $\Theta(n^2)$ in the MRSW model.

We now sketch the main idea behind the proof.  Our complexity
theorem says that the complexity of any protocol solving the renaming
problem in IIS is exactly the number of chromatic subdivisions
necessary to allow a ``symmetric'' simplicial map from the subdivided
input complex to the output complex. And indeed, for $N=2$ processes a
single subdivision suffices to allow such a map as depicted on the
right hand side of Figure~\ref{Fig2}. Labeling this subdivision
symmetrically requires 3 names and the resulting algorithm requires
exactly one time step.  For $N=3$ processes, 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 have different labels, which implies that one can
solve renaming in this case in a single time step. The various
``stacked'' subdivided 2-simplexes in the figure correspond to input
simplexes with different orders among the processors. For the sake of
our discussion it is enough to think about the ``top'' one.

If we only have $5$ Names, We need to subdivide the 2-simplex so that
all subsimplices can be labeled with different names. 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. Though one could also in this case provide a
uniform/canonical subdivision, it would be significantly more
complicated and the implied algorithm would have all processes take
two steps. Figure~\ref{Fig3} implies that with 5 names the time
complexity of solving 3 process renaming is two. As with the two
process case, the subdivision completely describes the solution
algorithm, as shown in Figure ~\ref{fig: alg three processes}. The two
process algorithm we refer to appears in Figure~\ref{Fig2}.
\footnote{We choose 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.}

\begin{figure}[h]
{\small
\begin{verse}
\verb$ Access first IS object $\\
\verb$  if in view one other process has value $$\bot$ \\
\verb$     run 2 process alg with non-$$\bot$\verb$ object$ \\
\verb$  elseif in view 2 other processes have value $$\bot$\\
\verb$     return 1$ \\
\verb$  else$\\
\verb$     if my_id is highest return 5$\\
\verb$     else access second IS object $\\
\verb$        run 2 process alg with other non-$$\bot$ \verb$process, $\\
\verb$        returning 4 in place of 1 if it was $$\bot$\\
\end{verse}
}
\caption{Algorithm for three process Renaming} %(for process p)
\label{fig: alg three processes}
\end{figure}

For $N=4$, one step induces a standard chromatic subdivision
$\cX(S^3)$ of the input 3-simplex such that each 2-face of $S^3$ can
be labeled with 6 names as in the case of $N=3$, and the 3-simplex in
the center of $\cX(S^3)$ (the one corresponding to executions in which
all processes see all others' values) is labeled using 4 additional
names, a total of 10 names.  We refer to all the 3-simplexes of
$\cX(S^3)$ apart from the central one as the outer 3-simplexes.e Now,
if we wish to remove one name from the labeling, we need to subdivide,
say, the 2-faces of the input simplex so that they use 5 names as in
the case of $N=3$, and then induce this subdivision non-uniformly onto
the whole subdivided simplex $\cX(S^3)$ (in other words, subdividing
each 2-simplex on the face of $S^3$ induces a non-uniform subdivision
of the outer 3-simplex that contains it in the subdivision
$\cX(S^3)$).  However, this additional time step allows us to
introduce an additional subdivision in the center 3-simplex of
$\cX(S^3)$ by taking one of its 1-faces $S^1$ and subdividing it as in
the case of $N=2$. Note that this does not require accessing a new
(third) IS object, since in terms of the executions implied by the
subdivision, after the first time step of the algorithm (in which the
1st IS object is accessed) the execution proceeds in one of the outer
3-simplexes or in the center one but not in both.  As we will prove in
the full paper, As we will show in the full proof, one can label the
induced subdivided 3-simplexes of $\wx^2(S^3)$ resulting from the
subdivision of $S^1$ by using the same names that appear on the
internal vertexes of the subdivided $2$-faces of $S^3$. Thus, if {\it
time\/}$(4)=2$ one can eliminate 2 names at the price of 1 time step,
requiring a total of 8 names.  Now, if {\it time\/}$(4)=2$, we cannot
remove any additional names from the 2-simplexes on the face of the
subdivision. This is because 5 names is the lower bound (see
\cite{HS95}). We can however eliminate one additional name from the
center 3-simplex, by, instead of subdividing a 1-simplex on its face,
subdividing a 2-simplex and labeling all its original vertexes with
the same name.  This subdivision requires 5 names and is exactly as in
the $N=3$ case (and hence two time steps) using the same names of the
2-simplexes $S^2$ on the boundary of $S^3$, with only the names of the
original vertexes of $s^2$ replaced by one of the names of the center
simplex. The original vertexes of the center 3-simplex are thus
labeled using only two names (the ones on its subdivided 2-face are
all labeled the same), and the faces of $S^3$ and the internal
simplexes of the subdivision are labeled using 5 names, a total of 7
names.  We derive the upper bound by extending this same reasoning
inductively to higher values of $N$, where starting with the $N(N+1)$
subdivision, the 1st time step we add cuts $N-2$ names, the second
$N-3$ and so on. We now proceed to the proof.

\begin{proof}(Of Theorem~\ref{theorem: renaming})

Our complexity theorem says that the complexity of any protocol
solving the renaming problem in the NIIS model is determined by the
level of non-uniform chromatic subdivision necessary to allow a
symmetry-preserving simplicial map from the subdivided input complex
to the output complex. As argued above for the case of approximate
agreement, such a simplicial map corresponds to a symmetric labeling
of the vertices of the subdivided input complex that agrees with the
task specification, that is, no two vertices on a simplex have the
same label. 

Given an input simplex $S$ to the $N$-process renaming problem, where
$N>1$. Suppose without loss of generality that the process ids of the
vertices in $S$ are in the range $0, \ldots, N-1$ and in increasing
order, that is, $\id(\vv_i) < \id(\vv_j)$ if and only if $i <
j$. Suppose also that there are $n= \mbox{\it names\/}(N)$ available
names, taken from the set $\{1, \ldots, n\}$, and that the available
time is $t= \mbox{\it time\/}(N)$.  The proof proceeds by inductively
building symmetrically labeled non-uniform subdivisions having maximal
level $t$ and labels taken from the $n$ names given above, where $n$
and $t$ are in accordance with the formula given above. The current
version of the proof as presented here is still in draft form and
provides the construction of each such subdivisionis but is missing
the proof that the subdivisions we use are in fact valid non-uniform
chromatic subdivisions.  This proof is rather straightforward, and for
now is left to the reader. %For lack of space we only , and leave the
%proof that it is valid to the full paper.

For ease of argument, we express the formula more compactly as
follows: Let $f(N,t) = \frac{N(N+1)}{2} - \overset{t}{\underset{i=2}{
\sum}} N-i$, for all $N>1$, $1 \leq t \leq N-1$.  Then Theorem
~\ref{theorem: renaming} says that there is a renaming protocol for
$N$ processes using $n$ names and $t$ time if $f(N,t) \leq n <
f(N,t)$.
 
We will provide a general construction for the case where the number
of names used is $n=f(N,t)$. The in-between case, in which $f(N,t) < n
< f(N,t-1)$, follows, since we can just run the algorithm for
$f(N,t)$ names whose output complex of this algorithm is a subcomplex of the
output complex for n, thus providing a solution in this case too.

We first consider the case where $N=2$.  We show how to non-uniformly
subdivide and symmetrically label (with output values) a typical input
simplex, $S=(\vv_0, \vv_1)$.  As discussed above, the labeling will
correspond to a simplicial map satisfying the task specification.
Suppose without loss of generality that $\id(\vv_0) < \id(\vv_1)$. The
resulting subdivision and simplicial map correspond to one of the two
1-simplexes in Figure ~\ref{Fig1}. The subdivision is simply a
standard chromatic subdivision of the entire simplex, and the
simplicial map $\mu$ is defined by the labelings on the vertices. The
level of subdivision is $1$, and the number of names used is $3$,
which is in accordance with the formula, since $(2\cdot 3)/2 - (2-2) =
3$. The symmetry requirement is clearly satisfied, since the choice of
which vertex gets the bigger name depends only on the relative
ordering of the original names. We denote this labeled subdivision for
$C_1(1,2,3)(S)$, and we will use it as an initial building block in
the ensuing induction. The notation $C_1(1,2,3)$ should be interpreted
as follows; The subscript $1$ indicates the dimension of the input
simplex, which is one less than the number of processes that
participate. The entries in the parentheses act as place holders for
labels. In this simple case, the labels used are $1$, $2$ and $3$. The
relative ordering of the place holders matters, as it corresponds to
the relative ordering of process ids.

Assume by induction that the result holds for $2, \ldots, N-1$
processes. We will establish it for the case of $N$
processes. Let $S=(\vv_0, \ldots,
\vv_{N-1})$ be an $N-1$-dimensional input simplex to the $N$ process
renaming problem. 
 
We first show how to subdivide and label $S$ in the extreme case where
$n = 2N-1$ and $t = N-1$. The right hand side of Figure ~\ref{Fig3}
shows how this is done in the case of $N=3$, $n=5$ and $t=2$, where
each big triangle corresponds to a subdivided simplex $S$. We see that
the entire simplex is subdivided once according to the standard
chromatic subdivision, with the $1$-simplices corresponding to the
boundary of the original simplex labeled according to
$C_1(1,2,3)$. The internal $2$-simplex is labeled using $4,5$, and one
edge (the one labeled with only $4$'s) is subdivided and labeled
further using $C_1(4,2,3)$. In general, we first subdivide the entire
simplex once according to the standard chromatic subdivision. We say a
vertex in this subdivision is {\em external} if its carrier is a
proper face of $S$, and {\em internal} otherwise.  By our induction
hypothesis, we already know how to solve $N-1$ process renaming with
$2N-3$ available names in time $N-2$..  This solution corresponds to
the labeled non-uniform subdivision $C_{N-2}(1,2,3, \ldots, 2N-3)$ of
level $N-2$. We continue subdividing the subcomplex spanned by the
external vertices so that eventually the subcomplex corresponding to
each $(N-2)$-face of $S$ is subdivided and labeled according to
$C_{N-2}(1,2,3, \ldots, 2N-3)$. These subdivisions are all induced onto
the entire subdivided simplex in the obvious way, that is, by
replacing the face with the appropriately subdivided face and starring
this with all vertices in the complex that were connected to the face
before the replacement.  This is in accordance with the definition of
the non-uniform chromatic subdivision.

We now label the $N$ internal vertices of the complex as follows: the
vertex whose process id is the largest, $\vv_{N-1}$, gets the label
$2N-1$. All the other vertices get the label $2N-2$. All that remains
is to subdivide and label the face of the internal simplex spanned by
the vertices with label $2N-2$. Call this simplex $T$. Using our
induction hypothesis again, we subdivide and label $T$ according to
$C_{N-2}(2N-2, 2N-4, 2N-3, .. , 2,3)$, and induce this subdivision
onto the rest of the subdivided simplex by replacing $T$ with the
labeled subdivision of $T$ and starring this with all vertices in the
complex that were connected to the $T$ before the replacement. This
concludes the construction of the labeled subdivided complex
$C_{N-1}(1,2,3 \ldots, 2N-1)$, which corresponds to a protocol that uses
time $N-1$ and $2N-1$ names, as required.

We now consider the general case, in which $n = f(N,t)$ and $1 \leq t
< N-1$. , which can be applied to any $(N-2)$-dimensional input
simplex to the $N-1$ process renaming problem.

We now describe how to subdivide and label $S$.  The left hand side of
Figure ~\ref{Fig3} shows how this is done in the case of $N=3$, $n=6$
and $t=1$, where each big triangle corresponds to a subdivided simplex
$S$. We see that the entire simplex is subdivided once according to
the standard chromatic subdivision, with the $1$-simplices
corresponding to the boundary of the original simplex labeled
according to $C_1(1,2,3)$. The internal $2$-simplex is labeled using
$4,5,6$. In general, we first subdivide the entire simplex once
according to the standard chromatic subdivision. By our induction
hypothesis, we already know how to solve $N-1$ process renaming with
$f(N-1,t)$ available names in time $t$. This solution corresponds to
the symmetrically labeled non-uniform subdivision $C_{N-2}(1,2,3, \ldots,
f(N-1,t))$. We continue subdividing the subcomplex spanned by the
external vertices so that eventually the subcomplex corresponding to
each $(N-2)$-face of $S$ is subdivided and labeled according to
$C_{N-2}( 1, \ldots, f(N-1,t))$. 

We now label the $N$ internal vertices of the complex as
follows. There are $f(N,t)-f(N-1,t) = N+1-t > 2$ unused names. We
label the $N-(N+1-t) +1 = t$ vertices with the lowest process ids
$f(N-1,t)+1$, and we label the remaining vertices in increasing order
using the names $f(N-1,t)+2, \ldots, f(N,t)$ such that the process
with the largest id, $\vv_{N-1}$, gets the label $f(N,t)$. Denote the
simplex spanned by the $t$ vertices labeled with $f(N-1,t)+1$ as
$T$. We subdivide and label $T$ according to 
%GUNNAR: it cannot be $C_{t-1}(f(N-1,t)+1, 2t-2,2t-1, .. , 2,3)$, 
% since in the case of a C_1 subdivision of the internal of a 4 process
% 3 dimensional complex, we use just the two highest names 4 and 5
% of those used on the outer faces so I think it should be something liek:
$C_{t-1}(f(N-1,t)+1, f(N-1,t)-1,f(N-1,t), .. ,f(N-1,t)-(2t-1),f(N-1,t)-(2t-2))$, 
and induce this subdivision onto the rest of the
subdivided 
% note its a complex not a simplex here
complex by replacing $T$ with the labeled subdivision of
$T$ and starring this with all vertices in the complex that were
connected to the $T$ before the replacement. This concludes the
construction of the labeled subdivided complex $C_{N-1}(1,2,3, \ldots,
f(N,t))$, which corresponds to a protocol that uses time $t$ and
$f(N,t)$ names, as required.

Note that, at each step, the labeling of internal vertices is based
solely on comparing process ids. This guarantees that the labelings
used in the proof are symmetric, as required.
\end{proof}


