Document Open Access Logo

Task Computability in Unreliable Anonymous Networks

Authors Petr Kuznetsov, Nayuta Yanagisawa

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.23.pdf
  • Filesize: 0.66 MB
  • 13 pages

Document Identifiers

Author Details

Petr Kuznetsov
  • LTCI, Télécom ParisTec, Université Paris-Saclay, France
Nayuta Yanagisawa
  • DeNA Co., Ltd., Japan

Cite As Get BibTex

Petr Kuznetsov and Nayuta Yanagisawa. Task Computability in Unreliable Anonymous Networks. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.OPODIS.2018.23

Abstract

We consider the anonymous broadcast model: a set of n anonymous processes communicate via send-to-all primitives. We assume that underlying communication channels are asynchronous but reliable, and that the processes are subject to crash failures. We show first that in this model, even a single faulty process precludes implementations of atomic objects with non-commuting operations, even as simple as read-write registers or add-only sets. We, however, show that a sequentially consistent read-write memory and add-only sets can be implemented t-resiliently for t<n/2, i.e., provided that a majority of the processes do not fail. We use this implementation to establish an equivalence between the t-resilient read-write anonymous shared-memory model and the t-resilient anonymous broadcast model in terms of colorless task solvability. As a result, we obtain the first task computability characterization for unreliable anonymous message-passing systems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Computability
Keywords
  • Distributed tasks
  • anonymous broadcast
  • fault-tolerance

Metrics

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

References

  1. Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic Snapshots of Shared Memory. JACM, 40(4):873-890, 1993. Google Scholar
  2. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235-253, 2006. Google Scholar
  3. 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
  4. Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing Memory Robustly in Message-passing Systems. J. ACM, 42(1):124-142, January 1995. URL: http://dx.doi.org/10.1145/200836.200869.
  5. François Bonnet and Michel Raynal. The Price of Anonymity: Optimal Consensus Despite Asynchrony, Crash, and Anonymity. ACM Trans. Auton. Adapt. Syst., 6(4):23:1-23:28, October 2011. URL: http://dx.doi.org/10.1145/2019591.2019592.
  6. Zohir Bouzid, Michel Raynal, and Pierre Sutra. Anonymous obstruction-free (n, k)-set agreement with n-k+1 atomic read/write registers. Distributed Computing, 31(2):99-117, 2018. Google Scholar
  7. Zohir Bouzid, Pierre Sutra, and Corentin Travers. Anonymous Agreement: The Janus Algorithm. In Principles of Distributed Systems - 15th International Conference, OPODIS 2011, Toulouse, France, December 13-16, 2011. Proceedings, pages 175-190, 2011. Google Scholar
  8. Claire Capdevielle, Colette Johnen, Petr Kuznetsov, and Alessia Milani. On the uncontended complexity of anonymous agreement. Distributed Computing, 30(6):459-468, 2017. Google Scholar
  9. S. Chaudhuri. More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems. Information and Computation, 105(1):132-158, 1993. Google Scholar
  10. Tom Chothia and Konstantinos Chatzikokolakis. A Survey of Anonymous Peer-to-Peer File-Sharing. In Proceedings of Satellite Workshop of the International Conference on Embedded and Ubiquitous Systems (EUS), pages 744-755, 2005. Google Scholar
  11. Carole Delporte-Gallet and Hugues Fauconnier. Two Consensus Algorithms with Atomic Registers and Failure Detector Ω. In Proceedings of the 10th International Conference on Distributed Computing and Networking (ICDCN), volume 5408 of Lecture Notes in Computer Science (LNCS), pages 251-262, 2009. Google Scholar
  12. Carole Delporte-Gallet, Hugues Fauconnier, Petr Kuznetsov, and Eric Ruppert. On the Space Complexity of Set Agreement? In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015, pages 271-280, 2015. Google Scholar
  13. Carole Delporte-Gallet, Hugues Fauconnier, Sergio Rajsbaum, and Nayuta Yanagisawa. A Characterization of t-Resilient Solvable Colorless Tasks in Anonymous Shared-Memory Model. In SIROCCO2018 (to appear), 2018. Technical report: URL: https://arxiv.org/abs/1712.04393.
  14. Carole Delporte-Gallet, Hugues Fauconnier, Sergio Rajsbaum, and Nayuta Yanagisawa. An anonymous wait-free weak-set object implementation. In NETYS2018 (to appear), 2018. Google Scholar
  15. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of Distributed Consensus with One Faulty Process. J. ACM, 32(2):374-382, April 1985. Google Scholar
  16. Rachid Guerraoui and Eric Ruppert. Anonymous and fault-tolerant shared-memory computing. Distributed Computing, 20(3):165-177, 2007. Google Scholar
  17. Maurice Herlihy. Wait-free synchronization. ACM TOPLAS, 13(1):123-149, 1991. Google Scholar
  18. Maurice Herlihy, Dmitry Kozlov, and Sergio Rajsbaum. Distributed computing through combinatorial topology. Morgan Kaufmann, 2013. Google Scholar
  19. Maurice Herlihy and Sergio Rajsbaum. A classification of wait-free loop agreement tasks. Theoretical Computer Science, 291(1):55-77, 2003. Google Scholar
  20. Nayuta Yanagisawa. Wait-Free Solvability of Colorless Tasks in Anonymous Shared-Memory Model. Theory of Computing Systems, pages pp 1-18, November 2017. URL: http://dx.doi.org/10.1007/s00224-017-9819-0.
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