A Theory-Oriented Introduction to Wait-freeSynchronization

Based on the Adaptive Renaming ProblemSergio RAJSBAUM? Michel RAYNAL†

? Instituto de Matematicas, Universidad Nacional Autonoma de MexicoCiudad Universitaria, D.F. 04510, Mexico (supported by PAPIIT and PAPIME UNAM Projects)

† Senior Member of the Institut Universitaire de FranceIRISA, Campus de Beaulieu, 35042 Rennes Cedex, Francerajsbaum@math.unam.mx raynal@irisa.fr

Abstract—The recent deployment of multiprocessors (such asmulticores) as the mainstream computing platform has given riseto a new concurrent programming impetus. In such a context itbecomes extremely important to be able to design shared objectsthat can cope with the net effect of asynchrony and processcrashes.

This paper is a theory-oriented introduction to wait-freesynchronization for such systems. It uses the adaptive renamingproblem as a paradigm to explain the difficulties and subtleties ofsynchronization in presence of process crashes. Renaming is oneof the most famous coordination problems studied in distributedcomputability. It consists in assigning new names to processes insuch a way that no two processes obtain the same new name andthe new name space be as small as possible. The paper visits theproblem by presenting three solutions.

This paper, that has a strong survey/short tutorial flavor,can consequently be considered as an introduction to both therenaming problem and progress conditions for synchronizationin presence of process crashes in the context of multiprocessorsystems.

Index Terms—Adaptive distributed algorithm, Asynchronousshared memory system, Concurrent programming, Crash fail-ures, Obstruction-freedom, Multicore systems, Read/write atomicregister, Recursion, Renaming problem, Shared object, Wait-freedom.

I. INTRODUCTION

a) The challenging advent of a new class of multiproces-sor systems: The speed of light has a limit. When combinedwith other physical and architectural demands, this physicalconstraint places limits on processor clocks: their speed canno longer rise forever. Hence, software performance can nolonger be obtained by increasing CPU frequencies. To face thisnew challenge, manufacturers are investigating and producingwhat they call multicore architectures, i.e. architectures inwhich each chip is made up of several processors that share acommon memory. This constitutes what is called the multicorerevolution [9].

The main challenge with this new class of multiprocessorarchitectures is “how to exploit their power”? How course theold (classical) “multiprocess programming” (multi-threading)methods are an answer to this question. Basically, these

methods provide the programmer with the concept of a lock.According to the abstraction level considered, this lock can bea semaphore object, a monitor object [14], or the programmer’sfavorite synchronization object (e.g., a serializer [13]).

Unfortunately, traditional lock-based solutions have inherentdrawbacks. On one side, if the set of data whose accessesare controlled by a single lock is too large (large grain), theparallelism can be drastically reduced. On another side, thesolutions where a lock is associated with each datum (finegrain) are error-prone (possible presence of subtle deadlocks),difficult to design, master and prove correct. In other words,providing the application programmers with locks is far frombeing the panacea when one has to produce correct andefficient multiprocess programs. Interestingly enough, this newclass of multiprocessor architectures have (in some sense) rangthe revival of concurrent programming [21].

b) Progress conditions suited to crash-prone environ-ments: A major problem when using locks lies in the net effectof asynchrony and process crashes. Namely, as a process is not“visible” by the other processes when it does not access theshared memory, there is no way for a process to know whetheranother process has crashed or is only very slow. This becomescritical when accesses to shred objects are protected by mutualexclusion locks. More specifically, if the process crashes whileholding a lock on an object, that object is locked forever asno other process can know if the process holding the lock isalive or not. This makes locks harmful or even irrelevant forsome classes of applications. The crash of a process can entailnon-faulty processes to block forever even if locks are usedcorrectly. Basically, locks are suited to failure-free systems forwhich the notion of deadlock-freedom and starvation-freedomare well understood and well-defined [22].

The previous observation has motivated the definition ofprogress conditions suited to crash-prone systems. The oldestand most famous one is wait-freedom. This condition statesthat if a process does not crash, it has to always terminate itsoperation on an object, whatever the behavior of the otherprocesses is (that can be very slow or even crashed) [8].

Wait-freedom can consequently be seen as starvation-freedomdespite process crashes.

Wait-freedom is the strongest possible progress condition.Obstruction-freedom is a weaker progress condition whosedefinition is concurrency-oriented. An obstruction-free imple-mentation of an object guarantees that a process that invokesan operation on that object -and does not crash- returnsfrom that invocation if it runs “long enough” in isolation1

[10]. While both wait-freedom and obstruction-freedom areprogress conditions whose definition is independent of thefailure pattern, the second one guarantees progress only in“favorable” concurrency patterns. k-Obstruction-freedom isa generalization of obstruction-freedom where “concurrency-free” is replaced by “concurrency limited to k processes” (1-obstruction-freedom is obstruction-freedom) [23].

