Document Open Access Logo

Set-Consensus Collections are Decidable

Authors Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, Petr Kuznetsov

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2016.7.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Carole Delporte-Gallet
Hugues Fauconnier
Eli Gafni
Petr Kuznetsov

Cite As Get BibTex

Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Petr Kuznetsov. Set-Consensus Collections are Decidable. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.OPODIS.2016.7

Abstract

A natural way to measure the power of a distributed-computing model is to characterize the set of tasks that can be solved in it. In general, however, the question of whether a given task can be solved in a given model is undecidable, even if we only consider the wait-free shared-memory model. In this paper, we address this question for restricted classes of models and tasks. We show that the question of whether a collection C of (l, j)-set consensus objects, for various l (the number of processes that can invoke the object) and j (the number of distinct outputs the object returns), can be used by n processes to solve wait-free k-set consensus is decidable. Moreover, we provide a simple O(n^2) decision algorithm, based on a dynamic programming solution to the Knapsack optimization problem. We then present an adaptive wait-free set-consensus algorithm that, for each set of participating processes, achieves the best level of agreement that is possible to achieve using C. Overall, this gives us a complete characterization of a read-write model defined by a collection of set-consensus objects through its set-consensus power.

Subject Classification

Keywords
  • Decidability
  • distributed tasks
  • set consensus
  • Knapsack problem

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. Journal of the ACM, 40(4):873-890, 1993. Google Scholar
  2. Yehuda Afek, Faith Ellen, and Eli Gafni. Deterministic objects: Life beyond consensus. In PODC, 2016. Google Scholar
  3. Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In STOC, pages 91-100. ACM Press, May 1993. Google Scholar
  4. Elizabeth Borowsky and Eli Gafni. The implication of the Borowsky-Gafni simulation on the set-consensus hierarchy. Technical report, UCLA, 1993. URL: http://fmdb.cs.ucla.edu/Treports/930021.pdf.
  5. Elizabeth Borowsky, Eli Gafni, Nancy A. Lynch, and Sergio Rajsbaum. The BG distributed simulation algorithm. Distributed Computing, 14(3):127-146, 2001. Google Scholar
  6. Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest failure detector for solving consensus. Journal of the ACM, 43(4):685-722, July 1996. Google Scholar
  7. Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225-267, March 1996. Google Scholar
  8. Soma Chaudhuri and Paul Reiners. Understanding the set consensus partial order using the Borowsky-Gafni simulation (extended abstract). In WDAG, pages 362-379, 1996. Google Scholar
  9. Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Petr Kuznetsov. Wait-freedom with advice. Distributed Computing, 28(1):3-19, 2015. Google Scholar
  10. Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Andreas Tielmann. The disagreement power of an adversary. Distributed Computing, 24(3-4):137-147, 2011. Google Scholar
  11. 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, April 1985. Google Scholar
  12. Eli Gafni and Rachid Guerraoui. Generalized universality. In Proceedings of the 22nd international conference on Concurrency theory, CONCUR'11, pages 17-27, Berlin, Heidelberg, 2011. Springer-Verlag. Google Scholar
  13. Eli Gafni and Elias Koutsoupias. Three-processor tasks are undecidable. SIAM J. Comput., 28(3):970-983, 1999. Google Scholar
  14. Eli Gafni and Petr Kuznetsov. Turning adversaries into friends: Simplified, made constructive, and extended. In OPODIS, pages 380-394, 2010. Google Scholar
  15. Eli Gafni and Petr Kuznetsov. Relating L-Resilience and Wait-Freedom via Hitting Sets. In ICDCN, pages 191-202, 2011. Google Scholar
  16. Eli Gafni, Michael Merritt, and Gadi Taubenfeld. The concurrency hierarchy, and algorithms for unbounded concurrency. In PODC, pages 161-169, 2001. Google Scholar
  17. Eli Gafni, Sergio Rajsbaum, and Maurice Herlihy. Subconsensus tasks: Renaming is weaker than set agreement. In DISC, pages 329-338, 2006. Google Scholar
  18. Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):123-149, January 1991. Google Scholar
  19. Maurice Herlihy and Sergio Rajsbaum. The decidability of distributed decision tasks (extended abstract). In STOC, pages 589-598, 1997. Google Scholar
  20. Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. Journal of the ACM, 46(2):858-923, 1999. Google Scholar
  21. Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack problems. Springer, 2004. Google Scholar
  22. 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. Google Scholar
  23. Paul Reiners. Understanding the set consensus partial order using the Borowsky-Gafni simulation. Master’s thesis, Iowa State University, 1996. Google Scholar
  24. Michael Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. on Computing, 29:1449-1483, 2000. 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