On Adaptive Renaming under Eventually Limited Contention

The adaptive

M

-renaming problem consists in designing an algorithm that allows a set of

p

 ≤ 

n

participating asynchronous processes (where

n

is the total number of processes) not known in advance to acquire pair-wise different new names in a name space whose size

M

depends on

p

(and not on

n

). Adaptive (2

p

 − 1)-renaming algorithms for read/write shared memory systems have been designed. These algorithms, which are optimal with respect to the value of

M

, consider the wait-freedom progress condition, which means that any correct participant has to acquire a new name whatever the behavior of the other processes (that can be very slow or even crashed).

This paper addresses the design of an adaptive

M

-renaming algorithm when considering the

k

-obstruction-freedom progress condition. This condition, that is weaker than wait-freedom, requires that every correct participating process acquires a new name in all runs where during “long enough periods” at most

k

processes execute steps (

p

-obstruction-freedom and wait-freedom are actually equivalent). The paper presents an optimal adaptive (

p

 + 

k

 − 1)-renaming algorithm and, consequently, contributes to a better understanding of synchronization and concurrency by showing that weakening the liveness condition from wait-freedom to

k

-obstruction-freedom allows the new name space to be reduced from 2

p

 − 1 to min (2

p

 − 1,

p

 + 

k

 − 1). Last but not least, the proposed algorithm is particularly simple, a first class property. This establishes an interesting tradeoff linking progress conditions with the size of the new name space.