Cited By
View all- Gelashvili R(2018)On the optimal space complexity of consensus for anonymous processesDistributed Computing10.1007/s00446-018-0331-931:4(317-326)Online publication date: 1-Aug-2018
Brief Announcement: A Tight Space Bound for Consensus
Author: 
Leqi ZhuAuthors Info & Claims
Pages 147 - 149
Abstract
Existing n-process randomized wait-free and obstruction-free consensus protocols from registers all use at least n registers. In 1992, it was proved that such protocols must use Ω(√n) registers. Recently, this was improved to Ω(n) registers in the anonymous setting, where processes do not have identifiers. We have recently proved that at least n-1 registers are needed, even if processes have identifiers.
References
[1]
Hagit Attiya and Keren Censor. Tight bounds for asynchronous randomized consensus. J. ACM, 55(5), 2008.
[2]
Hagit Attiya and Faith Ellen. Impossibility Results for Distributed Computing. Morgan & Claypool Publishers, 2014.
[3]
James Aspnes and Maurice Herlihy. Fast randomized consensus using shared memory. J. Algorithms, 11(3):441--461, 1990.
[4]
James Aspnes and Orli Waarts. Randomized consensus in expected o(n log(2\) n) operations per processor. SIAM J. Comput., 25(5):1024--1044, 1996.
[5]
James E. Burns and Nancy A. Lynch. Bounds on shared memory for mutual exclusion. Inf. Comput., 107(2):171--184, 1993.
[6]
Jack R. Bowman. Obstruction-free snapshot, obstruction-free consensus, and fetch-and-add modulo k. Technical Report TR2011--681, Dartmouth College, Computer Science, Hanover, NH, June 2011.
[7]
Zohir Bouzid, Michel Raynal, and Pierre Sutra. Brief Announcement: Anonymous Obstruction-free (n, k)-Set Agreement with n--k
[8]
1 Atomic Read/Write Registers. In Proceedings of 29th International Symposium on Distributed Computing (DISC 2015), volume 9363 of LNCS, pages 668--669. Springer, 2015.
[9]
Benny Chor, Amos Israeli, and Ming Li. Wait-free consensus using asynchronous hardware. SIAM J. Comput., 23(4):701--712, 1994.
[10]
Faith Ellen, Panagiota Fatourou, and Eric Ruppert. The space complexity of unbounded timestamps. Distributed Computing, 21(2):103--115, 2008.
[11]
Faith Ellen, Rati Gelashvili, Nir Shavit, and Leqi Zhu. A complexity-based hierarchy for multiprocessor synchronization. 2016. To appear in PODC '16.
[12]
Faith Ellen Fich, Maurice Herlihy, and Nir Shavit. On the space complexity of randomized synchronization. J. ACM, 45(5):843--862, 1998. A preliminary version appeared in PODC '93.
[13]
Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374--382, 1985.
[14]
Rati Gelashvili. On the optimal space complexity of consensus for anonymous processes. In Proceedings of 29th International Symposium on Distributed Computing (DISC 2015), volume 9363 of LNCS, pages 452--466. Springer, 2015.
[15]
George Giakkoupis, Maryam Helmi, Lisa Higham, and Philipp Woelfel. An O(√n) space bound for obstruction-free leader election. In Proceedings of 27th International Symposium on Distributed Computing (DISC 2013), volume 8205 of LNCS, pages 46--60. Springer, 2013.
[16]
George Giakkoupis, Maryam Helmi, Lisa Higham, and Philipp Woelfel. Test-and-set in optimal space. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC 2015), pages 615--623, 2015.
[17]
Rachid Guerraoui and Eric Ruppert. What can be implemented anonymously? In Proceedings of 19th International Symposium on Distributed Computing (DISC 2005), volume 3724 of LNCS, pages 244--259. Springer, 2005.
[18]
Maurice Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124--149, 1991.
[19]
Maryam Helmi, Lisa Higham, Eduardo Pacheco, and Philipp Woelfel. The space complexity of long-lived and one-shot timestamp implementations. J. ACM, 61(1):7:1--7:25, 2014.
[20]
Michael C. Loui and Hosame H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, 4:163--183, 1987.
[21]
Leqi Zhu. Brief Announcement: Tight Space Bounds for Memoryless Anonymous Consensus. In Proceedings of 29th International Symposium on Distributed Computing (DISC 2015), volume 9363 of LNCS, pages 665--666. Springer, 2015.
[22]
Leqi Zhu. A tight space bound for consensus. 2016. To appear in STOC '16.
Index Terms
- Brief Announcement: A Tight Space Bound for Consensus
Recommendations
A Tight Space Bound for Consensus
In the consensus problem, there are $n$ processes that each has a private input value. Each nonfaulty process must output a single value such that no two processes output different values and the output is the input value of some process. There are many ...
Brief announcement: byzantine agreement with a strong adversary in polynomial expected time
PODC '13: Proceedings of the 2013 ACM symposium on Principles of distributed computingIn a paper appearing in STOC 2013, we considered Byzantine agreement in the classic asynchronous message-passing model. The adversary is adaptive: it can determine which processors to corrupt and what strategy these processors should use as the ...
Brief Announcement: Asynchronous Secure Distributed Computing with Transferrable Non-equivocation Revisited
PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed ComputingIn this paper, we consider two fundamental problems in secure distributed computing, namely Asynchronous Byzantine Agreement (ABA) and Asynchronous Secure Multi-party Computation (ASMPC). Our focus is on the honest majority setting, involving a set of n ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2016 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 25 July 2016
Check for updates
Author Tags
Qualifiers
- Announcement
Conference
PODC '16: ACM Symposium on Principles of Distributed Computing
July 25 - 28, 2016
Illinois, Chicago, USA
Acceptance Rates
PODC '16 Paper Acceptance Rate 40 of 149 submissions, 27%;
Overall Acceptance Rate 740 of 2,477 submissions, 30%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 117Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 01 Jan 2025
Other Metrics
Citations
Cited By
View all- Gelashvili R(2018)On the optimal space complexity of consensus for anonymous processesDistributed Computing10.1007/s00446-018-0331-931:4(317-326)Online publication date: 1-Aug-2018
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in