Adaptive and Efficient Algorithms for Lattice Agreement and Renaming.
In a shared-memory system, n independent asynchronous processes, with distinct names in the range {0, ..., N-1}, communicate by reading and writing to shared registers. An algorithm is wait-free if a process completes its execution regardless of the behavior of other processes. This paper considers wait-free algorithms whose complexity adjusts to the level of contention in the system: An algorithm is adaptive (to total contention) if its step complexity depends only on the actual number of active processes, k; this number is unknown in advance and may change in different executions of the algorithm.Adaptive algorithms are presented for two important decision problems, lattice agreement and (6k-1)-renaming; the step complexity of both algorithms is O(k log k). An interesting component of the (6k-1)-renaming algorithm is an O(N) algorithm for (2k-1)-renaming; this improves on the best previously known (2k-1)-renaming algorithm, which has O(Nnk) step complexity.The efficient renaming algorithm can be modified into an O(N) implementation of atomic snapshots using dynamic single-writer multi-reader registers. The best known implementations of atomic snapshots have step complexity O(N log N) using static single-writer multi-reader registers, and O(N) using multi-writer multi-reader registers.
Introduction
. An asynchronous shared-memory system contains n processes
running at arbitrary speeds and communicating by reading from and writing to shared
registers; processes have distinct names in the range In a wait-free
algorithm, a process terminates in a finite number of steps, even if other processes
are very slow, or even stop taking steps completely.
The step complexity of many wait-algorithms depends on N ; for example, collecting
up-to-date information from all processes typically requires to read an array
indexed with processes' names. Real distributed systems need to accommodate a large
number of processes, i.e., N is large, while often only a small number of processes take
part in the computation. For such systems, step complexity depending on n or N is
undesirable; it is preferable to have step complexity which adjusts to the number of
processes participating in the algorithm.
An algorithm is adaptive (to total contention) if its step complexity depends
only on the total number of processes participating in the algorithm, denoted k; k is
unknown in advance and it may change in different executions of the algorithm. The
step complexity of an adaptive algorithm adjusts to the number of active processes:
It is constant if a single process participates in the algorithm, and it gradually grows
as the number of active processes increases.
A weaker guarantee is provided by range-independent algorithms whose step complexity
depends only on n, the maximal number of processes; clearly, n is fixed for all
executions. 1 The advantage of range-independent algorithms is quite restricted: They
require a priori knowledge of n, which is often difficult to determine; moreover, their
extended abstract of this paper appeared in proceedings of the 17th ACM Symposium on
Principles of Distributed Computing (June 1998), pp. 277-286.
2 Department of Computer Science, The Technion, Haifa 32000, Israel (hagit@cs.technion.ac.il,
leonf@cs.technion.ac.il). Supported by the fund for the promotion of research at the Technion.
1 Moir and Anderson [27] use the term "fast", which conflicts with other papers [3, 25].
2 Attiya and Fouren
(Algorithm
union [23]
O(k log
lattice agreement
(Algorithm
)-renaming [27]
(Algorithm
O(k log
(Algorithm
1)-renaming
(Algorithm
1)-renaming
O(n log n)
(Algorithm
1)-renaming
O(N)
Fig. 1. The algorithms presented in this paper; double boxes indicate the main results.
step complexity is not optimal when the actual number of participating processes is
much lower than the upper bound. Yet, as we show, they can be useful tools in the
construction of adaptive algorithms.
This paper presents adaptive wait-free algorithms for lattice agreement and re-
naming, using only read and write operations. Along the way, we improve the step
complexity of non-adaptive algorithms for renaming. Figure 1 depicts the algorithms
presented in this paper.
In the one-shot M -renaming problem [10], processes are required to choose distinct
names in a range of size M (k), for some bounded function M . This paper does
not consider the more general long-lived renaming problem [9], in which processes repeatedly
acquire and release names. Adaptive renaming can serve as an intermediate
step in adaptive algorithms for other problems [9, 26, 27, 28]: The new names replace
processes' original names, making the step complexity depend only on the number of
active processes. Our algorithms employ this technique, as well as [6, 7].
An efficient adaptive algorithm for renaming could not be derived from known
algorithms: The best previously known algorithm for renaming with linear name
space [18] has O(Nnk) step complexity, yielding O(k 3 ) step complexity (at best) if
it can be made adaptive. Thus, we first present an (2k \Gamma 1)-renaming algorithm
with O(N ) step complexity, which is neither adaptive nor range-independent. This
algorithm is based on a new "shrinking network" construction, which we consider to
be the novel algorithmic contribution of our paper.
The new linear renaming algorithm is employed in a range-independent algorithm
for 1)-renaming with O(n log n) step complexity. Processes start with an
adaptive O(k 2 )-renaming algorithm whose step complexity is O(k); this is a simple
modification of the range-independent renaming algorithm of Moir and Anderson [27].
Then, processes reduce the range of names in O(logn) iterations; each iteration uses
our new linear renaming algorithm.
The range-independent renaming algorithm is used to construct an adaptive (6k \Gamma
1)-renaming algorithm with O(k log complexity. In this algorithm, processes
are partitioned into O(logk) disjoint sets according to views obtained from an adaptive
lattice agreement algorithm (described below). This partition bounds the number
of processes in each set, and allows them to employ a range-independent (2k \Gamma 1)-
Adaptive Lattice Agreement and Renaming 3
renaming algorithm designed for this bound. Different sets use disjoint name spaces;
no coordination between the sets is required.
In the lattice agreement problem [15], processes obtain comparable (by contain-
ment) subsets of the set of active processes. A wait-free lattice agreement algorithm
can be turned into a wait-free implementation of an atomic snapshot object, with
O(n) additional read/write operations [15]. Atomic snapshot objects allow processes
to get instantaneous global views ("snapshots") of the shared memory and thus, they
simplify the design of wait-free algorithms.
The step complexity of our adaptive algorithm for lattice agreement is O(k log k).
In this algorithm, processes first obtain names in a range of size O(k 2 ) using the
simple algorithm with O(k) step complexity. Based on its reduced name, a process
enters an adaptive variant of the tree used in the lattice agreement algorithm of Inoue
et al. [23].


Appendix

C describes how the shrinking network is modified to get a lattice
agreement algorithm with O(N ) step complexity, using dynamic single-writer single-reader
registers; this gives an implementation of atomic snapshots with the same
complexity. Previous implementations of atomic snapshots had either O(N log N )
step complexity using static single-writer multi-reader registers [16], or O(N ) step
complexity using multi-writer multi-reader registers [23].
The renaming problem was introduced and solved by Attiya et al. [10] for the
message-passing model; Bar-Noy and Dolev [17] solved the problem in the shared-memory
model. Burns and Peterson [19] considered the l-assignment problem-
dynamic allocation of l distinct resources to processes. They present a wait-free
l-assignment algorithm which assumes l  is the number of processes
trying to acquire a resource. All these algorithms have exponential step complexity
[21]. Borowsky and Gafni [18] present an algorithm for one-shot (2k \Gamma 1)-renaming
using O(Nnk) read/write operations.
Anderson and Moir [9] define long-lived renaming and present range-independent
algorithms for one-shot and long-lived renaming; their algorithms use test&set op-
erations. Moir and Anderson [27] introduced a building block, later called a split-
ter, and employ it in range-independent algorithms for long-lived renaming, using
read/write operations. Moir and Garay [28, 26] give a range-independent long-lived
O(kn)-renaming algorithm, using only read/write operations. By combining with a
long-lived 1)-renaming algorithm [19] they obtain a range-independent long-lived
1)-renaming algorithm; its step complexity is dominated by the exponential step
complexity of Burns and Peterson's algorithm.
Herlihy and Shavit [22] show that one-shot renaming requires names. This
implies that our range-independent renaming algorithm provides an optimal name
space. The name space provided by our adaptive renaming algorithm is not optimal
it is linear in the number of active processes.
Following the original publication of our paper [12], Afek and Merritt [4] used our
algorithms to obtain an adaptive wait-free (2k \Gamma 1)-renaming algorithm, with O(k 2 )
step complexity.
In another paper [13], we present an adaptive collect algorithm with O(k) step
complexity and derive adaptive algorithms for atomic snapshots, immediate snapshots
and 1)-renaming. That paper emphasizes the modular use of a collect operation
to make known algorithms adaptive; the algorithms have higher step complexity than
those presented here.
Our algorithms adapt to the total number of participating processes, that is, if a
4 Attiya and Fouren
process ever performs a step then it influences the step complexity of the algorithm
throughout the execution. More useful are algorithms which adapt to the current contention
and whose step complexity decreases when processes stop participating. Afek,
Dauber and Touitou [3] present implementations of long-lived objects which adapt to
the current contention; they use load-linked and store-conditional operations. Recent
papers present algorithms for long-lived renaming [2, 14], collect [6] and snapshots [7]
which adapt to the current contention using only read/write operations.
Lamport [25] suggests a mutual exclusion algorithm which requires a constant
number of steps when a single process wishes to enter the critical section, using
read/write operations; when several processes compete for the critical section, the
step complexity depends on the range of names. Alur and Taubenfeld [8] show that
this behavior is inherent for mutual exclusion algorithms. Choy and Singh [20] present
mutual exclusion algorithms whose time complexity-the time between consecutive
entries to the critical section-is O(k), using only read/write operations. Afek, Stupp
and Touitou [6] use an adaptive collect algorithm to derive an adaptive version of
the Bakery algorithm [24]; they present another mutual execlusion algorithm in [5].
Recently, Attiya and Bortnikov [11] presented a mutual exclusion algorithm whose
time complexity is O(log k); this algorithm employs an unbalanced tournament tree
with the same structure as our adaptive lattice agreement tree.
2. Preliminaries.
2.1. The Model. In the shared-memory model, processes
by applying operations on shared objects. A process p i is modeled as a (possibly
infinite) state machine; process p i has a distinct name id
The shared objects considered in this paper are atomic read/write registers, accessed
by read and write operations. A read(R) operation does not change the state of
R, and returns the current value stored in R; a write(v,R) operation changes the state
of R to v. A multi-writer multi-reader register allows any process to perform read and
operations. A single-writer multi-reader register allows only a single process to
perform write operations, and any process to perform read operation. A single-writer
multi-reader register is dynamic if the identity of the single process writing to the
register varies in different executions; otherwise, it is static.
An event is a computation step by a single process; the process determines the
operation to perform according to its state, and its next state according to its state
and the value returned by the operation. Computations in the system are captured
as sequences of events. An execution ff is a (finite or infinite) sequence of events
is the process performing the event OE r , then
it applies a read or a write operation to a single register and changes its state according
to its transition function. There are no constraints on the interleaving of events by
different processes, reflecting the assumption that processes are asynchronous and
there is no bound on their relative speeds.
Consider an execution ff of some algorithm A. For process is the
number of read/write operations p i performs in ff. The step complexity of A in ff,
denoted step(A; ff), is the maximum of step(A; ff; process is
active in ff if it takes a step in ff, that is, step(A; ff; denotes the number
of active processes in ff.
Algorithm A is range-independent if there is a function f : N 7! N such that in
every execution ff of A, step(A; ff)  f(n). Namely, the step complexity of A in every
execution is bounded by a function of the total number of processes (which is known
in advance); it does not depend on the range of the initial names.
Adaptive Lattice Agreement and Renaming 5[0][1]
[6]
diagonal
Fig. 2. The grid used for O(k 2 )-renaming (depicted for
Algorithm A is adaptive (to total contention) if there is a function f : N 7! N such
that in every execution ff of A, step(A; ff)  f(k(ff)). Namely, the step complexity of
A in ff is bounded by a function of the number of active processes in ff. Clearly, the
number of active processes is not known a priori.
A wait-free algorithm guarantees that every process completes its computation in
a finite number of steps, regardless of the behavior of other processes. Since k(ff) is
bounded (by n) it follows that adaptive algorithms are wait-free.
2.2. Problems. The M -renaming problem [10] requires processes to choose distinct
names in a range that depends only on the number of active processes. Namely,
there is a function M : N 7! N such that in every execution ff, processes output
distinct names in the range 1g.
In the lattice agreement problem [15], every process p i outputs V i a subset of the
active processes (e.q., a view) such that the following conditions hold:
are comparable (either V
and j.
2.3. Simple O(k 2 )-Renaming in O(k) Operations. The first step in our algorithms
is a simple adaptive O(k 2 )-renaming algorithm. This algorithm reduces the
range of names to depend only on the number of active processes; later stages use
these distinct names, without sacrificing the adaptiveness. We describe this algorithm
first since it employed in both adaptive algorithms presented in this paper.
The basic building block of this algorithm is the splitter of Moir and Anderson [27].
A process executing a splitter obtains down, right or stop. At most one process
obtains stop and when a single process executes the splitter it obtains stop; when
two or more processes execute the splitter, not all of them obtain the same value. In
this way, the set of processes accessing the splitter is "split" into smaller subsets.
As in [27], splitters are arranged in a grid of size n \Theta n (Figure 2). A process
starts at the upper left corner of the grid; the splitters direct the process either to
continue (moving right or down in the grid), or to obtain the number associated with
the current splitter. The grid spreads the processes so that each process eventually
stops in a distinct splitter.
The difference between the algorithm of Moir and Anderson [27] and our algorithm
is that they number splitters by by rows, while we number splitters by diagonals.
Splitter (i; j), in row i and column j, 0

Figure

shows our numbering; the numbering of Moir and
Anderson appears in square brackets.
6 Attiya and Fouren
Algorithm 1 Adaptive k(k 1)=2-renaming.
Procedure Adaptive k(k
private i, j: integer, initially 0 // row and column indices
private move: fdown; right; stopg, initially down // direction
1. while ( move 6= stop ) do
2. move := Splitter[i; j]() // execute splitter in grid position (i;
3. if ( move increase row
4. if ( move = right ) then j++ // increase column
5. return((i name based on the current splitter
Procedure Splitter[i; j] // from Moir and Anderson [27]
shared initially ?
shared Y[i; j]: Boolean, initially false
1. X[i; j] := id
2. if ( Y[i; j] ) then return(right)
3. else Y[i; j] := true
4. if ( X[i;
5. else return(down)
Algorithm 1 presents pseudocode for the grid and for a splitter. 2
We say that splitter (i; steps away from splitter (0; 0), the top left
corner of the grid. As shown in [27, Section 3.1], if k processes access the grid then
each process stops after O(k) operations in a distinct splitter which is at most k \Gamma 1
steps away from (0; 0). A simple counting argument shows that these splitters have
numbers in the range 1g.
Theorem 2.1. Algorithm 1 solves k(k 1)=2-renaming with O(k) step complexity

3. 1)-Renaming in O(N ) Operations. As explained in the introduction,
the step complexity of adaptive renaming depends on a new linear renaming algorithm,
which is neither range-independent nor adaptive.
The algorithm is organized as a network of reflectors. A reflector has two distinguished
entrances; a process accessing the reflector changes the direction of its movement
if another process accessed the reflector, depending on the entrance through
which it entered the reflector.
The network consists of N columns, numbered from left to right
(see

Figure

3). Column
\Gammac, from top to bottom. Process q with name c starts at the topmost
reflector of column c and descends through column c, until it sees another process
accessing the same reflector. Then, q moves left to right towards column
outputs the row on which it exits column N \Gamma 1.
For column c, S c\Gamma1 is the set of processes starting in columns 1. The
main property of the network is that processes in S c\Gamma1 enter column c on distinct
rows among the lowest 2jS ones. Therefore, processes in S c\Gamma1 do not access
the same reflectors in column c (or larger); they may interfere only with the single
process descending through column c.
Algorithms declare private variables only if their usage in not obvious, or their initial value is
important.
Adaptive Lattice Agreement and Renaming 7
Process q descends through column c until it accesses a reflector in row r through
which a process in S c\Gamma1 has passed; then, q moves to column c remaining in row
r. If process p 2 S c\Gamma1 accesses a reflector which q has passed, then p moves one row
up to column c a reflector which q did not pass, then p moves one
row down to column c+ 1. Therefore, processes in S c\Gamma1 which enter column c on rows
move one row up; processes in S c\Gamma1 which enter column c on rows ! r, move
one row down. Process q leaves on one of the free rows between the rows occupied
by these two subsets of S
fqg leave
column c on distinct rows. Since the new names of the processes are the rows on
which they leave the network, they output distinct names.
The interaction of processes in column c guarantees that processes in S c\Gamma1 move
to upper rows in column c is active; at most two additional rows are
occupied (Figure 5(b)). If q is not active, then processes leave column c exactly on
the same number of rows as they enter (Figure 5(a)). Thus, an active process causes
at most two rows to be occupied; if there are k active processes, then they leave the
network on the lowest rows.
More formally, a reflector has two entrances, in 0 and in 1 , two lower exits, down 0
and down 1 , and two upper exits, up 0 and up 1 . A process entering the reflector on
entrance in i leaves the reflector only on exits up i or down i (see top left corner of

Figure

3). If a single process enters the reflector then it must leave on a lower exit,
and at most one process leaves on a lower exit; it is possible that two processes
entering the reflector will leave on upper exits. A reflector is easily implemented with
two Boolean registers (see Algorithm 2).
The reflectors of column c, denoted are connected
as follows:
- The upper exit up 0 of S[c; r] is connected to entrance in 0 of S[c
- The upper exit up 1 of S[c; r] is connected to entrance in 0 of S[c
- The lower exit down 0 of S[c; r] is connected to entrance in 0 of S[c
- The lower exit down 1 of a reflector S[c; r] is connected to entrance in 1 of
reflector lowest reflector of column c),
then it is connected to entrance in 0 of reflector S[c
In Algorithm 2, a process with name c starts on entrance in 1 of the upper reflector of
column c; it descends through column c (leaving on exit down 1 ) until it sees another
process or it reaches the bottom of the column. At this point, the process leaves on
exit up 1 to the next column, and moves towards column in each column y,
it enters exactly one reflector on entrance in 0 ; it leaves on exit up 0 if it sees another
process, or on exit down 0 , otherwise.
Suppose that p j enters the reflector on entrance in i , i 2 f0; 1g, and no process
enters the reflector on entrance in 1\Gammai . Since no process writes to R 1\Gammai , p j reads false
from R 1\Gammai and leaves the reflector on the lower exit, down i . This implies the following
lemma:
Lemma 3.1. If a single process enters a reflector, then it leaves on a lower exit.
Similar arguments are used in the proof of the next lemma:
Lemma 3.2. If a single process enters a reflector on in 0 and a single process
enters the reflector on in 1 , then at most one process leaves the reflector on a lower
exit.
Proof. Assume that p i enters the reflector on in 0 and p j enters the reflector on in 1 .
If both processes read true from R 1 and R 0 , then by the algorithm, exit(p i
and the lemma holds. Otherwise, without loss of generality, p i reads
8 Attiya and Fouren
A reflector.
in 0
in 1 up 0
Fig. 3. The network of reflectors for (2k \Gamma 1)-renaming (depicted for
false from R 1 . Since p i reads false from R 1 , p j writes to R 1 in Line 1 after p i
reads R 1 at Line 2. Therefore, p j reads R 0 in Line 2 after p i writes to R 0 in Line 1.
Consequently, obtains true from R 0 and by the algorithm, exit(p
proves the lemma.
Recall that S c contains the active processes starting on columns
every process c) be the value of the local variable row before p i
accesses the first reflector in column c + 1. The next lemma shows that processes exit
a column on distinct rows.
Lemma 3.3. For every pair of processes
Proof. The proof is by induction on the column c. In the base case, the
lemma trivially holds since only one process may access a reflector in column 0.
For the induction step, suppose that the lemma holds for column c  0; there are
two cases:
Adaptive Lattice Agreement and Renaming 9
Algorithm 1)-renaming.
Procedure shrink(name renaming algorithm
private col, row: integer, initially name // start on top reflector of column name
1. while ( name ) do // descend through column name
2. exit := reflector[row,col](1) // enter on in 1
3. if (
4. else row\Gamma\Gamma //
5. if ( row ! \Gammacol ) then col++ // reached the lowest reflector in column
6. while do // move towards column
7. exit := reflector[row; col](0) // enter on in 0
8. if (
9. else col++; row\Gamma\Gamma; //
10. return(row +N );
Procedure reflector(entrance r : 0,1)
2. if ( R
3. else return(up r )
Case 1: If no process starts on column c + 1, then by the algorithm, no reflector
in column c+1 is accessed on in 1 . By Lemma 3.1, every process p i 2 S c leaves column
. By the algorithm, we have

Figure

4(a)) and the lemma holds by the induction hypothesis.
Case 2: Suppose that process q starts on column c + 1. Let S[c
the last reflector accessed by q in column c + 1. That is, q leaves reflectors S[c
does not access any of the reflectors
By Lemma 3.2, every process p i 2 S c which enters column c + 1 on row r
higher, exits column c + 1 on up 0 , and we have:
By Lemma 3.1, every process p i 2 S c which enters column c+1 on row r lower,
exits column c + 1 on down 0 , and we have:
Now consider process q. By the algorithm, q leaves column c 1 either on exit
down 1 of the lowest reflector in the column, S[c 1)], or on exit up 1 of a
reflector
If q leaves reflector S[c+1; \Gamma(c+1)] on down 1 (Figure 4(b)), then by the algorithm,
If there is a process
(a) (b) (c)
Fig. 4. Illustration for the proof of Lemma 3.3-column c + 1.
If q leaves reflector S[c then by the algorithm,
. By Lemma 3.2, there is a process p j 2 S c which accesses S[c+1; r 0 ];
that is, row(p . By the algorithm
ae
leaves on down 0
The induction hypothesis and the above equations imply that in all cases, row(p
1), for every pair of processes
Therefore, processes exit the network on different rows and hence, obtain distinct
names. The next lemma shows that processes in S c leave column c on the lowest
rows.
Lemma 3.4. For every process
Proof. The proof is by induction on c. In the base case, there is a process
i such that id since no process accesses
reflector S[0; 0] on in 0 . Therefore, by the algorithm, we have row(p
the lemma holds.
For the induction step, suppose that the lemma holds for column c  0; there are
two cases:
Case 1: If no process starts on column c + 1, then no process accesses reflectors
in column c +1 on entrance in 1 (Figure 5(a)). Therefore, by Lemma 3.1, each process
By the induction hypothesis
Also, since jS c+1
The lemma follows from these inequalities.
Case 2: Suppose that process q starts on column c + 1. By the induction hypoth-
esis, processes from S c access only the lowest 2jS c reflectors in column c+1. Since
no process accesses the upper reflectors S[c
on in 0 , by Lemma 3.1, q accesses these reflectors until it reaches a reflector S[c+1; r 0 ]
Adaptive Lattice Agreement and Renaming 11
(a) (b)
Fig. 5. Illustration for the proof of Lemma 3.4-column c + 1.
accessed by another process, or until it reaches the lowest reflector S[c
in the column (Figure 5(b)). Therefore, q leaves column c 1 either on exit down 1 of
reflector 1)] or on exit up 1 of a reflector S[c
1. By the algorithm, this implies
(1)
According to the algorithm, for each process
ae
Together with the induction hypothesis, this implies
(2)
Also,
The lemma follows from inequalities (1), (2) and (3).
Lemma 3.4 implies that processes leave the network on rows
2. Since jS N the names chosen in Line 10 are in the range
Process at most 2id reflectors in column id j , and exactly one
reflector in each column id Each reflector requires a constant number
of operations, implying the next theorem:
Theorem 3.5. Algorithm 2 solves (2k \Gamma 1)-renaming with step complexity
O(N ).
The network consists of O(N 2 ) reflectors; each reflector is implemented with two
registers. Register R i of a reflector is written only by a process entering the reflector
on entrance in i . Entrance in 1 of a reflector is accessed only by the single process
starting on this column, and entrance in 0 is accessed by at most one process (by
Lemma 3.3). Therefore, we use O(N 2 ) dynamic single-writer single-reader registers.
12 Attiya and Fouren
shrink[1]
shrink[2] shrink[3]
shrink[7]
shrink[6]
shrink[5]
shrink[4]
1)=2-renaming (Algorithm 1)
Fig. 6. The range-independent algorithm for (2k \Gamma 1)-renaming (depicted for
Algorithm 3 Range-independent (2k \Gamma 1)-renaming for n processes.
Procedure indRenamingn ()
1. temp-name := Adaptive k(k
2. is the height of the tree
3. side := temp-name mod 2
4. temp-name := 0
5. while ( '  1 ) do
6. temp-name := shrink['](temp-name
7. side := ' mod 2
8. ' := b'=2c
9. return(temp-name)
4. (2k \Gamma1)-Renaming in O(n log n) Operations. A range-independent (2k \Gamma1)-
renaming can be obtained by combining adaptive O(k 2 )-renaming and non-adaptive
1)-renaming. First, the names are reduced into a range of size O(n 2 ) (Algo-
rithm 1); these names are used to enter the shrinking network of Algorithm 2, which
reduces them into a range of size (2k \Gamma1). The shrinking network is started with names
of size O(n 2 ), and hence, the step complexity of this simple algorithm is O(n 2 ). The
algorithm presented in this section obtains O(n log n) step complexity by reducing
the name space gradually in O(log n) iterations. To do so, distinct copies of shrink
(Algorithm are associated with the vertices of a complete binary tree of height
Each copy of shrink is designed for names
in a range of size 4n \Gamma 2; that is, it employs a network with
A process starts Algorithm 3 by acquiring a name using O(k 2 )-renaming; this
name determines from which leaf to start. The process performs the shrinking network
associated with each vertex v on the path from the leaf to the root, starting at a column
which is determined by the name obtained at the previous vertex: If it ascends from
the left subtree of v, then it starts at one of the first 2n \Gamma 1 columns of the network;
otherwise, it starts at one of the last columns. The process outputs the name
obtained at the root.
The vertices of the tree are numbered in BFS order (Figure 4): The root is
numbered vertex v is numbered ', then its left child is numbered 2', and its right
child is numbered 2'+ 1. The copy of Algorithm 2 associated with a vertex numbered
' is denoted shrink['].
Lemma 4.1. For every vertex v, processes executing shrink[v] obtain distinct
temporary names in the range
Proof. The proof is by induction on d, the height of v. In the base case,
Adaptive Lattice Agreement and Renaming 13
Algorithm 4 Adaptive (6k \Gamma 1)-renaming.
1. V := AdaptiveLA() // Algorithm 5, presented below
2. r := dlog jVje
3. temp-name := indRenaming 2 r () // Algorithm 3
4. if (
5. else return(temp-name
After executing Algorithm 1, processes get distinct names in the range
1g. Therefore, at most one process accesses v from the left executing shrink[v]
with temporary name 0, and at most one process accesses v from the right, executing
shrink[v] with temporary name 1. Thus, they execute shrink[v]
with different temporary names in the range 3g. Theorem 3.5 implies
they obtain distinct names in the range f0; 1; 2g and therefore, the lemma holds when
For the induction step, assume the lemma holds for vertices at height d, and let
v be a vertex at height d + 1. By the induction hypothesis and by the algorithm,
accessing v from the left child have distinct temporary names in the range
accessing v from the right child have distinct names in
the range f2n 3g. Thus, processes execute shrink[v] with distinct
names in the range distinct names in the range
2g, by Theorem 3.5.
Therefore, processes obtain distinct names in the range completing
shrink at the root. A process performs shrink in n) vertices of
the tree, and each vertex requires O(n) operations (Theorem 3.5). This implies the
following theorem:
Theorem 4.2. Algorithm 3 solves (2k \Gamma 1)-renaming with O(n log n) step complexity

5. 1)-Renaming in O(k log Operations. In our adaptive (6k \Gamma 1)-
renaming algorithm, a process estimates the number of active processes and performs
a copy of the range-independent (2k \Gamma 1)-renaming algorithm (Algorithm designed
for this number. Processes may have different estimates of k, the number of active
processes, and perform different copies of Algorithm 3. Instead of consolidating the
names obtained in the different copies, disjoint name spaces are allocated to the copies.
The number of active processes is estimated by the size of a view obtained from
lattice agreement; since views are comparable, the estimate is within a constant factor
(see Lemma 5.1).
In Algorithm 4, process p i belongs to a set S j if the size of its view is in
For views obtained in lattice agreement, this partition guarantees that jS j j  2 j , for
moreover, if the number of active processes is k, then jS
dlog ke. There are dlog ne copies of the Algorithm 3, denoted indRenaming 2
indRenaming 2 dlog ne . Processes in S j perform indRenaming 2 j , designed for 2 j processes,
and obtain names in a range of size 2jS j 1. The name spaces for S ne do
not overlap, and their size is linear k (Figure 7).
Lemma 5.1. If the views of processes in a set S satisfy the comparability and
self-inclusion properties of lattice agreement, and the size of a view is at most k, then
jSj  k.
Proof. Assume V is the view with maximal size in S. Let V i be the view of some
process S. The self-inclusion property implies that and the comparability
14 Attiya and Fouren
adaptive lattice agreement
renaming
range-independent
Fig. 7. Adaptive (6k \Gamma 1)-renaming.
property implies that V i ' V . Therefore, S ' V , implying that jSj  jV j  k.
By the algorithm, if process p i is in S j then jV i j  2 j . Lemma 5.1 implies the
next lemma:
Lemma 5.2. If there are k active processes, then jS
For every process since the views contain only active processes.
Therefore, which implies the next lemma:
Lemma 5.3. If there are k active processes, then jS
By Lemma 5.2, at most 2 j processes invoke indRenaming 2 j . Therefore, process p i
invoking indRenaming 2 j obtains temp-name 2g, by Theorem 4.2. By
the algorithm, p i returns temp-name
The set of names returned by processes performing indRenaming 2 j is denoted
NameSpace the next lemma follows from the algorithm:
Lemma 5.4. (1) NameSpace i
NameSpace
dlog ne.
(2)
Lemma 5.5. If there are k active processes, then they return distinct names in
the range
Proof. If two active processes, p i and p j , execute the same copy of indRenaming,
then they obtain distinct names by Theorem 4.2; otherwise, they obtain distinct
names, by Lemma 5.4(1).
By Lemma 5.3, processes invoke indRenaming 2 j only if 0  j  dlog ke. By
Lemma 5.4(2), processes invoking indRenaming
in the range 2g. By Theorem 4.2, a process p i invoking the last non-empty
copy indRenaming 2 dlog ke obtains a temporary name in the range
By the algorithm, p i returns a name in the range f2 dlog
3 There are dlog ke+1 names of the form 2 which are not used. Therefore,
the names obtained in the algorithm can be mapped into a name space of size 6k \Gamma dlog 2.
Adaptive Lattice Agreement and Renaming 15
Thus, the output names are in a range whose size is not greater than 2 dlog
the correctness of the algorithm follows from
Lemma 5.5.
If there are k active processes, then each process performs AdaptiveLA (pre-
sented in the next section) in O(k log operations. By Lemma 5.3, only copies
of indRenaming for less than 2k processes are invoked. Therefore, a process completes
indRenaming in O(k log operations.
Theorem 5.6. Algorithm 4 solves (6k \Gamma 1)-renaming with O(k log

The upper bound on the size of the name space, 6k \Gamma 1, is tight for Algorithm 4.
Assume that all processes executing lattice agreement obtain the maximal view (with
size and access indRenaming 2 dlog ke . The processes leave the range
2g unused (since it is unknown whether the previous copies of indRenaming are empty
or not) and return names in the range f2 dlog 2g. If k is not an
integral power of 2, then the output names are in a range of size  2 log k+2
is an integral power of 2, then the output names are in a range of size
Merritt (private communication) noted that the names can be reduced by partitioning
the active processes into sets of size a for an integer a ? 2.
Active processes are partitioned into sets S
adaptiveRenaming a j designed for a j participants and obtain new names in a range of
size 2jS j 1. As in our algorithm, when k processes are active, adaptiveRenaming a j
is accessed only for 0  j  dlog a ke. Processes accessing copies adaptiveRenaming a j ,
names in a space of size
P dlog a
2 a log a k+1 \Gamma1
which tends to 2k, when a ! 1. Processes accessing the last
non-empty copy, adaptiveRenaming a dlog a new names in a range of size 2k \Gamma 1.
Thus, the size of the total name space is
6. Lattice Agreement in O(k log Operations. Our lattice agreement algorithm
is based on the algorithm of Inoue et al. [23]. In their algorithm, each process
starts at a distinct leaf (based on its name) of a complete binary tree with height
climbs up the tree to the root. At each vertex on the path, it performs
a procedure which merges together two sets of views, each set containing only
comparable views; this procedure is called union. At the leaf, the process uses its own
name as input to union; at the inner vertices, it uses the view obtained in the previous
vertex as input to union. The process outputs the view it obtains at the root.
Specifically, union takes two parameters, an input view V and an integer side 2
f0; 1g, and returns an output view; its properties are specified by the next lemma [23,
Lemma 6]:
Lemma 6.1. If the input views of processes invoking union with are
comparable and satisfy the self-inclusion property, and similarly for the input views
of processes invoking union with
(1) the output views of processes exiting union are comparable, and
(2) the output view of a process exiting union contains its input view.


Appendix

A describes union in detail, and explains the next lemma:
Lemma 6.2. The step complexity of union is O(k).
Our adaptive algorithm uses an unbalanced binary tree T r defined inductively as
follows. T 0 has a root v 0 with a single left child (Figure 8(a)). For r  0, suppose T r
Attiya and Fouren22 37
29 vr
Cr
(a) T0
(b) Tr+1
Fig. 8. The unbalanced binary tree used in the adaptive lattice agreement algorithm.
is defined with an identified vertex v r , which is the last vertex in an in-order traversal
of T r ; notice that v r does not have a right child in T r . T r+1 is obtained by inserting
a new vertex v r+1 as the right child of v r , and inserting a complete binary tree C r+1
of height r as the left subtree of v r+1 (Figure 8(b)). By the construction, v r+1 is
the last vertex in an in-order traversal of T r+1 .
The vertices of the tree are numbered as follows: The root is numbered 1; if a
vertex is numbered ', then its left child is numbered 2', and its right child is numbered

Figure

8).
By the construction, the leaves of T r are the leaves of the complete binary subtrees
. Therefore, the total number of leaves in T r is
The following simple lemma, proved in Appendix B, states some properties of T r .
Lemma 6.3. Let w be the i-th leaf of T r , 1  i  counting from left to
right. Then
(1) the depth of w is 2blog ic
(2) w is numbered 2 d
Algorithm 5 uses T 2 log n\Gamma1 , which has n leaves. 4 A process starts the algorithm
by obtaining a new name in a range of size k(k + 1)=2 (using Algorithm 1).
This name determines the leaf at which the process starts to climb up the tree: A
process with a new name x i starts the algorithm at the x i th leaf of the tree, counting
from left to right. Since k(k
leaves for temporary names in a range of size k(k + 1)=2. By Lemma 6.3, the x i th
leaf is numbered 2 d
As in [23], a distinct copy of union is associated with each inner vertex of the tree.
A process performs copies of union associated with the vertices along its path to the
root, and returns the view obtained at the root.
Simple induction on the distance of a vertex v from the leaves shows that the
views obtained by processes executing union at v satisfy the comparability and self-
inclusion properties. In the base case, v is a leaf and the claim is trivial since a single
process starts at each leaf; the induction step follows immediately from Lemma 6.1.
Hence, the views obtained at the root have the lattice agreement properties.
If there are k active processes, process p i gets a unique name x
4 For simplicity, we assume n is a power of 2.
Adaptive Lattice Agreement and Renaming 17
Algorithm 5 Adaptive lattice agreement.
Procedure AdaptiveLA()
1. temp-name := Adaptive k(k
2. d := blog temp-namec
3. temp-name // the leaf corresponding to temp-name
4. V := fp i g // the input is the process's name
5. while ( '  1 ) do
6. side := ' mod 2 // calculate side
7. ' := b'=2c // calculate father
8. V := union['](V; side)
9. return(V)
1)=2g (Line 1) and by Lemma 6.3(2), starts in a leaf ' of depth 2blog x
Therefore, p i accesses at most 2blog x
vertices. At each vertex, the execution of union requires O(k) operations (Lemma 6.2).
Thus, the total step complexity of the algorithm is O(k log k), implying the following
theorem:
Theorem 6.4. Algorithm 5 solves lattice agreement with O(k log

7. Discussion. This work presents adaptive wait-free algorithms, whose step
complexity depends only on the number of active processes, for lattice agreement and
1)-renaming in the read/write asynchronous shared-memory model; the step
complexity of both algorithms is O(k log k).
Clearly, the complexities of our algorithms-the number of steps, the number
and the size of registers used-can be improved. For example, an algorithm for O(k)-
renaming with O(k) step complexity would immediately yield a lattice agreement
algorithm with the same step complexity. Also it would be interesting to see if ideas
from our efficient algorithms can improve the complexities of algorithms which adapt
to the current contention [2, 6].

Acknowledgments

:. We thank Yehuda Afek and Eli Gafni for helpful discussions,
Yossi Levanoni for comments on an earlier version of the paper, and the reviewers for
many suggestions on how to improve the organization and presentation.



--R

Atomic snapshots of shared memory






Results about fast mutual exclusion
Using local-spin k-exclusion algorithms to improve wait-free object implementation
Renaming in an asynchronous environment
Adaptive and efficient mutual exclusion
Adaptive wait-free algorithms for lattice agreement and renaming


Atomic snapshots using lattice agreement
Atomic snapshots in O(n log n) operations
A partial equivalence between shared-memory and message-passing in an asynchronous fail-stop distributed environment

The ambiguity of choosing
Adaptive solutions to the mutual exclusion problem
Exponential examples for two renaming algorithms.
The topological structure of asynchronous computability

A new solution of Dijkstra's concurrent programming problem



Fast long-lived renaming improved and simplified
--TR

--CTR
Michel Raynal, Wait-free computing: an introductory lecture, Future Generation Computer Systems, v.21 n.5, p.655-663, May 2005
Hagit Attiya , Faith Ellen Fich , Yaniv Kaplan, Lower bounds for adaptive collect and related objects, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
Wojciech Golab , Danny Hendler , Philipp Woelfel, An O(1) RMRs leader election algorithm, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
Hagit Attiya , Arie Fouren , Eli Gafni, An adaptive collect algorithm with applications, Distributed Computing, v.15 n.2, p.87-96, April 2002
Hagit Attiya , Arie Fouren, Algorithms adapting to point contention, Journal of the ACM (JACM), v.50 n.4, p.444-468, July
atomic read/write registers;lattice agreement;shared-memory systems;wait-free computation;renaming;atomic snapshots