c) The renaming problem: Renaming is among the basicproblems that lie at the core of computability in asynchronousdistributed systems prone to process crashes [2]. Each of then processes of the system has an initial name taken from avery large domain [1..N ] (n << N ). Initially a process knowsonly its name, the value n and the fact that no two processeshave the same initial name. The processes have to cooperateto choose new names from a name space [1..M ] such thatM << N and no two processes have the same new name.Given an integer M , the problem is called M-renaming.

A renaming algorithm is adaptive if the size of the newname space depends only on the number p of processes thatask for a new name (and not on the total number n ofprocesses). Several adaptive algorithms have been designedsuch that the size of the new name space is M = 2p−1. Thismeans that if “today” p′ processes acquire new names, theirnew names belong to the interval [1..2p′ − 1]. If “tomorrow”p′′ additional processes acquire new names, these processeswill have their new names in the interval [1..2p − 1] wherep = p′ + p′′. An important theoretical result associated withadaptive renaming in asynchronous read/write systems is thefact that M = 2p − 1 is the lower bound on the size of thenew name space [11].

d) Content of the paper: The paper is algorithm-orientedand theory-oriented. It is made up of VI sections. Section IIpresents the computation model and introduces base defini-tions. Then Section III presents an adaptive renaming algo-rithm due to Attiya and Welch [3]. This classical algorithm issimple but can be time-inefficient in some particular scenarios.

Section IV presents a variant of a recursion-based adaptivealgorithm due to Gafni and Rajsbaum [6]. Interestingly, thetime complexity of this algorithm is polynomial with respectto n (the total number of processes), namely, O(n2). Anotherinteresting feature of this algorithm lies in its recursive for-mulation which makes its design and its proof relatively easy.Both previous algorithms, use only read/write operations, andenjoy two noteworthy properties.

1The words “long enough” are due to asynchrony. They are used to capturethe arbitrary duration required by a process to execute an operation on anobject; intuitively, it means that a process is not required to run in isolationfor an infinite time.

Both previous algorithms (a) are wait-free (with means thatany non-faulty process always terminates its renaming oper-ation, i.e., whatever the behavior of the other processes) and(b) ensure a renaming space M with an optimal size, namelyM = 2p−1 (where p is the number of participating processes).Considering a progress condition weaker than wait-freedom,that is called k-obstruction-freedom, Section V presents acorresponding algorithm due to Imbs and Raynal [15]. Theweakening of the progress condition allows the renaming spaceto be reduced to M = min(p+k−1, 2p−1). This value of M isoptimal for the k-obstruction-freedom progress condition. Thisalgorithm shows an interesting tradeoff relating the strength ofthe progress condition that the implementation of an adaptiverenaming object has to ensure and the size of the new namespace: the stronger the progress condition, the larger the newname space (that is upper bounded by 2p+1). Finally, SectionVI concludes the paper.

II. COMPUTATION MODEL AND BASE DEFINITIONS

A. Computation model

e) Process model: The system consists of n processesthat we denote p1, . . . , pn. The integer i is the index of pi.Each process pi has an initial name old namei such thatold namei ∈ [1..N ] (N is arbitrarily large). Moreover, aprocess does not know the initial names of the other processes;it only knows that no two processes have the same initial name.A process can crash. Given an execution, a process that crashesis said to be faulty. Otherwise, it is correct in that execution.It is assumed that at most n − 1 processes may crash. Eachprocess progresses at its own speed, which means that thesystem is asynchronous.

f) Notation: A process can have local registers. Suchregisters are denoted with lowercase letters with the processindex appearing as a subscript (e.g., propi is a local registerof pi). The notation ⊥ is used to denote a default value.Uppercase letters are used to denote shared objects.

g) Communication among processes: Processes commu-nicate by accessing two types of objects: arrays of size n ofatomic one-writer/multi-reader (denoted 1WnR) registers andsnapshot objects.

As far as an array X[1..n] is concerned, “one-writer” meansthat only pi can write X[i], while any process pj can read thewhole array. Such a read, denoted aa← X[1..n] where aa isa local variable of the reader, is not atomic. The reader readsasynchronously all entries of the array in any order.

Snapshot objects have been introduced in [1]. A snap-shot object X is a size n array of 1WnR atomic registersthat provides each process pi with a write operation and asnapshot operation denoted X.snapshot(). The former allowspi to assign a value v to the one-writer register X[i] (itis consequently denoted X[i] ← v). The latter operation,X.snapshot(), returns to pi the current value of the array Xas it if has been executed atomically. This means that theimportant point here is that all write and snapshot operationsappear as if they have been executed one after the other in anorder that respects their physical occurrence order (a snapshot

object is linearizable [12]). A snapshot object can be wait-freebuilt on top of atomic read/write registers [1].

B. Adaptive renamingh) Definition: The adaptive renaming problem has been

informally stated in the introduction [2]. Each process pi hasan initial name old namei such that no two processes havethe same initial name. These initial names belong to a set1, . . . , N such that n << N . Let new name() be the (only)operation provided by an adaptive M -renaming object, i.e.,an object that allows processes to obtain new distinct namesbelonging to the interval [1..M ]. The behavior of this object(that defines the adaptive M -renaming problem) is definedby the following properties where p denotes the number ofprocesses that invoke new name() during an execution (theset of panticipating processes).• Termination. If a correct process invokes new name() it

returns from that invocation.• Agreement. No two new names are identical.• Adaptivity. A new name belong to [1..M ] where M =

f(p) where f() is a function such that f(p) ≤ f(p+ 1).• Index independence. The behavior of a process is inde-

pendent of its index.The last property states that, if, in a run, a process whose

index is i obtains the new name v, that process would haveobtained the very same new name if its index was j. Thismeans that, from an operational point of view, the indexesdefine an underlying communication infrastructure, namely,an addressing mechanism that can be used only to accessentries of shared arrays. Indexes cannot be used to computenew names.

As already indicated, f(p) = 2p − 1 is the smallest sizefor the new name space that can be attained by any wait-free algorithm in which the processes communicate only byreading and writing a shared memory.

C. Progress conditionsi) Wait-freedom: The wait-freedom progress condition

for adaptive renaming is the one stated previously in thetermination property. A process that invokes new name()and does not crash always returns from that invocation (i.e.,whatever the behavior of the other objects).

j) k-Obstruction-freedom: For k < n, the k-obstruction-freedom progress condition is weaker than wait-freedom (itis the same for k = n). It states that progress is requiredonly when at most k correct processes keep on executingnew name(). Let us observe that it is possible that no processever terminates if no set P of at most k processes execute inisolation for a long enough period. The termination property(progress condition) becomes the following.• Termination. For any subset P of correct processes, with|P | ≤ k, if the processes of P execute new name() inisolation2, each process of P eventually terminates its

2Let us observe that this does not prevent k′ > k correct processes to havestarted executing new name(), as long as k′ − k of them, whatever theirprogress in the code of new name(), stop executing during a “long enough”period.

invocation (and obtains a new name).This means that if the concurrency degree becomes smaller

or equal to k for “long enough” periods, then all invocationsof new name() by correct processes terminates.

III. SIMPLE WAIT-FREE (2p− 1)-RENAMING

This section presents a simple adaptive M -renaming algo-rithm that provides the participating processes with an optimalnew name space, i.e., M = 2p − 1, when the processes cancooperate through atomic registers only. This algorithm (dueto Attiya and Welch [3]) is an adaptation to asynchronousread/write shared memory systems of a message-passing al-gorithm described in [2].

k) Communication medium: a snapshot object: Theshared memory is made up of a single snapshot objectSTATE . As we have seen this is array of 1WnR atomicregisters denoted STATE [1..n] such that STATE [i] can bewritten only by pi and the whole array can be atomically readby pi by invoking STATE .snapshot(). Each atomic registerSTATE [i] is a pair made up of two fields: STATE [i].oldwill contain the initial name of pi, while STATE [i].prop willcontain the last proposal of pi to acquire a new name. Eachentry is initialized to < ⊥,⊥ >.

l) The algorithm: underlying principle and description:The algorithm is described in Figure 1 (code for the processpi). The local register propi contains pi’s current proposalfor a new name. When pi (whose initial name is old namei)invokes new name(), it sets propi to 1 (line 01), and enters awhile loop (lines 02-12). It exits that loop when it has obtaineda new name (statement return(propi) issued at line 06).

The principle that underlies the algorithm is the following. Anew name can be considered as a slot, and processes competeto acquire free slots in the interval of slots [1..2p − 1]. Afterentering the loop, a process pi first updates STATE [i] (line03) in order to announce to all processes its current proposalfor a new name (let us notice that it also implicitly announcesit is competing for a new name).

Then, thanks to the snapshot() operation on the snapshotobject STATE (line 04), pi obtains a consistent view (locallysaved in the array competingi) of the system’s global state.let us notice that this view is consistent because it has beenobtained from an atomic snapshot operation. Then the behaviorof pi depends on the consistent global state of the sharedmemory it has obtained, more precisely on the value of thepredicate ∀ j 6= i : competingi [j].prop 6= propi. We considerboth cases.• Case 1: the predicate is true. This means that no process

pj is competing with pi for the new name propi. In thatcase, pi considers the current value of propi as its newname (line 06).

• Case 2: the predicate is false. This means that severalprocesses are competing to obtain the same new namepropi. So, pi construct a new proposal for a new nameand enters again the loop. This proposal is built from theconsistent global state of the system that pi has obtainedin competingi .

operation new name():(01) propi ← 1;(02) while true do(03) STATE [i]←< old namei, propi >;(04) competingi ← STATE .snapshot();(05) if (∀ j 6= i : competingi [j].prop 6= propi)(06) then return (propi)(07) else let X = competingi [j].prop | (competingi [j].prop 6= ⊥) ∧ (1 ≤ j ≤ n);(08) let free = the increasing sequence 1, 2, . . . from which

the integers in X have been suppressed;(09) let Y = competingi [j].old | (competingi [j].old 6= ⊥) ∧ (1 ≤ j ≤ n);(10) let r = rank of old namei in Y ;(11) propi ← the rth integer in the increasing sequence free(12) end if(13) end while.

Figure 1. A simple read/write wait-free adaptive (2p− 1)-renaming [3] (code for pi)

Set X = competingi [j].prop | (competingi [j].prop 6=⊥) ∧ (1 ≤ j ≤ n) (line 07) contains the proposals(as seen by pi) for new names, while the set Y =competingi [j].old | (competingi [j].old 6= ⊥)∧(1 ≤ j ≤n) (line 09) contains the initial names of the processesthat pi sees as competing for obtaining a new name.The determination of a new proposal by pi is based onthese two sets. First, pi considers the increasing sequence(denoted free) of the integers that are “free” and canconsequently be used to define new name proposals.This is the sequence of positive integers from which theproposals in X have been suppressed (line 08). Then,pi computes its rank r among the processes that (fromits point of view) want to acquire a new name (line09). Finally, given the sequence free and r, pi definesits new name proposal as its rank in this sequence (thisrank is r, i.e., its rank in the set of processes it sees ascompeting processes).

m) Discussion: A proof of this algorithm can be foundin [3]. The proof that no two new names are the same does notdepend on the way the new names are chosen, it depends onlyon the fact that all the STATE .snapshot() operations appearas if they were executed one after the other. The fact that thenew names belong to the interval [1..2p − 1] depends on theway the new names are chosen (lines 09-11).

It is shown in [5] that there are particular scenarios inwhich processes can execute an exponential (with respect ton) number of steps (shared memory accesses). Hence, thesimplicity of this adaptive renaming algorithm is at the priceof a set of runs that are very time-inefficient, albeit very rare.

IV. EFFICIENT RECURSION-BASED RENAMING

This section presents a variant of a wait-free adaptiverenaming algorithm, due to Gafni and Rajsbaum [6], that isboth optimal with respect to the size of the new name space(i.e., as M = 2p − 1) and time-efficient, namely its timecomplexity is O(n2).

One of the noteworthy features of this algorithm is the factthat its design is based on recursion. This allows for a concise

definition of the algorithm and for a relatively simple invariant-based proof of it.

n) Communication medium: atomic 1WnR atomic reg-isters: The processes cooperate through a three-dimensionalarray of size n × (2n − 1) × 2 denoted SM [n..1, 2n −1..1, up, down]. Each element of this array is a vector of natomic 1WnR registers. Hence, SM [x, f, d] is a vector withn entries, and SM [x, f, d][i] is an atomic register that can bewritten only by pi but read by any process pj . For every 4-uple〈x, f, d, i〉, SM [x, f, d][i] is initialized to ⊥.

As far notation are concerned, we have up = 1 = downand down = −1 = up.

o) The algorithm: underlying principle and description:When a process pi wants to acquire a new name it invokesnew name(x,first , dir) with x = n, first = 1 and dir =up. The parameter x is the recursion parameter and will takevalues n (main call), n−1, n−2, etc. until process pi decides anew name. Its smallest possible value is 1. Hence, differentlyfrom sequential recursion where recursion is usually on thesize and the structure of the data that is visited, here recursionis on the number of processes.

The value up is used to indicate that the concerned pro-cesses are renaming “from left to right” (as far as the newnames are concerned) while down is used to indicate that theconcerned processes are renaming “from right to left”. Moreprecisely, when pi invokes new name(x, f, up), it considersthe renaming space [f..f + 2x − 2] to obtain a new name,while it considers the space [f − (2x− 2)..first] if it invokesnew name(x, f, down). Hence, a process pi considers initiallythe renaming space [1..2n−1], and then (as far pi is concerned)this space will shrink at each recursive call (going up or goingdown) until pi obtains a new name.

The algorithm is presented in Figure 2. When, it invokesnew name(x,first , dir), process pi first writes its old namein SM [x,first , dir][i] (line 01) and reads (asynchronously)the size n array of atomic registers SM [x,first , dir][1..n].This array is used to allow the processes that invokenew name(x,first , dir) to “synchronize” to obtain newnames. More precisely, all processes that compete for newnames in [first..first + 2x − 2] if dir = up, or [first −(2x − 2)..first] if dir = down, deposit their old name

in SM [x,first , dir] (line 01). Then, according to the value(saved in the local array competingi) that it has read(asynchronously) from the vector SM [x,first , dir][1..n] (line02), the behavior of the set X of processes that invokenew name(x,first , dir) is the behavior of a splitter (seebelow).

