Document Open Access Logo

Distributed Decision Problems: Concurrent Specifications Beyond Binary Relations (Invited Talk)

Author Sergio Rajsbaum

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2022.3.pdf
  • Filesize: 1.21 MB
  • 13 pages

Document Identifiers

Author Details

Sergio Rajsbaum
  • Institute of Mathematics, National Autonomous University of Mexico, Mexico City, Mexico

Funding

Supported by UNAM-PAPIIT IN106520.

Cite As Get BibTex

Sergio Rajsbaum. Distributed Decision Problems: Concurrent Specifications Beyond Binary Relations (Invited Talk). In 33rd International Conference on Concurrency Theory (CONCUR 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 243, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CONCUR.2022.3

Abstract

Much discussion exists about what is computation, but less about is a computational problem. Turing’s definition of computation was based on computing functions. When we move from sequential computing to interactive computing, discussions concentrate on computations that do not terminate, overlooking notions of distributed problems. Many models where concurrency happens have been proposed, ranging from those equivalent to a Turing machine, to those where much heated discussion has taken place, claiming that interactive models are fundamentally different from Turing machines.
It is argued here that there is no need to go all the way to non-terminating interaction, to appreciate how different distributed computation is from sequential computation. The discussion concentrates on the various ways that exist of representing a distributed decision problem. Each process of a distributed system starts with an initial private input value, and after communicating with other processes in the system, produces a local output value. An input/output relation is needed, to specify which output values are legal for a particular assignment of input values to the processes.
An overview is provided of some results that show how rich the topic of distributed decision problems can be, when asynchronous processes can fail, but mostly independent of particular models of distributed computing and their many intricate details (types of failures and of communication). We are in a world very different from that of the functions of sequential computation; moving away from the world of graphs beyond binary relations, to the world of simplicial complexes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • Distributed decision tasks
  • simplicial complex
  • linearizability
  • interval-linearizability
  • Arrow’s impossibility
  • Speedup theorems

Metrics

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

References

  1. Alfred V. Aho. Computation and Computational Thinking. The Computer Journal, 55(7):832-835, July 2012. URL: https://doi.org/10.1093/comjnl/bxs074.
  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. Dan Alistarh, Faith Ellen, and Joel Rybicki. Wait-free approximate agreement on graphs. In Tomasz Jurdzinski and Stefan Schmid, editors, Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, Wrocław, Poland, June 28 - July 1, 2021, Proceedings, volume 12810 of Lecture Notes in Computer Science, pages 87-105. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-79527-6_6.
  4. Kenneth J. Arrow. A difficulty in the concept of social welfare. Journal of Political Economy, 58(4):328-346, 1950. URL: https://doi.org/10.1086/256963.
  5. Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics. John Wiley & Sons, Hoboken, NJ, USA, 2004. Google Scholar
  6. Ofer Biran, Shlomo Moran, and Shmuel Zaks. A combinatorial characterization of the distributed 1-solvable tasks. J. Algorithms, 11(3):420-440, 1990. Preliminary version in PODC 1988. URL: https://doi.org/10.1016/0196-6774(90)90020-F.
  7. Ofer Biran, Shlomo Moran, and Shmuel Zaks. Deciding 1-sovability of distributed task is np-hard. In Rolf H. Möhring, editor, Graph-Theoretic Concepts in Computer Science, 16rd International Workshop, WG '90, Berlin, Germany, June 20-22, 1990, Proceedings, volume 484 of Lecture Notes in Computer Science, pages 206-220. Springer, 1990. URL: https://doi.org/10.1007/3-540-53832-1_44.
  8. Ofer Biran, Shlomo Moran, and Shmuel Zaks. Tight bounds on the round complexity of distributed 1-solvable tasks. In Jan van Leeuwen and Nicola Santoro, editors, Distributed Algorithms, 4th International Workshop, WDAG '90, Bari, Italy, September 24-26, 1990, Proceedings, volume 486 of Lecture Notes in Computer Science, pages 373-389. Springer, 1990. URL: https://doi.org/10.1007/3-540-54099-7_25.
  9. Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 91-100. ACM, 1993. URL: https://doi.org/10.1145/167088.167119.
  10. Elizabeth Borowsky, Eli Gafni, Nancy A. Lynch, and Sergio Rajsbaum. The BG distributed simulation algorithm. Distributed Comput., 14(3):127-146, 2001. URL: https://doi.org/10.1007/PL00008933.
  11. Armando Castañeda, Damien Imbs, Sergio Rajsbaum, and Michel Raynal. Renaming is weaker than set agreement but for perfect renaming: A map of sub-consensus tasks. In David Fernández-Baca, editor, LATIN 2012: Theoretical Informatics - 10th Latin American Symposium, Arequipa, Peru, April 16-20, 2012. Proceedings, volume 7256 of Lecture Notes in Computer Science, pages 145-156. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-29344-3_13.
  12. Armando Castañeda, Damien Imbs, Sergio Rajsbaum, and Michel Raynal. Generalized symmetry breaking tasks and nondeterminism in concurrent objects. SIAM J. Comput., 45(2):379-414, 2016. URL: https://doi.org/10.1137/130936828.
  13. Armando Castañeda, Sergio Rajsbaum, and Michel Raynal. The renaming problem in shared memory systems: An introduction. Comput. Sci. Rev., 5(3):229-251, 2011. URL: https://doi.org/10.1016/j.cosrev.2011.04.001.
  14. Armando Castañeda, Sergio Rajsbaum, and Michel Raynal. Unifying concurrent objects and distributed tasks: Interval-linearizability. J. ACM, 65(6):45:1-45:42, 2018. URL: https://doi.org/10.1145/3266457.
  15. Armando Castañeda, Sergio Rajsbaum, and Matthieu Roy. Two convergence problems for robots on graphs. In 2016 Seventh Latin-American Symposium on Dependable Computing, LADC 2016, Cali, Colombia, October 19-21, 2016, pages 81-90. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/LADC.2016.21.
  16. Himanshu Chauhan and Vijay K. Garg. Democratic elections in faulty distributed systems. In Davide Frey, Michel Raynal, Saswati Sarkar, Rudrapatna K. Shyamasundar, and Prasun Sinha, editors, Distributed Computing and Networking, 14th International Conference, ICDCN 2013, Mumbai, India, January 3-6, 2013. Proceedings, volume 7730 of Lecture Notes in Computer Science, pages 176-191. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-35668-1_13.
  17. Peter J. Denning. Reflections on a Symposium on Computation. The Computer Journal, 55(7):799-802, July 2012. URL: https://doi.org/10.1093/comjnl/bxs064.
  18. Peter J. Denning and Peter Wegner. Introduction to What is Computation. The Computer Journal, 55(7):803-804, July 2012. URL: https://doi.org/10.1093/comjnl/bxs065.
  19. Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. Reasoning About Knowledge. MIT Press, 1995. URL: https://doi.org/10.7551/mitpress/5803.001.0001.
  20. Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374-382, 1985. URL: https://doi.org/10.1145/3149.214121.
  21. Lance Fortnow. The enduring legacy of the turing machine. Comput. J., 55(7):830-831, July 2012. URL: https://doi.org/10.1093/comjnl/bxs073.
  22. Pierre Fraigniaud, Ami Paz, and Sergio Rajsbaum. A speedup theorem for asynchronous computation with applications to consensus and approximate agreement. To appear in ACM PODC 2022, abs/2206.05356, 2022. To appear in ACM PODC 2022. URL: https://doi.org/10.48550/arXiv.2206.05356.
  23. Pierre Fraigniaud, Sergio Rajsbaum, and Corentin Travers. Locality and checkability in wait-free computing. Distributed Comput., 26(4):223-242, 2013. URL: https://doi.org/10.1007/s00446-013-0188-x.
  24. Dennis J. Frailey. Computation is Process. The Computer Journal, 55(7):817-819, July 2012. URL: https://doi.org/10.1093/comjnl/bxs069.
  25. Hugo Rincon Galeana, Sergio Rajsbaum, and Ulrich Schmid. Continuous tasks and the asynchronous computability theorem. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 73:1-73:27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.73.
  26. Éric Goubault, Marijana Lazic, Jérémy Ledent, and Sergio Rajsbaum. Wait-free solvability of equality negation tasks. In Jukka Suomela, editor, 33rd International Symposium on Distributed Computing, DISC 2019, October 14-18, 2019, Budapest, Hungary, volume 146 of LIPIcs, pages 21:1-21:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.DISC.2019.21.
  27. Éric Goubault, Jérémy Ledent, and Samuel Mimram. Concurrent specifications beyond linearizability. In Jiannong Cao, Faith Ellen, Luis Rodrigues, and Bernardo Ferreira, editors, 22nd International Conference on Principles of Distributed Systems, OPODIS 2018, December 17-19, 2018, Hong Kong, China, volume 125 of LIPIcs, pages 28:1-28:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2018.28.
  28. Éric Goubault, Jérémy Ledent, and Sergio Rajsbaum. A simplicial complex model for dynamic epistemic logic to study distributed task computability. Inf. Comput., 278:104597, 2021. URL: https://doi.org/10.1016/j.ic.2020.104597.
  29. Rachid Guerraoui, Michel Hurfin, Achour Mostéfaoui, Rui Carlos Oliveira, Michel Raynal, and André Schiper. Consensus in asynchronous distributed systems: A concise guided tour. In Sacha Krakowiak and Santosh K. Shrivastava, editors, Advances in Distributed Systems, Advanced Distributed Computing: From Algorithms to Systems, volume 1752 of Lecture Notes in Computer Science, pages 33-47. Springer, 1999. URL: https://doi.org/10.1007/3-540-46475-1_2.
  30. 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.
  31. Maurice Herlihy and Sergio Rajsbaum. A classification of wait-free loop agreement tasks. Theor. Comput. Sci., 291(1):55-77, 2003. URL: https://doi.org/10.1016/S0304-3975(01)00396-6.
  32. Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. J. ACM, 46(6):858-923, 1999. URL: https://doi.org/10.1145/331524.331529.
  33. Maurice Herlihy and Nir Shavit. The art of multiprocessor programming. Morgan Kaufmann, 2008. Google Scholar
  34. Maurice Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, 1990. URL: https://doi.org/10.1145/78969.78972.
  35. 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.
  36. 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
  37. Butler Lampson. How to build a highly available system using consensus. In Ozalp Babaoglu and Keith Marzullo, editors, 10th International Workshop on Distributed Algorithms (WDAG 1996), pages 1-17. Springer, October 1996. The proceedings are: Distributed Algorithms, Lecture Notes in Computer Science 1151, Springer, 1996. URL: https://www.microsoft.com/en-us/research/publication/how-to-build-a-highly-available-system-using-consensus/.
  38. Xingwu Liu, Zhiwei Xu, and Jianzhong Pan. Classifying rendezvous tasks of arbitrary dimension. Theor. Comput. Sci., 410(21-23):2162-2173, 2009. URL: https://doi.org/10.1016/j.tcs.2009.01.033.
  39. Wai-Kau Lo and Vassos Hadzilacos. All of us are smarter than any of us: Nondeterministic wait-free hierarchies are not robust. SIAM J. Comput., 30(3):689-728, 2000. URL: https://doi.org/10.1137/S0097539798335766.
  40. Darya Melnyk, Yuyi Wang, and Roger Wattenhofer. Byzantine preferential voting. In George Christodoulou and Tobias Harks, editors, Web and Internet Economics, pages 327-340, Cham, 2018. Springer International Publishing. Google Scholar
  41. Hammurabi Mendes, Maurice Herlihy, Nitin Vaidya, and Vijay K. Garg. Multidimensional agreement in byzantine systems. Distributed Computing, 28(6):423-441, 2015. URL: https://doi.org/10.1007/s00446-014-0240-5.
  42. Mark Moir and Nir Shavit. Concurrent data structures. In Dinesh P. Mehta and Sartaj Sahni, editors, Handbook of Data Structures and Applications. Chapman and Hall/CRC, 2004. URL: https://doi.org/10.1201/9781420035179.ch47.
  43. Shlomo Moran and Yaron Wolfstahl. Extended impossibility results for asynchronous complete networks. Inf. Process. Lett., 26(3):145-151, 1987. URL: https://doi.org/10.1016/0020-0190(87)90052-4.
  44. Achour Mostéfaoui, Sergio Rajsbaum, and Michel Raynal. Conditions on input vectors for consensus solvability in asynchronous distributed systems. J. ACM, 50(6):922-954, 2003. URL: https://doi.org/10.1145/950620.950624.
  45. Achour Mostefaoui, Sergio Rajsbaum, and Michel Raynal. Synchronous condition-based consensus. Distributed Computing, 18(5):325-343, 2006. URL: https://doi.org/10.1007/s00446-005-0148-1.
  46. Gil Neiger. Set-linearizability. In James H. Anderson, David Peleg, and Elizabeth Borowsky, editors, Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, Los Angeles, California, USA, August 14-17, 1994, page 396. ACM, 1994. URL: https://doi.org/10.1145/197917.198176.
  47. Sergio Rajsbaum and Armajac Raventós-Pujol. A distributed combinatorial topology approach to arrow’s impossibility theorem. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC '22, page to appear, New York, NY, USA, 2022. Association for Computing Machinery. Google Scholar
  48. Michel Raynal. Concurrent Programming - Algorithms, Principles, and Foundations. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-32027-9.
  49. Michel Raynal. Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-94141-7.
  50. Michel Raynal. The notion of universality in crash-prone asynchronous message-passing systems: A tutorial. In 2019 38th Symposium on Reliable Distributed Systems (SRDS), pages 334-33416, 2019. URL: https://doi.org/10.1109/SRDS47363.2019.00046.
  51. Paul S. Rosenbloom. Computing and Computation. The Computer Journal, 55(7):820-824, July 2012. URL: https://doi.org/10.1093/comjnl/bxs070.
  52. Michael E. 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.
  53. Gadi Taubenfeld and Shlomo Moran. Possibility and impossibility results in a shared memory environment. Acta Informatica, 33(1):1-20, 1996. Preliminary version in WDAG 1989. URL: https://doi.org/10.1007/s002360050034.
  54. Peter Wegner. The Evolution of Computation. The Computer Journal, 55(7):811-813, July 2012. URL: https://doi.org/10.1093/comjnl/bxs067.
  55. Yunguang Yue, Jie Wu, and Fengchun Lei. The evolution of non-degenerate and degenerate rendezvous tasks. Topology and its Applications, 264:187-200, 2019. URL: https://doi.org/10.1016/j.topol.2019.06.015.
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