When and How Process Groups Can Be Used to Reduce the Renaming Space

Considering the

M

-renaming problem and process groups, this paper investigates the following question: Is there a relation between the number of groups and the size of the new name space

M

? This question can be rephrased as follows: Can the initial partitioning of the processes into

m

groups allows the size of the renaming space

M

to be reduced, and if yes, how much?

This paper answers the previous questions. Let

n

denote the number of processes. Assuming that the processes are initially partitioned into

m

 = 

n

 − ℓ non-empty groups, such that each process knows only its identity and its group number, the paper first presents a wait-free

M

-renaming algorithm whose size of the new name space is

M

 = 

n

 + 2ℓ − 1. For

$\frac{n}{2} < m \leq n-1$

(i.e.

$1\leq \ell < \frac{n}{2}$

), we have

M

 < 2

n

 − 1, which shows that, when the number of groups is greater than

$\frac{n}{2}$

, groups allow to circumvent the renaming lower bound in read/write systems. Then, on the lower bound size, the paper shows that there are pairs of values (

n

,

m

) such that there is no read/write wait-free

M

-renaming algorithm for which

M

 ≤ 2

n

 − 2. This impossibility result breaks our hope to have a renaming algorithm providing a new name space whose size would decrease “regularly” as the number of groups increases from 1 to

n

. Finally, the paper considers the case where each group includes at least

s

processes. This algorithm shows that, when

m

is such that

$\frac{n}{s+1}< m < \frac{n}{s}$

, there is an

M

-renaming algorithm where

M

 = 3

n

 − (

s

 + 1)

m

 − 1 = 

n

(2 − 

s

) + (

s

 + 1)ℓ − 1. Hence, the paper leaves open the following question: For any

n

and

s

 = 1, does the predicate

$m > \frac{n}{2}$

define a threshold on the number of groups which allows the 2

n

 − 2 lower bound on the renaming space size to be bypassed?