Document Open Access Logo

Consensus with Max Registers

Authors James Aspnes, He Yang Er

PDF
Thumbnail PDF

File

LIPIcs.DISC.2019.1.pdf
  • Filesize: 497 kB
  • 9 pages

Document Identifiers

Author Details

James Aspnes
  • Department of Computer Science, Yale University, New Haven, CT, USA
He Yang Er
  • Department of Computer Science, Yale University, New Haven, CT, USA

Funding

  • Aspnes, James: Supported in part by NSF grants CCF-1637385 and CCF-1650596.

Cite As Get BibTex

James Aspnes and He Yang Er. Consensus with Max Registers. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 1:1-1:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.DISC.2019.1

Abstract

We consider the problem of implementing randomized wait-free consensus from max registers under the assumption of an oblivious adversary. We show that max registers solve m-valued consensus for arbitrary m in expected O(log^* n) steps per process, beating the Omega(log m/log log m) lower bound for ordinary registers when m is large and the best previously known O(log log n) upper bound when m is small. A simple max-register implementation based on double-collect snapshots translates this result into an O(n log n) expected step implementation of m-valued consensus from n single-writer registers, improving on the best previously-known bound of O(n log^2 n) for single-writer registers.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • consensus
  • max register
  • single-writer register
  • oblivious adversary
  • shared memory

Metrics

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

References

  1. Karl Abrahamson. On Achieving Consensus Using a Shared Memory. In Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 291-302, 1988. Google Scholar
  2. Dan Alistarh and James Aspnes. Sub-logarithmic test-and-set against a weak adversary. In Distributed Computing: 25th International Symposium, DISC 2011, volume 6950 of Lecture Notes in Computer Science, pages 97-109. Springer-Verlag, September 2011. Google Scholar
  3. Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Corentin Travers. Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement. In Yingfei Dong, Ding-Zhu Du, and Oscar H. Ibarra, editors, ISAAC, volume 5878 of Lecture Notes in Computer Science, pages 943-953. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-10631-6_95.
  4. James Aspnes. A modular approach to shared-memory consensus, with applications to the probabilistic-write model. Distributed Computing, 25(2):179-188, May 2012. Google Scholar
  5. James Aspnes. Faster randomized consensus with an oblivious adversary. Distributed Computing, 28(1):21-29, February 2015. Google Scholar
  6. James Aspnes, Hagit Attiya, and Keren Censor-Hillel. Polylogarithmic concurrent data structures from monotone circuits. jacm, 59(1):2:1-2:24, February 2012. Google Scholar
  7. James Aspnes and Keren Censor-Hillel. Atomic Snapshots in O(log³ n) Steps Using Randomized Helping. In Yehuda Afek, editor, Distributed Computing: 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings, volume 8205 of Lecture Notes in Computer Science, pages 254-268. Springer Berlin Heidelberg, 2013. URL: https://doi.org/10.1007/978-3-642-41527-2_18.
  8. James Aspnes and Faith Ellen. Tight Bounds for Adopt-Commit Objects. Theory of Computing Systems, 55(3):451-474, 2014. URL: https://doi.org/10.1007/s00224-013-9448-1.
  9. James Aspnes, Bernhard Haeupler, Alexander Tong, and Philipp Woelfel. Allocate-On-Use Space Complexity of Shared-Memory Algorithms. In Ulrich Schmid and Josef Widder, editors, 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, volume 121 of LIPIcs, pages 8:1-8:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.8.
  10. James Aspnes and Orli Waarts. Randomized consensus in expected O(n log² n) operations per processor. SIAM J. Comput., 25(5):1024-1044, October 1996. Google Scholar
  11. Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing Memory Robustly in Message-Passing Systems. jacm, 42(1):124-142, 1995. URL: https://doi.org/10.1145/200836.200869.
  12. Hagit Attiya and Keren Censor-Hillel. Lower Bounds for Randomized Consensus under a Weak Adversary. SIAM J. Comput., 39(8):3885-3904, 2010. URL: https://doi.org/10.1137/090751906.
  13. Benny Chor, Amos Israeli, and Ming Li. Wait-Free Consensus Using Asynchronous Hardware. SIAM J. Comput., 23(4):701-712, 1994. Google Scholar
  14. Oksana Denysyuk and Philipp Woelfel. Are Shared Objects Composable Under an Oblivious Adversary? In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC '16, pages 335-344, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2933057.2933115.
  15. Eli Gafni. Round-by-Round Fault Detectors: Unifying Synchrony and Asynchrony (Extended Abstract). In Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, pages 143-152, 1998. URL: https://doi.org/10.1145/277697.277724.
  16. George Giakkoupis and Philipp Woelfel. On the time and space complexity of randomized test-and-set. In Darek Kowalski and Alessandro Panconesi, editors, ACM Symposium on Principles of Distributed Computing, PODC '12, Funchal, Madeira, Portugal, July 16-18, 2012, pages 19-28. ACM, 2012. URL: https://doi.org/10.1145/2332432.2332436.
  17. Wojciech Golab, Lisa Higham, and Philipp Woelfel. Linearizable Implementations Do Not Suffice for Randomized Distributed Computation. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC '11, pages 373-382, New York, NY, USA, 2011. ACM. URL: https://doi.org/10.1145/1993636.1993687.
  18. Maryam Helmi, Lisa Higham, and Philipp Woelfel. Strongly Linearizable Implementations: Possibilities and Impossibilities. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, PODC '12, pages 385-394, New York, NY, USA, 2012. ACM. URL: https://doi.org/10.1145/2332432.2332508.
  19. Maurice Herlihy. Wait-free Synchronization. ACM Trans. Program. Lang. Syst., 13(1):124-149, January 1991. URL: https://doi.org/10.1145/114005.102808.
  20. Prasad Jayanti. Robust wait-free hierarchies. J. ACM, 44(4):592-614, 1997. URL: https://doi.org/10.1145/263867.263888.
  21. Michael C. Loui and Hosame H. Abu-Amara. Memory Requirements for Agreement Among Unreliable Asynchronous Processes. In Franco P. Preparata, editor, Parallel and Distributed Computing, volume 4 of Advances in Computing Research, pages 163-183. JAI Press, 1987. Google Scholar
  22. Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal, and Corentin Travers. The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement. sicomp, 38(4):1574-1601, 2008. Google Scholar
  23. M. Pease, R. Shostak, and L. Lamport. Reaching Agreement in the Presence of Faults. jacm, 27(2):228-234, April 1980. Google Scholar
  24. Gary L Peterson and James E Burns. Concurrent reading while writing II: the multi-writer case. In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pages 383-392. IEEE, 1987. 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