It is important to notice that, for each triple (x, f, d),all invocations new name(x, f , d) coordinate their respectivebehavior with the help of the size n array of atomic registersSM [x, f, d][1..n]. The local variable competingi is an arrayof n local registers such that competingi[j] contains either⊥ or old namej , the initial name of pj (line 01). The fol-lowing notations are used. |competingi| denotes the numberof entries that are different from ⊥, while max(competingi)is the greatest initial name it contains. As a process pideposits its initial name in SM [x,first , dir][i] before readingSM [x,first , dir][1..n], it follows that competingi contains atleast one non-⊥ entry when it is read by pi.

Let us observe that if p processes participate in the renam-ing, their main call new name(n, 1, up) will systematicallyentail the call new name(n − 1, 1, up), etc., until the callnew name(p, 1, up). Then, the behavior of a participatingprocess pi depends on both the concurrency pattern and thefailure pattern.

algorithm new name(x,first , dir):% x (n ≥ x ≥ 1) is the recursion parameter %

(01) SM [x,first , dir][i]← old namei;(02) competingi ← SM [x,first , dir][1..n];(03) if |competingi| = x(04) then last← first + dir(2x− 2);(05) if old namei = max(competingi)(06) then res← last

(07) else res← new name(x− 1, last + dir, dir)(08) end if(09) else res← new name(x− 1,first , dir)(10) end if;(11) return(res).

Figure 2. Recursive adaptive renaming algorithm (code for pi) [6]

Considering the at most x processes that invokenew name(x,first , dir), the splitter behavior (adapted to re-naming) is defined by the following properties.• At most x − 1 processes invoke new name(x −

1,first , up) (line 09). Hence these processes will obtainnew names (going up) in [first..first+ 2x− 2].

• At most x− 1 processes invoke new name(x− 1, last +dir, dir) (line 07) where last = first + dir(2x− 2) (line04). Hence these processes will obtain their new namesin a renaming space starting at last + 1 and going fromleft to right if dir = up, or starting at last − 1 andgoing from right to left if dir = down. Let us observethat the value last ± 1 is considered as starting namebecause the slot last is reserved for the new name ofthe process (if any) that stops during its invocation ofnew name(x,first , dir) (see the next item).

• At most one process “stops”, i.e., defines its new nameas last = first + dir(2x − 2) (lines 04 and 06). Let

us observe that the only process pk that can stop isthe one such that old namek has the greatest valuein SM [x, first, dir][1..n] (line 05) that contains thenexactly x old names (line 03).p) Discussion: A sketch of proof of a variant of the

previous algorithm is given in [6]. It is easy to see that thetime complexity is O(n2). This follows from the fact thatwriting old namei at line 01 costs one shared memory access,reading SM [x, f, d][1..n] costs n shared memory accesses anda process executes at most n recursive calls.

V. k-OBSTRUCTION-FREE RENAMING

This section presents an adaptive M -renaming algorithmwhere M = min(p + k − 1, 2p − 1) that guarantees that thecorrect processes that invokes new name() always return fromtheir invocation if there are long enough periods during whichat most k correct processes execute in isolation.

This algorithm, due to Imbs and Raynal [15], can be seenas an “appropriate modification” of the algorithm describedin Section III that aims at replacing the “wait-freedom”requirement by the k-obstruction-freedom” requirement.

q) Communication medium: atomic 1WnR registers anda snapshot object: The processes cooperate through two arraysof atomic 1WnR registers denoted OLDNAMES [1..n], andLEVEL[1..n], and a snapshot object denoted NAMES .• Register OLDNAMES [i], that is initialized to ⊥, is

used by pi to store its identity old namei. HenceOLDNAMES [i] 6= ⊥ means that pi participates in therenaming.

• Register LEVEL[i] is initialized to 0. In order to obtain anew name, the processes progress asynchronously from alevel (starting from 1) to the next one. LEVEL[i] containsthe current level attained by process pi. As we will see,if during a long enough period at most k processes takesteps, they will stabilize at the same level and obtain newnames.

• NAMES [1..n] is a snapshot object initialized to[⊥, . . . ,⊥]. NAMES [i] contains the new name that pitries to acquire. When pi returns from new name(),NAMES [i] contains its new name.r) The algorithm: underlying principle and description:

The algorithm defined in Figure 3 describes the behavior ofa process pi. When it invokes new name(old namei), pideposits old namei in OLDNAMES [i] and proceeds fromlevel 0 to level 1. The local variable propi contains pi’s currentproposal for a new name. Its initial value is ⊥. Then, pi entersa loop (lines 03-21) that it will exit at line 06 with its newname.

Each time it starts a new execution of the loop body, pi firstposts its current name proposal in NAMES [i] and reads (witha NAMES .snapshot() invocation) the values of all currentproposals (line 04). If its current proposal propi is not ⊥ andno other process has proposed the same new name (line 05), pidefines its new name as the value of propi and exits the loop(line 06). Otherwise, there is a conflict: several processes are

operation new name():(01) propi ← ⊥; my leveli ← 1;(02) OLDNAMES [i]← old namei; LEVEL[i]← my leveli;(03) repeat forever(04) NAMES [i]← propi; namesi ← NAMES .snapshot();(05) if

