TY - JOUR
T1 - Mutual exclusion in fully anonymous shared memory systems
AU - Raynal, Michel
AU - Taubenfeld, Gadi
N1 - Publisher Copyright:
© 2020 Elsevier B.V.
PY - 2020/6
Y1 - 2020/6
N2 - Process anonymity has been studied for a long time. Memory anonymity is more recent. In an anonymous memory system, there is no a priori agreement among the processes on the names of the shared registers. As an example, a shared register named A by a process p and a shared register named B by another process q may correspond to the very same register X, while the same name C may correspond to different register names for the processes p and q, and this remains unknown to the processes. This article introduces the full anonymous model, namely a model in which both the processes and the registers are anonymous. A fundamental question is then “is this model meaningful?”, which can be translated as “can non-trivial fundamental problems be solved in such a very weak computing model?” This article answers this question positively. More precisely, it presents a deadlock-free mutual exclusion algorithm in such a fully anonymous model where the anonymous registers are read/modify/write registers. This algorithm assumes that m (the number of shared registers) and n (the number of processes) are such that m is relatively prime with all the integers ℓ∈{1,...,n}. Combined with a previous result (PODC 2019) on mutual exclusion in memory anonymous (but not process anonymous) systems, it follows that this condition is both necessary and sufficient for the existence of such an algorithm in fully anonymous systems. As far as we know, this is the first time full anonymity is considered, and where a non-trivial concurrency-related problem is solved in such a very strong anonymity context.
AB - Process anonymity has been studied for a long time. Memory anonymity is more recent. In an anonymous memory system, there is no a priori agreement among the processes on the names of the shared registers. As an example, a shared register named A by a process p and a shared register named B by another process q may correspond to the very same register X, while the same name C may correspond to different register names for the processes p and q, and this remains unknown to the processes. This article introduces the full anonymous model, namely a model in which both the processes and the registers are anonymous. A fundamental question is then “is this model meaningful?”, which can be translated as “can non-trivial fundamental problems be solved in such a very weak computing model?” This article answers this question positively. More precisely, it presents a deadlock-free mutual exclusion algorithm in such a fully anonymous model where the anonymous registers are read/modify/write registers. This algorithm assumes that m (the number of shared registers) and n (the number of processes) are such that m is relatively prime with all the integers ℓ∈{1,...,n}. Combined with a previous result (PODC 2019) on mutual exclusion in memory anonymous (but not process anonymous) systems, it follows that this condition is both necessary and sufficient for the existence of such an algorithm in fully anonymous systems. As far as we know, this is the first time full anonymity is considered, and where a non-trivial concurrency-related problem is solved in such a very strong anonymity context.
KW - Anonymous memory
KW - Anonymous processes
KW - Distributed computing
KW - Mutual exclusion
UR - http://www.scopus.com/inward/record.url?scp=85079876711&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2020.105938
DO - 10.1016/j.ipl.2020.105938
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:85079876711
SN - 0020-0190
VL - 158
JO - Information Processing Letters
JF - Information Processing Letters
M1 - 105938
ER -