Document Open Access Logo

Continuous Tasks and the Asynchronous Computability Theorem

Authors Hugo Rincon Galeana , Sergio Rajsbaum , Ulrich Schmid

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.73.pdf
  • Filesize: 0.81 MB
  • 27 pages

Document Identifiers

Author Details

Hugo Rincon Galeana
  • Embedded Computing Systems Group TU Wien, Austria
Sergio Rajsbaum
  • UNAM, Instituto de Matemáticas, Mexico City, Mexico
Ulrich Schmid
  • Embedded Computing Systems Group TU Wien, Austria

Funding

  • Galeana, Hugo Rincon: Supported by the Doctoral College on Resilient Embedded Systems at TU Wien and the Austrian Science Fund (FWF) project ByzDEL (P33600).
  • Rajsbaum, Sergio: Supported by UNAM-PAPIIT IN106520. Part of this work was done while visiting École Polytechnique.

Cite AsGet BibTex

Hugo Rincon Galeana, Sergio Rajsbaum, and Ulrich Schmid. Continuous Tasks and the Asynchronous Computability Theorem. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 73:1-73:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.73

Abstract

The celebrated 1999 Asynchronous Computability Theorem (ACT) of Herlihy and Shavit characterized distributed tasks that are wait-free solvable and uncovered deep connections with combinatorial topology. We provide an alternative characterization of those tasks by means of the novel concept of continuous tasks, which have an input/output specification that is a continuous function between the geometric realizations of the input and output complex: We state and prove a precise characterization theorem (CACT) for wait-free solvable tasks in terms of continuous tasks. Its proof utilizes a novel chromatic version of a foundational result in algebraic topology, the simplicial approximation theorem, which is also proved in this paper. Apart from the alternative proof of the ACT implied by our CACT, we also demonstrate that continuous tasks have an expressive power that goes beyond classic task specifications, and hence open up a promising venue for future research: For the well-known approximate agreement task, we show that one can easily encode the desired proportion of the occurrence of specific outputs, namely, exact agreement, in the continuous task specification.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Mathematics of computing → Hypergraphs
Keywords
  • Wait-free computability
  • topology
  • distributed computing
  • decision tasks
  • shared memory

Metrics

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

Related Versions

