The notion of an anonymous shared memory (recently introduced in PODC 2017) considers that processes use different names for the same memory location. Hence, there is permanent disagreement on the location names among processes. In this context, the PODC paper presented -among other results- a symmetric deadlock-free mutual exclusion (mutex) algorithm for two processes and a necessary condition on the size @math of the anonymous memory for the existence of a symmetric deadlock-free mutex algorithm in an @math -process system. This condition states that @math must be greater than @math and belong to the set @math (symmetric means that, while each process has its own identity, process identities can only be compared with equality). The present paper answers several open problems related to symmetric deadlock-free mutual exclusion in an @math -process system ( @math ) where the processes communicate through @math registers. It first presents two algorithms. The first considers that the registers are anonymous read write atomic registers and works for any @math greater than @math and belonging to the set @math . It thus shows that this condition on @math is both necessary and sufficient. The second algorithm considers anonymous read modify write atomic registers. It assumes that @math . These algorithms differ in their design principles and their costs (measured as the number of registers which must contain the identity of a process to allow it to enter the critical section). The paper also shows that the condition @math is necessary for deadlock-free mutex on top of anonymous read modify write atomic registers. It follows that, when @math , @math is a tight characterization of the size of the anonymous shared memory needed to solve deadlock-free mutex, be the anonymous registers read write or read modify write.
This paper originates from the work described in @cite_2 , where the memory-anonymous mutex problem is introduced, and where first results are presented on mutual exclusion in read write memory-anonymous systems, namely a symmetric deadlock-free algorithm for two processes (the notion of symmetric'' is related to the use of process identifiers; it will be defined in ), a theorem stating there is no deadlock-free algorithm if the number of processes is not known, a necessary condition stating that any symmetric deadlock-free mutex algorithm for @math processes, which uses @math read write registers, requires that @math belongs to the set @math (i.e., @math and @math are relatively prime). Let us observe that @math is infinite (among other values, it contains an infinite number of prime numbers).
@cite_2
2030003887
In the renaming task n + 1 processes start with unique input names taken from a large space and must choose unique output names taken from a smaller name space, 0, 1, . . . , K. To rule out trivial solutions, a protocol must be anonymous: the value chosen by a process can depend on its input name and on the execution, but not on the specific process id. showed in 1990 that renaming has a wait-free solution when K ≥ 2n. Several proofs of a lower bound stating that no such protocol exists when K < 2n have been published. We presented in the ACM PODC 2008 conference the following two results. First, we presented the first completely combinatorial lower bound proof stating that no such a protocol exists when K < 2n. This bound holds for infinitely many values of n. Second, for the other values of n, we proved that the lower bound for K < 2n is incorrect, exhibiting a wait-free renaming protocol for K = 2n−1. More precisely, we presented a theorem stating that there exists a wait-free renaming protocol for K < 2n if and only if the set of integers ( n+1 i+1 | 0 i n-1 2 ) are relatively prime. This paper is the first part of the full version of the results presented in the ACM PODC 2008 conference. It includes only the lower bound. Namely, we show here that no protocol for renaming exists when K < 2n, if n is such that ( n+1 i+1 | 0 i n-1 2 ) are not relatively prime. We prove this result using the known equivalence of K-renaming for K = 2n−1 and the weak symmetry breaking task. In this task processes have no input values and the output values are 0 or 1, and it is required that in every execution in which all processes participate, at least one process decides 0 and at least one process decides 1. The full version of the upper bound appears in a companion paper [10].