Document Open Access Logo

Locally Solvable Tasks and the Limitations of Valency Arguments

Authors Hagit Attiya , Armando Castañeda, Sergio Rajsbaum

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2020.18.pdf
  • Filesize: 1.03 MB
  • 16 pages

Document Identifiers

Author Details

Hagit Attiya
  • Computer Science Department, Technion, Haifa, Israel
Armando Castañeda
  • Instituto de Matemáticas, UNAM, Mexico City, Mexico
Sergio Rajsbaum
  • Instituto de Matemáticas, UNAM, Mexico City, Mexico

Funding

  • Attiya, Hagit: Supported by ISF grant 380/18.
  • Castañeda, Armando: Supported by UNAM-PAPIIT project IN108720.
  • Rajsbaum, Sergio: Supported by UNAM-PAPIIT project IN106520.

Acknowledgements

We thank Ulrich Schmid and the reviewers for helpful comments, and Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili and Leqi Zhu for helpful conversations.

Cite AsGet BibTex

Hagit Attiya, Armando Castañeda, and Sergio Rajsbaum. Locally Solvable Tasks and the Limitations of Valency Arguments. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.OPODIS.2020.18

Abstract

An elegant strategy for proving impossibility results in distributed computing was introduced in the celebrated FLP consensus impossibility proof. This strategy is local in nature as at each stage, one configuration of a hypothetical protocol for consensus is considered, together with future valencies of possible extensions. This proof strategy has been used in numerous situations related to consensus, leading one to wonder why it has not been used in impossibility results of two other well-known tasks: set agreement and renaming. This paper provides an explanation of why impossibility proofs of these tasks have been of a global nature. It shows that a protocol can always solve such tasks locally, in the following sense. Given a configuration and all its future valencies, if a single successor configuration is selected, then the protocol can reveal all decisions in this branch of executions, satisfying the task specification. This result is shown for both set agreement and renaming, implying that there are no local impossibility proofs for these tasks.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Computing methodologies → Distributed algorithms
  • Computing methodologies → Concurrent algorithms
  • Theory of computation → Concurrent algorithms
  • Theory of computation → Distributed algorithms
Keywords
  • Wait-freedom
  • Set agreement
  • Weak symmetry breaking
  • Impossibility proofs

Metrics

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

Related Versions

References

  1. M. K. Aguilera and S. Toueg. A simple bivalency proof that t-resilient consensus requires t + 1 round. Information Processing Letters, 71(3-4):155-158, 1999. Google Scholar
  2. Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. Why extension-based proofs fail. In STOC, pages 986-996, 2019. Google Scholar
  3. James Aspnes. Lower bounds for distributed coin-flipping and randomized consensus. Journal of the ACM, 45(3):415-450, 1998. Google Scholar
  4. H. Attiya, A. Bar-Noy, D. Dolev, D. Peleg, and R. Reischuk. Renaming in an asynchronous environment. Journal of the ACM, 37(3):524-548, 1990. Google Scholar
  5. Hagit Attiya and Armando Castañeda. A non-topological proof for the impossibility of k-set agreement. Theoretical Computer Science, 512:41-48, 2013. Google Scholar
  6. Hagit Attiya, Armando Castañeda, Danny Hendler, and Matthieu Perrin. Separating lock-freedom from wait-freedom. In PODC, pages 41-50, 2018. URL: https://doi.org/10.1145/3212734.3212739.
  7. Hagit Attiya and Keren Censor. Tight bounds for asynchronous randomized consensus. Journal of the ACM, 55(5):1-26, 2008. Google Scholar
  8. Hagit Attiya, Nancy Lynch, and Nir Shavit. Are wait-free algorithms fast? Journal of the ACM, 41(1):725-763, 1994. Google Scholar
  9. Hagit Attiya and Ami Paz. Counting-based impossibility proofs for set agreement and renaming. Journal of Parallel and Distributed Computing, 87:1-12, 2016. Google Scholar
  10. E. Boroswsky and E. Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In ACM Symposium on Theory of Computing, pages 91-100, 1993. Google Scholar
  11. Elizabeth Borowsky and Eli Gafni. Immediate atomic snapshots and fast renaming. In PODC, pages 41-51, 1993. Google Scholar
  12. Armando Castañeda and Sergio Rajsbaum. New combinatorial topology bounds for renaming: The lower bound. Distributed Computing, 22(5-6):287-301, 2010. URL: https://doi.org/10.1007/s00446-010-0108-2.
  13. Armando Castañeda and Sergio Rajsbaum. New combinatorial topology bounds for renaming: The upper bound. J. ACM, 59(1):3:1-3:49, 2012. URL: https://doi.org/10.1145/2108242.2108245.
  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. Soma Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation, 105(1):132-158, 1993. Google Scholar
  16. Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the ACM, 34(1):77-97, January 1987. Google Scholar
  17. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374-382, 1985. Google Scholar
  18. Eli Gafni and Sergio Rajsbaum. Distributed programming with tasks. In OPODIS, pages 205-218, 2010. Google Scholar
  19. Eli Gafni, Sergio Rajsbaum, and Maurice Herlihy. Subconsensus tasks: Renaming is weaker than set agreement. In DISC, pages 329-338, 2006. Google Scholar
  20. M. Herlihy, D. Kozlov, and S. Rajsbaum. Distributed Computing Through Combinatorial Topology. Elsevier-Morgan Kaufmann, 2013. URL: https://doi.org/10.1016/C2011-0-07032-1.
  21. Maurice Herlihy. Impossibility results for asynchronous PRAM. In SPAA, pages 327-336, 1991. URL: https://doi.org/10.1145/113379.113409.
  22. Maurice Herlihy and Sergio Rajsbaum. The topology of distributed adversaries. Distrib. Comput., 26(3):173-192, June 2013. URL: https://doi.org/10.1007/s00446-013-0189-9.
  23. Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. Journal of the ACM, 46(6):858-923, 1999. Google Scholar
  24. Maurice P. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):123-149, 1991. Google Scholar
  25. Idit Keidar and Sergio Rajsbaum. A simple proof of the uniform consensus synchronous lower bound. Information Processing Letters, 85(1):47-52, 2003. URL: https://doi.org/10.1016/S0020-0190(02)00333-2.
  26. 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.
  27. M. C. Loui and H. A. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, 4:163-183, 1987. Google Scholar
  28. Ronit Lubitch and Shlomo Moran. Closed schedulers: a novel technique for analyzing asynchronous protocols. Distributed Computing, 8(4):203-210, 1995. URL: https://doi.org/10.1007/BF02242738.
  29. Yoram Moses and Sergio Rajsbaum. A layered analysis of consensus. SIAM Journal on Computing, 31(4):989-1021, 2002. Google Scholar
  30. Thomas Nowak, Ulrich Schmid, and Kyrill Winkler. Topological characterization of consensus under general message adversaries. In PODC, page 218–227, 2019. Google Scholar
  31. S. Rajsbaum. Iterated shared memory models. In LATIN, pages 407-416, 2010. Google Scholar
  32. Michael Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM Journal on Computing, 29(5):1449-1483, 2000. Google Scholar
  33. E. Sperner. Neuer beweis für die invarianz der dimensionszahl und des gebietes. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 6(1):265-272, 1928. URL: https://doi.org/10.1007/BF02940617.
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