References

  1. Yehuda Afek and Eli Gafni. A simple characterization of asynchronous computations. Theoretical Computer Science, 561:88-95, 2015. Special Issue on Distributed Computing and Networking. URL: https://doi.org/10.1016/j.tcs.2014.07.022.
  2. Manuel Alcantara, Armando Castañeda, David Flores-Peñaloza, and Sergio Rajsbaum. The topology of look-compute-move robot wait-free algorithms with hard termination. Distributed Comput., 32(3):235-255, 2019. URL: https://doi.org/10.1007/s00446-018-0345-3.
  3. Hagit Attiya, Armando Castañeda, Danny Hendler, and Matthieu Perrin. Separating lock-freedom from wait-freedom. In Calvin Newport and Idit Keidar, editors, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 41-50. ACM, 2018. URL: https://doi.org/10.1145/3212734.3212739.
  4. Hagit Attiya, Armando Castañeda, and Sergio Rajsbaum. Locally Solvable Tasks and the Limitations of Valency Arguments. In Quentin Bramas, Rotem Oshman, and Paolo Romano, editors, 24th International Conference on Principles of Distributed Systems (OPODIS 2020), volume 184 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1-18:16, Dagstuhl, Germany, 2021. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2020.18.
  5. Hagit Attiya and Sergio Rajsbaum. The combinatorial structure of wait-free solvable tasks. SIAM J. Comput., 31(4):1286-1313, 2002. URL: https://doi.org/10.1137/S0097539797330689.
  6. Fernando Benavides and Sergio Rajsbaum. Collapsibility of read/write models using discrete morse theory. J. Appl. Comput. Topol., 1(3-4):365-396, 2018. URL: https://doi.org/10.1007/s41468-018-0011-7.
  7. Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 91-100, New York, NY, USA, 1993. ACM. URL: https://doi.org/10.1145/167088.167119.
  8. Elizabeth Borowsky and Eli Gafni. A simple algorithmically reasoned characterization of wait-free computation (extended abstract). In Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '97, page 189?198, New York, NY, USA, 1997. Association for Computing Machinery. URL: https://doi.org/10.1145/259380.259439.
  9. Elizabeth Borowsky, Eli Gafni, Nancy Lynch, and Sergio Rajsbaum. The BG distributed simulation algorithm. Distributed Computing, 14(3):127-146, 2001. URL: http://link.springer.de/link/service/journals/00446/bibs/1014003/10140127.htm.
  10. Armando Castañeda and S. Rajsbaum. New combinatorial topology bounds for renaming: the lower bound. Distributed Computing, 22:287-301, 2010. Google Scholar
  11. Carole Delporte-Gallet, Hugues Fauconnier, Sergio Rajsbaum, and Nayuta Yanagisawa. A characterization of t-resilient colorless task anonymous solvability. In Zvi Lotker and Boaz Patt-Shamir, editors, Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Ma'ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers, volume 11085 of Lecture Notes in Computer Science, pages 178-192. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-01325-7_18.
  12. Michael J. Fischer, Nancy A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374-382, April 1985. Google Scholar
  13. Matthias Függer, Thomas Nowak, and Manfred Schwarz. Tight bounds for asymptotic and approximate consensus. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC '18, pages 325-334, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3212734.3212762.
  14. E. Gafni and E. Koutsoupias. Three-processor tasks are undecidable. SIAM J. Comput., 28:970-983, 1999. Google Scholar
  15. Eli Gafni. The extended bg-simulation and the characterization of t-resiliency. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, pages 85-92, New York, NY, USA, 2009. Association for Computing Machinery. URL: https://doi.org/10.1145/1536414.1536428.
  16. Eli Gafni, Petr Kuznetsov, and Ciprian Manolescu. A generalized asynchronous computability theorem. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC '14, pages 222-231, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2611462.2611477.
  17. Eli Gafni and Sergio Rajsbaum. Distributed programming with tasks. In Chenyang Lu, Toshimitsu Masuzawa, and Mohamed Mosbah, editors, Principles of Distributed Systems - 14th International Conference, OPODIS 2010, Tozeur, Tunisia, December 14-17, 2010. Proceedings, volume 6490 of Lecture Notes in Computer Science, pages 205-218. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-17653-1_17.
  18. Hugo Rincon Galeana, Kyrill Winkler, Ulrich Schmid, and Sergio Rajsbaum. A topological view of partitioning arguments: Reducing k-set agreement to consensus. In Stabilization, Safety, and Security of Distributed Systems - 21st International Symposium, SSS 2019, Pisa, Italy, October 22-25, 2019, Proceedings, volume 11914 of Lecture Notes in Computer Science, pages 307-322. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-34992-9_25.
  19. Rachid Guerraoui and Michel Raynal. The Alpha of Indulgent Consensus. The Computer Journal, 50(1):53-67, August 2006. URL: https://doi.org/10.1093/comjnl/bxl046.
  20. Michiel Hazewinkel. Encyclopedia of mathematics, 2018. URL: http://encyclopediaofmath.org/index.php?title=Simplicial_complex&oldid=42757.
  21. Maurice Herlihy. Impossibility results for asynchronous pram (extended abstract). In Proceedings of the Third Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '91, pages 327-336, New York, NY, USA, 1991. Association for Computing Machinery. URL: https://doi.org/10.1145/113379.113409.
  22. Maurice Herlihy, Dmitry N. Kozlov, and Sergio Rajsbaum. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, 2013. URL: https://store.elsevier.com/product.jsp?isbn=9780124045781.
  23. Maurice Herlihy and Sergio Rajsbaum. The decidability of distributed decision tasks (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC '97, pages 589-598, New York, NY, USA, 1997. Association for Computing Machinery. URL: https://doi.org/10.1145/258533.258652.
  24. Maurice Herlihy and Sergio Rajsbaum. The topology of shared-memory adversaries. In Andréa W. Richa and Rachid Guerraoui, editors, Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, PODC 2010, Zurich, Switzerland, July 25-28, 2010, pages 105-113. ACM, 2010. URL: https://doi.org/10.1145/1835698.1835724.
  25. Maurice Herlihy and Sergio Rajsbaum. Simulations and reductions for colorless tasks. In Darek Kowalski and Alessandro Panconesi, editors, ACM Symposium on Principles of Distributed Computing, PODC '12, Funchal, Madeira, Portugal, July 16-18, 2012, pages 253-260. ACM, 2012. URL: https://doi.org/10.1145/2332432.2332483.
  26. Maurice Herlihy and Sergio Rajsbaum. The topology of distributed adversaries. Distributed Comput., 26(3):173-192, 2013. URL: https://doi.org/10.1007/s00446-013-0189-9.
  27. Maurice Herlihy, Sergio Rajsbaum, Michel Raynal, and Julien Stainer. From wait-free to arbitrary concurrent solo executions in colorless distributed computing. Theoretical Computer Science, 683:1-21, 2017. URL: https://doi.org/10.1016/j.tcs.2017.04.007.
  28. Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. J. ACM, 46(6):858-923, November 1999. Conference version in ACM STOC 1993. URL: https://doi.org/10.1145/331524.331529.
  29. Gunnar Hoest and Nir Shavit. Toward a topological characterization of asynchronous complexity. SIAM J. Comput., 36(2):457-497, 2006. URL: https://doi.org/10.1137/S0097539701397412.
  30. Petr Kuznetsov. Understanding non-uniform failure models. Bull. EATCS, 106:53-77, 2012. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/80.
  31. Petr Kuznetsov and Thibault Rieutord. Affine tasks for k-test-and-set. In Stéphane Devismes and Neeraj Mittal, editors, Stabilization, Safety, and Security of Distributed Systems, pages 151-166, Cham, 2020. Springer International Publishing. Google Scholar
  32. Petr Kuznetsov, Thibault Rieutord, and Yuan He. An asynchronous computability theorem for fair adversaries. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 387-396, 2018. URL: https://dl.acm.org/citation.cfm?id=3212765.
  33. Thomas Nowak, Ulrich Schmid, and Kyrill Winkler. Topological characterization of consensus under general message adversaries. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019., pages 218-227, 2019. (full version: http://arxiv.org/abs/1905.09590). URL: https://doi.org/10.1145/3293611.3331624.
  34. Michael Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. Comput., 29(5):1449-1483, 2000. URL: https://doi.org/10.1137/S0097539796307698.
  35. Vikram Saraph, Maurice Herlihy, and Eli Gafni. Asynchronous computability theorems for t-resilient systems. In Cyril Gavoille and David Ilcinkas, editors, Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings, volume 9888 of Lecture Notes in Computer Science, pages 428-441. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_31.
  36. Vikram Saraph, Maurice Herlihy, and Eli Gafni. An algorithmic approach to the asynchronous computability theorem. J. Appl. Comput. Topol., 1(3-4):451-474, 2018. URL: https://doi.org/10.1007/s41468-018-0014-4.
  37. Yunguang Yue, Fengchun Lei, Xingwu Liu, and Jie Wu. Asynchronous computability theorem in arbitrary solo models. Mathematics, 8(5), 2020. URL: https://doi.org/10.3390/math8050757.
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 Imprint Privacy Contact