((propi 6= ⊥) ∧ (∀j 6= i : namesi[j] 6= propi)

)(06) then return(propi)(07) else levelsi ← LEVEL[1..n]; highest leveli ← max(levelsi [j]);(08) if (my leveli < highest leveli )(09) then my leveli ← highest leveli ; LEVEL[i]← my leveli(10) else oldnamesi ← OLDNAMES [1..n];(11) competingi ← oldnamesi[j] | levelsi [j] = highest leveli;(12) if (|competingi | > k)(13) then my leveli ← highest leveli + 1; LEVEL[i]← my leveli(14) else let X = namesi [j] | namesi [j] 6= ⊥;(15) let free = the increasing sequence 1, 2, 3, . . . from which

the integers in X have been suppressed;(16) let r = rank of old namei in competingi ;(17) propi ← the rth integer in the increasing sequence free(18) end if(19) end if(20) end if(21) end repeat.

Figure 3. k-Obstruction-free adaptive M -renaming with M = min(2p− 1, p + k − 1) [15]

trying to acquire the same new name propi. In that case, pienters lines 08-19 to solve this conflict. These lines constitutethe core of the algorithm.

In case of conflict, pi first reads asynchronously all entriesof LEVEL[1..n] and computes the highest level attained(line 07) highest leveli. If its current level is smaller thanhighest leveli, pi jumps to that level, indicates it by writingLEVEL[i] (lines 08-09) and proceeds to the next loop itera-tion.

If its current level is equal to highest leveli , pi computesthe set of processes it is competing with in order to acquire anew name, namely the set competingi (lines 10-11). Those arethe processes whose level is equal to highest leveli. Then,the behavior of pi depends on the size of the set competingi(predicate at line 12).

• If |competingi| > k, there are too many processes com-peting when we consider k-obstruction-freedom. Processpi progresses then to the next level and proceeds to thenext loop iteration (line 13).

• If |competingi| ≤ k, pi selects a new name proposalbefore proceeding to the next iteration. This selectionis similar to what is done in the adaptive renamingalgorithm described in Section III. As defined at lines14-15, free denotes the list of names that are currentlyavailable. Accordingly, pi defines its new name proposalas the rth value in the list free where r is its rank in the setof (at most k) competing processes (hence, 1 ≤ r ≤ k).

s) Discussion: A proof of this algorithm can be found in[15] where it is also shown that this algorithm is optimal withrespect to the new name space, i.e., there is no k-obstruction-free adaptive M -renaming algorithm with M < min(p+ k −1, 2p− 1).

VI. CONCLUSION

This paper was focused on the notions of wait-freedom andk-obstruction-freedom, two of the most important progressconditions investigated up to now (other progress conditionsare investigated in [16], [17]).These progress conditions seemparticularly relevant when one is interested in solving synchro-nization problems on multicore computers where processesmay crash.

These notions have been illustrated with the help of theadaptive renaming problem. Although the algorithms presentedare not trivial, they are simple enough to give non-expertreaders a flavor of the wait-freedom and obstruction-freedomnotions. Moreover, the paper has shown that efficiency andrecursion are not antagonistic concepts in the context ofsynchronization.

REFERENCES

[1] Afek Y., Attiya H., Dolev D., Gafni E., Merritt M. and Shavit N., AtomicSnapshots of Shared Memory. Journal of the ACM, 40(4):873-890, 1993.

[2] Attiya H., Bar-Noy A., Dolev D., Peleg D. and Reischuk R., Renamingin an Asynchronous Environment. Journal of the ACM, 37(3):524-548,1990.

[3] Attiya H. and Welch J., Distributed Computing: Fundamentals, Simula-tions and Advanced Topics, (2d Edition), Wiley-Interscience, 414 pages,2004.

[4] Borowsky E. and Gafni E., Immediate Atomic Snapshots and FastRenaming. Proc. 12th ACM Symposium on Principles of DistributedComputing (PODC’93), pp. 41-51, 1993.

[5] Fouren A., Exponential Examples of two Renaming Algorithms. Tech-nion Tech Report, 1999.

[6] Gafni E. and Rajsbaum S., Recursion in Distributed Computing. 12thInt’l Symposium on Stabilization, Safety, and Security of DistributedSystems (SSS’10), Springer Verlag LNCS #6366, pp. 362-376, 2010.

[7] Gafni E., Raynal M. and Travers C., Test&set, Adaptive Renaming andSet Agreement: a Guided Visit to Asynchronous Computability. 26thIEEE Symposium on Reliable Distributed Systems (SRDS’07), pp. 93-102, 2007.

[8] Herlihy M.P., Wait-Free Synchronization. ACM Transactions on Progr.Languages and Systems, 13(1):124-149, 1991.

[9] Herlihy M.P. and Luchangco V., Distributed Computing and the Multi-core Revolution. SIGACT News, 39(1): 62-72, 2008.

