Abstract
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\ne 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\ge 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:~ \text{ such } \text{ that } \forall ~ \ell : 1<\ell \le n:~ \mathsf{{gcd}}(\ell ,m)=1\}\setminus \{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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Peterson’s mutual exclusion algorithm is such a symmetric algorithm [17]. As it requires \(2n-1\) non-anonymous atomic registers, we need to have both \(m\in M(n)\) and \(m\ge 2n-1\).
References
Aigner, M., Ziegler, G.: Proofs from THE BOOK. Springer, Heidelberg (2010). 274 p. ISBN 978-3-642-00856-6
Angluin D.: Local and global properties in networks of processes. In: Proceedings of the 12th Symposium on Theory of Computing (STOC 1980). ACM Press, pp. 82–93 (1980)
Aghazadeh Z., Imbs D., Raynal M., Taubenfeld G., Woelfel P.: Optimal memory-anonymous symmetric deadlock-free mutual exclusion. In: Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), 10 p. ACM Press (2019)
Attiya, H., Gorbach, A., Moran, S.: Computing in totally anonymous asynchronous shared-memory systems. Inf. Comput. 173(2), 162–183 (2002)
Bonnet, F., Raynal, M.: Anonymous asynchronous systems: the case of failure detectors. Distrib. Comput. 26(3), 141–158 (2013)
Bouzid, Z., Raynal, M., Sutra, P.: Anonymous obstruction-free \((n, k)\)-set agreement with \((n-k+1)\) atomic read/write registers. Distrib. Comput. 31(2), 99–117 (2018)
Delporte-Gallet, C., Fauconnier, H., Gafni, E., Lamport, L.: Adaptive register allocation with a linear number of registers. In: Afek, Y. (ed.) DISC 2013. LNCS, vol. 8205, pp. 269–283. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41527-2_19
Dijkstra, E.W.: Solution of a problem in concurrent programming control. Commun. ACM 8(9), 569 (1965)
Dijkstra, E.W.: Some beautiful arguments using mathematical induction. Algorithmica 13(1), 1–8 (1980)
Garg V.K., Ghosh J.: Symmetry in spite of hierarchy. In: Proceedings of the 10th International Conference on Distributed Computing Systems (ICDCS 1990), pp. 4–11. IEEE Computer Press (1990)
Guerraoui, R., Ruppert, E.: Anonymous and fault-tolerant shared-memory computations. Distrib. Comput. 20, 165–177 (2007)
Johnson R.E., Schneider F.B.: Symmetry and similarity in distributed systems. In: Proceedings off the 4th ACM Symposium on Principles of Distributed Computing (PODC 1985), pp. 13–22, ACM Press (1985)
Lamport, L.: On interprocess communication, part I: basic formalism. Distrib. Comput. 1(2), 77–85 (1986)
Navlakha, S., Bar-Joseph, Z.: Algorithms in nature: the convergence of systems biology and computational thinking. Mol. Syst. Biol. 7(546), 1–11 (2011)
Navlakha, S., Bar-Joseph, Z.: Distributed information processing in biological and computational systems. Commun. ACM 58(1), 94–102 (2015)
Perlis, A.J.: Epigrams on programming. ACM SIGPLAN Not. 17(1), 7–13 (1982)
Peterson, G.L.: Myths about the mutual exclusion problem. Inform. Process. Lett. 12(3), 115–116 (1981)
Rashid S., Taubenfeld G., Bar-Joseph Z.: Genome wide epigenetic modifications as a shared memory consensus. In: 6th Workshop on Biological Distributed Algorithms (BDA 2018), London (2018)
Raynal, M.: Concurrent Programming: Algorithms, Principles and Foundations. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-32027-9. 515 p. ISBN 978-3-642-32026-2
Raynal, M.: Fault-Tolerant Message-passing Distributed Systems: An Algorithmic Approach. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-94141-7. 492 p. ISBN 978-3-319-94140-0
Raynal, M., Cao, J.: Anonymity in distributed read/write systems: an introductory survey. In: Podelski, A., Taïani, F. (eds.) NETYS 2018. LNCS, vol. 11028, pp. 122–140. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-05529-5_9
Taubenfeld, G.: Synchronization Algorithms and Concurrent Programming. Pearson Education/Prentice Hall, London (2006). 423 p. ISBN 0-131-97259-6
Taubenfeld G.: Coordination without prior agreement. In: Proceedings of the 36th ACM Symposium on Principles of Distributed Computing (PODC 2017), pp. 325–334. ACM Press (2017)
Yamashita, M., Kameda, T.: Computing on anonymous networks: part I -characterizing the solvable cases. IEEE Trans. Parallel Distrib. Syst. 7(1), 69–89 (1996)
Acknowledgments
This work was partially supported by the French ANR project DESCARTES (16-CE40-0023-03) devoted to layered and modular structures in distributed computing. The authors want to thank the referees for their constructive comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Godard, E., Imbs, D., Raynal, M., Taubenfeld, G. (2019). Mutex-Based De-anonymization of an Anonymous Read/Write Memory. In: Atig, M., Schwarzmann, A. (eds) Networked Systems. NETYS 2019. Lecture Notes in Computer Science(), vol 11704. Springer, Cham. https://doi.org/10.1007/978-3-030-31277-0_21
Download citation
DOI: https://doi.org/10.1007/978-3-030-31277-0_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-31276-3
Online ISBN: 978-3-030-31277-0
eBook Packages: Computer ScienceComputer Science (R0)