LIPIcs.DISC.2023.46.pdf
- Filesize: 0.5 MB
- 6 pages
Document
Brief Announcement: The Space Complexity of Set Agreement Using Swap
Author
-
Part of:
Volume:
37th International Symposium on Distributed Computing (DISC 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-10-05
Cite As Get BibTex
Sean Ovens. Brief Announcement: The Space Complexity of Set Agreement Using Swap. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 46:1-46:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.DISC.2023.46
Abstract
We prove that any randomized wait-free n-process k-set agreement algorithm using only swap objects requires at least ⌈n/k⌉-1 objects. We also sketch a proof that any randomized wait-free consensus algorithm using only readable swap objects with domain size b requires at least (n-2)/(3b+1) objects.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed algorithms
Keywords
- space complexity
- consensus
- set agreement
- lower bound
- shared memory
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- James Aspnes and Maurice Herlihy. Fast randomized consensus using shared memory. Journal of Algorithms, 11(3):441-461, 1990. URL: https://doi.org/10.1016/0196-6774(90)90021-6.
- Zohir Bouzid, Michel Raynal, and Pierre Sutra. Anonymous obstruction-free (n, k)-set agreement with n-k+1 atomic read/write registers. Distributed Comput., 31(2):99-117, 2018. URL: https://doi.org/10.1007/s00446-017-0301-7.
- Jack R. Bowman. Obstruction-free snapshot, obstruction-free consensus, and fetch-and-add modulo k. Master’s thesis, Dartmouth College, Computer Science, 2011. URL: https://digitalcommons.dartmouth.edu/senior_theses/67.
- S. Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation, 105(1):132-158, 1993. URL: https://doi.org/10.1006/inco.1993.1043.
-
B. Chor, A. Israeli, and M. Li. Wait-free consensus using asynchronous hardware. SIAM J. Comput., 23:701-712, 1994.
- Faith Ellen, Rati Gelashvili, and Leqi Zhu. Revisionist simulations: A new approach to proving space lower bounds. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC '18, pages 61-70, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3212734.3212749.
- Faith Fich, Maurice Herlihy, and Nir Shavit. On the space complexity of randomized synchronization. J. ACM, 45(5):843-862, September 1998. A preliminary version appeared in PODC '93. URL: https://doi.org/10.1145/290179.290183.
- Sean Ovens. The space complexity of consensus from swap. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC'22, pages 176-186, New York, NY, USA, 2022. Association for Computing Machinery. URL: https://doi.org/10.1145/3519270.3538420.
- Sean Ovens. The space complexity of consensus from swap. CoRR, abs/2305.06507, 2023. URL: https://arxiv.org/abs/2305.06507.
- Leqi Zhu. A tight space bound for consensus. SIAM J. Comput., 50(3), 2019. A preliminary version appeared in STOC '16. URL: https://doi.org/10.1137/16M1096785.