[10] Herlihy M.P., Luchangco V. and Moir M., Obstruction-free synchro-nization: double-ended queues as an example. Proc. 23th Int’l IEEEConference on Distributed Computing Systems (ICDCS’03), pp. 522-529, 2003.

[11] Herlihy M.P. and Shavit N., The Topological Structure of AsynchronousComputability. JACM, 46(6):858-923, 1999.

[12] Herlihy M.P. and Wing J.M., Linearizability: a Correctness Conditionfor Concurrent Objects. ACM Transactions on Programming Languagesand Systems, 12(3):463-492, 1990.

[13] Hewitt C.E. and Atkinson R.R., Specification and Proof Techniques forSerializers. IEEE Transactions on Software Engineering, SE5(1):1-21,1979.

[14] Hoare C.A.R., Monitors: an Operating System Structuring Concept.Comm. of the ACM, 17(10):549-557, 1974.

[15] Imbs D. and Raynal M., On Adaptive Renaming Under EventuallyLimited Contention. 12th Int’l Symposium on Stabilization, Safety, andSecurity of Distributed Systems (SSS’10), Springer Verlag LNCS #6366,pp. 377-387, 2010.

[16] Imbs D. and Raynal M., The x-Wait-freedom Progress Condition. 16thEuropean Conf. on Parallelism (EUROPAR’10), Springer Verlag LNCS#6271, pp. 584-595, 2010.

[17] Imbs D., Raynal M. and Taubenfeld G., On Asymmetric ProgressConditions. Proc. 29th ACM Symposium on Principles of DistributedComputing (PODC’10),pp. 55-64, 2010.

[18] Lamport. L., On Interprocess Communication, Part 1: Models, Part 2:Algorithms. Distr. Computing, 1(2):77-101, 1986.

[19] Mostefaoui A., Raynal M. and Travers C., Exploring Gafni’s ReductionLand: from Ωk to Wait-free Adaptive (2p− d p

ke)-Renaming via k-Set

Agreement. 20th Int’l Symp. on Distr. Computing (DISC’06), SpringerLNCS #4167, pp. 1-15, 2006.

[20] Mostefaoui A., Raynal M. and Travers C., From Renaming to k-SetAgreement. 14th Int’l Colloquium on Structural Information and Com-munication Complexity (SIROCCO’07), Springer Verlag LNCS #4474,pp. 62-76, 2007.

[21] Raynal M., Synchronization is Coming Back, but Is it the Same?Keynote Speech. IEEE 22nd Int’l Conference on Advanced InformationNetworking and Applications (AINA’08), IEEE Society Press, pp. 1-10,2008.

[22] Raynal M., Locks Considered Harmful: a Look at Non-traditionalSynchronization. Proc. 6th Int’l Workshop on Software Technologies forEmbedded and Ubiquitous Systems (SEUS’08), Springer Verlag LNCS#5287, pp. 369-380, 2008.

[23] Taubenfeld G., Contention-Sensitive Data Structure and Algorithms.Proc. 23th Int’l Symposium on Distributed Computing (DISC’09),Springer Verlag LNCS #5805, pp. 157-171, 2009.

APPENDIX

This section shows that the recursive algorithm describedin Figure 2 is correct, i.e., all correct participating processesobtain a new name in the interval [1..2p− 1] (where p is thenumber of participating processes), and no two new names areidentical. Moreover, the process indexes are used only as anaddressing mechanism (index independence).

a) Notation: In the following the sentence “process pistops in SM [x, f, d]” means that pi executes line 06 duringits invocation new name(x, f, d).

b) Remark: The proof is based on a reasoning by induc-tion. This is a direct consequence of the recursive formulationof the algorithm. In that sense the proof provides us with adeeper insight on the way the algorithm works.

Lemma 1: Let 〈x, f, d〉 be a triple such that x ≥ 1and assume that at most x processes invoke the opera-tion new name(x, f, d). When considering these processeswe have the following. At most one process stops inSM [x, f, d] (line 06), at most (x − 1) processes invokenew name(x − 1, f, d) (line 09) and most (x − 1) processesinvoke new name(x− 1, f ′, d) (line 07).

Proof Let u ≤ x be the number of processes that invokenew name(x, f, d). If u < x, it follows that the predicate atline 03 is false for these processes that consequently proceedto line 09 and invoke new name(x− 1, f, d). As u ≤ x− 1,the lemma follows.

Let us now consider the case where x processes invokenew name(x, f, d). We have then the following.• Let y be the number of processes for which the predicate|competingj | = x (line 03) is false when they invokenew name(x, f, d). We have 0 ≤ y < x. It follows fromthe text of the algorithm that these y processes invokenew name(x− 1, f, d) at line 09. As y < x, the lemmafollows for these invocations.

• Let z be the number of processes for which the predicate|competingj | = x (line 03) is true when they invokenew name(x, f, d). We have 1 ≤ z ≤ x and y + z = x.If one of these z processes pk is such that the predicateof line 05 is true (i.e., old namek = max(SM [x, f, d])),then pk executes line 06 and stops inside SM [x, f, d].Let us also notice that this is always the case if x = 1. Ifx > 1, it follows from y+z = x that z−1 < x−1. Then,the other z−1 processes invoke new name(x−1, f ′, d).As z−1 < x−1, the lemma follows for these invocations.If the test of line 05 is false for each of the z processes, itfollows that the process pk that has the greatest old nameamong the x processes that invoke new name(x, f, d), isnecessarily one of the y previous processes. Hence, in thatcase, we have y ≥ 1. As y + z = x, this implies z < x.It then follows that at most z ≤ x − 1 processes invokenew name(x−1, f ′, d), which concludes the proof of thelemma. 2Lemma 1

Lemma 2: Every correct participant decides a new name.Proof As there are at most n participating processes, and eachstarts by invoking new name(n, 1, 1), it follows from Lemma1 that every correct process stops in some SM [x, ∗, ∗] for1 ≤ x ≤ n. It then decides a new name at line 06, whichproves the lemma. 2Lemma 2

Lemma 3: Let p be the number of participating processes.We have M = [1..2p − 1]. Moreover for any pair of partici-pating processes pi and pj we have resi 6= resj .Proof The lemma is trivially true for p = 1 (the single processthat invokes new name(n, 1, 1) obtains the new name 1, if itdoes not crash). A simple case analysis shows that the newnames for p = 2 are a pair in [1..3] (each pair is actuallyassociated with a set of concurrency and failure patterns).

The rest of the proof is by induction on the number of par-ticipating processes. The previous paragraph has establishedthe base cases. Assuming that the lemma is true for all p′ ≤ p(induction assumption), let us show that it is true for p + 1participating processes (induction assumption).

Each of the p+1 processes invoke new name(n, 1, 1). Eachof these invocations entails the invocation of new name(n−1, 1, 1) (line 09), etc., until the invocation new name(p +1, f, d) with f = 1 and d = 1.

• Let Y be the set of processes pj (with |Y | = y) suchthat the predicate |contendingj | = p + 1 (line 03) isfalse. We have 0 ≤ y < p + 1. These processes invokenew name(p, f, d), etc., until new name(y, f, d) and dueto the induction assumption they rename (with distinctnew names) in [f..f +2y− 2], i.e., as f = 1, [1..2y− 1].

• Let Z be the set of processes pj (with |Z| = z) such thatthe predicate |contendingj | = p+1 (line 03) is true. Wehave 1 ≤ z ≤ p+ 1 and y + z = p+ 1. At line 04, eachof these z processes obtain last = f + 2(p + 1) − 2 =f + 2p = 2p+ 1.

– If one of these z processes pk is such thatold namek = max(SM [p + 1, f, d]) (line 05),it stops at SM [p + 1, f, d]) obtaining the nameres = last = f + 2ps = 2p+ 1 (as f = 1).

– If no process stops at SM [p+1, f, d], we have 1 ≤z ≤ p and 1 ≤ y (this is because the process withthe greatest old name is then necessarily a processof Y ).

Hence, the z′ = z ≤ p or z′ = z−1 ≤ p processes that donot stop at SM [p+ 1, f, d], invoke new name(p, last−1, d), etc., until new name(z′, f +2p− 1, d). Due to theinduction assumption, these z′ processes rename (withdistinct new names) in the interval [(f +2p−1)− (2z′−2)..f + 2p− 1] = [2p− (2z′ − 2)..2p].Hence, when considering the y+ z = p+1 processes ofY ∪ Z, the y processes of Y rename with distinct newnames in [1..2y − 1], the z′ processes of Z rename withdistinct names [2p − (2z′ − 2)..2p] and, if z′ + 1 = z,the remaining process of Z obtains the new name 2p+1.The new name space for the whole set processes Y ∪ Zis consequently [1..2p+ 1].It remains to show that a process of Y and a process of Zcannot obtain the same new name. To that end we haveto show that the upper bound 2y − 1 of the new namesof the processes of Y is smaller than the lower bound2p− (2z′ − 2) of the new names of the processes of Z,namely, 2y− 1 < 2p− (2z′ − 2), i.e., 2(y+ z′) < 2(p+1) + 1, which is true because z′ ≤ z and y + z ≤ p+ 1,which concludes the proof of the lemma. 2Lemma 3

Theorem 1: The algorithm described in Figure 2 is anadaptive M -renaming algorithm such that M = 2p−1 (wherep is the number of participating processes).Proof The fact that no two new names are identical and thatthe new name space is [1..2p − 1] is proved in Lemma 3.The fact that any correct participating process decides a newname is proved in Lemma 2. Finally the index independenceproperty follows directly from the text of the algorithm: theprocess indexes are used only in lines 01 and 02 where theyare used to address entries of arrays. 2Theorem 1