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.
@cite_2: Assuming that there is an a priori agreement between processes on the names of shared memory locations, as done in almost all the publications on shared memory algorithms, is tantamount to assuming that agreement has already been solved at the lower-level. From a theoretical point of view, it is intriguing to figure out how coordination can be achieved without relying on such lower-level agreement. In order to better understand the new model, we have designed new algorithms without relying on such a priori lower-level agreement, and proved space lower bounds and impossibility results for several important problems, such as mutual exclusion, consensus, election and renaming. Using these results, we identify fundamental differences between the standard model where there is a lower-level agreement about the shared register's names and the strictly weaker model where there is no such agreement.
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).