Document Open Access Logo

Set-Consensus Collections are Decidable

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

PDF

File

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

Document Identifiers

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

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.

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

Author Details

Carole Delporte-Gallet
Hugues Fauconnier
Eli Gafni
Petr Kuznetsov

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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact