Document Open Access Logo

A Wealth of Sub-Consensus Deterministic Objects

Authors Eli Daian, Giuliano Losa, Yehuda Afek, Eli Gafni

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.17.pdf
  • Filesize: 470 kB
  • 17 pages

Document Identifiers

Author Details

Eli Daian
  • School of Computer Science, Tel-Aviv University, Israel
Giuliano Losa
  • Computer Science Department, University of California, Los Angeles, CA, USA
Yehuda Afek
  • School of Computer Science, Tel-Aviv University, Israel
Eli Gafni
  • Computer Science Department, University of California, Los Angeles, CA, USA

Funding

The work of Yehuda Afek and Eli Gafni was partially supported by the United States-Israel Binational Science Foundation (grant 2014226). This material is based upon work supported by the National Science Foundation under Grant No. 1655166.

Cite As Get BibTex

Eli Daian, Giuliano Losa, Yehuda Afek, and Eli Gafni. A Wealth of Sub-Consensus Deterministic Objects. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.DISC.2018.17

Abstract

The consensus hierarchy classifies shared an object according to its consensus number, which is the maximum number of processes that can solve consensus wait-free using the object. The question of whether this hierarchy is precise enough to fully characterize the synchronization power of deterministic shared objects was open until 2016, when Afek et al. showed that there is an infinite hierarchy of deterministic objects, each weaker than the next, which is strictly between i and i+1-processors consensus, for i >= 2. For i=1, the question whether there exist a deterministic object whose power is strictly between read-write and 2-processors consensus, remained open.
We resolve the question positively by exhibiting an infinite hierarchy of simple deterministic objects which are equivalent to set-consensus tasks, and thus are stronger than read-write registers, but they cannot implement consensus for two processes. Still our paper leaves a gap with open questions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • shared memory
  • distributed algorithms
  • wait-free
  • set consensus

Metrics

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

References

  1. Yehuda Afek, Faith Ellen, and Eli Gafni. Deterministic objects: Life beyond consensus. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC '16, pages 97-106, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2933057.2933116.
  2. Yehuda Afek, Eli Gafni, and Adam Morrison. Common2 extended to stacks and unbounded concurrency. Distributed Computing, 20(4):239-252, Nov 2007. URL: http://dx.doi.org/10.1007/s00446-007-0023-3.
  3. Yehuda Afek, Eli Gafni, Sergio Rajsbaum, Michel Raynal, and Corentin Travers. Simultaneous consensus tasks: A tighter characterization of set-consensus. In Soma Chaudhuri, Samir R. Das, Himadri S. Paul, and Srikanta Tirthapura, editors, Distributed Computing and Networking, pages 331-341, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. Google Scholar
  4. Yehuda Afek and Michael Merritt. Fast, wait-free (2k-1)-renaming. In Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '99, pages 105-112, New York, NY, USA, 1999. ACM. URL: http://dx.doi.org/10.1145/301308.301338.
  5. Yehuda Afek, Eytan Weisberger, and Hanan Weisman. A completeness theorem for a class of synchronization objects. In Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing, PODC '93, pages 159-170, New York, NY, USA, 1993. ACM. URL: http://dx.doi.org/10.1145/164051.164071.
  6. Hagit Attiya and Arie Fouren. Adaptive wait-free algorithms for lattice agreement and renaming (extended abstract). In Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC '98, pages 277-286, New York, NY, USA, 1998. ACM. URL: http://dx.doi.org/10.1145/277697.277749.
  7. Rida A. Bazzi, Gil Neiger, and Gary L. Peterson. On the use of registers in achieving wait-free consensus. Distributed Computing, 10(3):117-127, Mar 1997. URL: http://dx.doi.org/10.1007/s004460050029.
  8. Elizabeth Borowsky. Capturing the Power of Resiliency and Set Consensus in Distributed Systems. PhD thesis, University of California in Los Angeles, Los Angeles, CA, USA, 1995. UMI Order No. GAX96-10429. Google Scholar
  9. Elizabeth Borowsky and Eli Gafni. Generalized flp impossibility result for t-resilient asynchronous computations. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC '93, pages 91-100, New York, NY, USA, 1993. ACM. URL: http://dx.doi.org/10.1145/167088.167119.
  10. Elizabeth Borowsky and Eli Gafni. The implication of the Borowsky-Gafni simulation on the set-consensus hierarchy. UCLA Computer Science Department, 1993. Google Scholar
  11. Elizabeth Borowsky, Eli Gafni, and Yehuda Afek. Consensus power makes (some) sense! (extended abstract). In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '94, pages 363-372, New York, NY, USA, 1994. ACM. URL: http://dx.doi.org/10.1145/197917.198126.
  12. David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg. On the number of objects with distinct power and the linearizability of set agreement objects. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 12:1-12:14, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.DISC.2017.12.
  13. David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg. On the classification of deterministic objects via set agreement power. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC '18, pages 71-80, New York, NY, USA, 2018. ACM. URL: http://dx.doi.org/10.1145/3212734.3212775.
  14. Soma Chaudhuri. Agreement is harder than consensus: Set consensus problems in totally asynchronous systems. In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, PODC '90, pages 311-324, New York, NY, USA, 1990. ACM. URL: http://dx.doi.org/10.1145/93385.93431.
  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. Soma Chaudhuri and Paul Reiners. Understanding the set consensus partial order using the borowsky-gafni simulation. In Özalp Babaoğlu and Keith Marzullo, editors, Distributed Algorithms, pages 362-379, Berlin, Heidelberg, 1996. Springer Berlin Heidelberg. Google Scholar
  17. Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374-382, 1985. Google Scholar
  18. 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. ACM. URL: http://dx.doi.org/10.1145/113379.113409.
  19. Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS), 13:124-149, January 1991. URL: http://dx.doi.org/10.1145/114005.102808.
  20. Prasad Jayanti. Wait-free computing. In Jean-Michel Hélary and Michel Raynal, editors, Distributed Algorithms, pages 19-50, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg. Google Scholar
  21. Leslie Lamport. Solved problems, unsolved problems and non-problems in concurrency. SIGOPS Oper. Syst. Rev., 19(4):34-44, 1985. URL: http://dx.doi.org/10.1145/858336.858339.
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