Mutex-Based De-anonymization of an Anonymous Read/Write Memory - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Mutex-Based De-anonymization of an Anonymous Read/Write Memory

Résumé

Anonymous shared memory is a memory in which processes use different names for the same shared read/write register. As an example, a shared register named A by a process p and a shared register named B by another process q can correspond to the very same register X, and similarly for the names B at p and A at q which can correspond to the same register Y = X. Hence, there is a permanent disagreement on the register names among the processes. This new notion of anonymity was recently introduced by G. Taubenfeld (PODC 2017), who presented several memory-anonymous algorithms and impossibility results. This paper introduces a new problem, that consists in "de-anonymizing" an anonymous shared memory. To this end, it presents an algorithm that, starting with a shared memory made up of m anonymous read/write atomic registers (i.e., there is no a priori agreement on their names), allows each process to compute a local addressing mapping, such that all the processes agree on the names of each register. The proposed construction is based on an underlying deadlock-free mutex algorithm for n ≥ 2 processes (recently proposed in a paper co-authored by some of the authors of this paper), and consequently inherits its necessary and sufficient condition on the size m of the anonymous memory, namely m must belong to the set M (n) = {m : such that ∀ ℓ : 1 < ℓ ≤ n : gcd(ℓ, m) = 1} \ {1}. This algorithm, which is also symmetric in the sense process identities can only be compared by equality, requires the participation of all the processes; hence it can be part of the system initialization. Last but not least, the proposed algorithm has a noteworthy first-class property, namely, its simplicity.
Fichier principal
Vignette du fichier
Mutex-based-desanonymization-NETYS-2019-Final.pdf (188.81 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02445119 , version 1 (19-02-2020)

Identifiants

Citer

Emmanuel Godard, Damien Imbs, Michel Raynal, Gadi Taubenfeld. Mutex-Based De-anonymization of an Anonymous Read/Write Memory. NETYS 2019 - 7th International Conference on Networked Systems, Jun 2019, Marrakech, Morocco. pp.311-326, ⟨10.1007/978-3-030-31277-0_21⟩. ⟨hal-02445119⟩
104 Consultations
122 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More