Optimal memory-anonymous symmetric deadlock-free mutual exclusion

The notion of an anonymous shared memory, introduced by Taubenfeld in PODC 2017, considers that processes use different names for the same memory location. As an example, a location name A used by a process p and a location name B A used by another process q can correspond to the very same memory location X, and similarly for the names B used by p and A used by q which may (or may not) correspond to the same memory location Y X. In this context, the PODC paper presented a 2-process symmetric deadlock-free mutual exclusion (mutex) algorithm and a necessary condition on the size m of the anonymous memory for the existence of such an n-process algorithm. This condition states that m must be belongs to M(n) {1} where M(n)= {m: : (1) The present paper presents two optimal deadlock-free symmetric mutual exclusion algorithms for n-process systems where communication is through m registers. The first algorithm, which considers anonymous read/write registers, works for any m which is n and belongs to the set M(n). It follows that this condition on m is both necessary and sufficient for symmetric deadlock-free mutual exclusion in this anonymity context, and this algorithm is optimal with respect to m The second algorithm, which considers anonymous read/modify/write atomic registers, works for any m M(n), which is shown to be necessary and sufficient for anonymous read/modify/write registers. It follows that, when m > 1, m M(n) is a tight characterization of the size of the anonymous shared memory needed to solve deadlock-free mutex, be the registers read/write or read/modify/write.