Document Open Access Logo

Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms

Authors Bogdan S. Chlebus, Gianluca De Marco, Muhammed Talo

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2017.15.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

Bogdan S. Chlebus
Gianluca De Marco
Muhammed Talo

Cite As Get BibTex

Bogdan S. Chlebus, Gianluca De Marco, and Muhammed Talo. Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.OPODIS.2017.15

Abstract

We consider synchronous distributed systems in which processors communicate by shared read- write variables. Processors are anonymous and do not know their number n. The goal is to assign individual names by all the processors to themselves. We develop algorithms that accomplish this for each of the four cases determined by the following independent properties of the model: concurrently attempting to write distinct values into the same shared memory register either is allowed or not, and the number of shared variables either is a constant or it is unbounded. For each such a case, we give a Monte Carlo algorithm that runs in the optimum expected time and uses the expected number of O(n log n) random bits. All our algorithms produce correct output upon termination with probabilities that are 1−n^{−Ω(1)}, which is best possible when terminating almost surely and using O(n log n) random bits.

Subject Classification

Keywords
  • anonymous processors
  • synchrony
  • shared memory
  • read-write registers
  • naming
  • Monte Carlo algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Rachid Guerraoui. Tight bounds for asynchronous renaming. Journal of the ACM, 61(3):18:1-18:51, 2014. Google Scholar
  2. Dan Alistarh, Hagit Attiya, Seth Gilbert, Andrei Giurgiu, and Rachid Guerraoui. Fast randomized test-and-set and renaming. In Proceedings of the 24th International Symposium on Distributed Computing (DISC), volume 6343 of Lecture Notes in Computer Science, pages 94-108. Springer, 2010. Google Scholar
  3. Dana Angluin. Local and global properties in networks of processors. In Proceedings of the 12th ACM Symposium on Theory of Computing (STOC), pages 82-93, 1980. Google Scholar
  4. James Aspnes, Faith Ellen Fich, and Eric Ruppert. Relationships between broadcast and shared memory in reliable anonymous distributed systems. Distributed Computing, 18(3):209-219, 2006. Google Scholar
  5. James Aspnes, Gauri Shah, and Jatin Shah. Wait-free consensus with infinite arrivals. In Proceedings of the 34th ACM Symposium on Theory of Computing (STOC), pages 524-533, 2002. Google Scholar
  6. Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and Rüdiger Reischuk. Renaming in an asynchronous environment. Journal of the ACM, 37(3):524-548, 1990. Google Scholar
  7. Hagit Attiya, Alla Gorbach, and Shlomo Moran. Computing in totally anonymous asynchronous shared memory systems. Information and Computation, 173(2):162-183, 2002. Google Scholar
  8. Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. John Wiley, 2nd edition, 2004. Google Scholar
  9. Paolo Boldi and Sebastiano Vigna. An effective characterization of computability in anonymous networks. In Proceedings of the 15th International Conference on Distributed Computing (DISC), volume 2180 of Lecture Notes in Computer Science, pages 33-47. Springer, 2001. Google Scholar
  10. François Bonnet and Michel Raynal. The price of anonymity: Optimal consensus despite asynchrony, crash, and anonymity. ACM Transactions on Autonomous and Adaptive Systems, 6(4):23, 2011. Google Scholar
  11. Harry Buhrman, Alessandro Panconesi, Riccardo Silvestri, and Paul Vitanyi. On the importance of having an identity or, is consensus really universal? Distributed Computing, 18(3):167-176, 2006. Google Scholar
  12. Bogdan S. Chlebus, Gianluca De Marco, and Muhammed Talo. Anonymous processors with synchronous shared memory: Las Vegas algorithms. Submitted. Google Scholar
  13. Bogdan S. Chlebus, Gianluca De Marco, and Muhammed Talo. Anonymous processors with synchronous shared memory. CoRR, abs/1507.02272, 2015. Google Scholar
  14. Bogdan S. Chlebus and Dariusz R. Kowalski. Asynchronous exclusive selection. In Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC), pages 375-384, 2008. Google Scholar
  15. Ömer Eğecioğlu and Ambuj K. Singh. Naming symmetric processes using shared variables. Distributed Computing, 8(1):19-38, 1994. Google Scholar
  16. Peter van Emde Boas. Machine models and simulation. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), pages 1-66. The MIT Press, 1990. Google Scholar
  17. Yuval Emek, Jochen Seidel, and Roger Wattenhofer. Computability in anonymous networks: Revocable vs. irrecovable outputs. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Part II, volume 8573 of Lecture Notes in Computer Science, pages 183-195. Springer, 2014. Google Scholar
  18. Faith E. Fich and Eric Ruppert. Hundreds of impossibility results for distributed computing. Distributed Computing, 16(2-3):121-163, 2003. Google Scholar
  19. Rachid Guerraoui and Eric Ruppert. Anonymous and fault-tolerant shared-memory computing. Distributed Computing, 20(3):165-177, 2007. Google Scholar
  20. Joseph JáJá. An Introduction to Parallel Algorithms. Addison-Wesley, 1992. Google Scholar
  21. Prasad Jayanti and Sam Toueg. Wakeup under read/write atomicity. In Proceedings of the 4th International Workshop on Distributed Algorithms (WDAG), volume 486 of Lecture Notes in Computer Science, pages 277-288. Springer, 1990. Google Scholar
  22. Shay Kutten, Rafail Ostrovsky, and Boaz Patt-Shamir. The Las-Vegas processor identity problem (How and when to be unique). Journal of Algorithms, 37(2):468-494, 2000. Google Scholar
  23. Richard J Lipton and Arvin Park. The processor identity problem. Information Processing Letters, 36(2):91-94, 1990. Google Scholar
  24. Alessandro Panconesi, Marina Papatriantafilou, Philippas Tsigas, and Paul M. B. Vitányi. Randomized naming using wait-free shared variables. Distributed Computing, 11(3):113-124, 1998. Google Scholar
  25. Eric Ruppert. The anonymous consensus hierarchy and naming problems. In Proceedings of the 11th International Conference on Principles of Distributed Systems (OPODIS), volume 4878 of Lecture Notes in Computer Science, pages 386-400. Springer, 2007. Google Scholar
  26. Naoshi Sakamoto. Comparison of initial conditions for distributed algorithms on anonymous networks. In Proceedings of the 18th ACM Symposium on Principles of Distributed Computing (PODC), pages 173-179, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact