Abstract
The optimal space complexity of consensus in shared memory is a decades-old open problem. For a system of n processes, no algorithm is known that uses a sublinear number of registers. However, the best known lower bound due to Fich, Herlihy, and Shavit requires \(\Omega (\sqrt{n})\) registers.
The special symmetric case of the problem where processes are anonymous (run the same algorithm) has also attracted attention. Even in this case, the best lower and upper bounds are still \(\Omega (\sqrt{n})\) and O(n). Moreover, Fich, Herlihy, and Shavit first proved their lower bound for anonymous processes, and then extended it to the general case. As such, resolving the anonymous case might be a significant step towards understanding and solving the general problem.
In this work, we show that in a system of anonymous processes, any consensus algorithm satisfying nondeterministic solo termination has to use \(\Omega (n)\) read-write registers in some execution. This implies an \(\Omega (n)\) lower bound on the space complexity of deterministic obstruction-free and randomized wait-free consensus, matching the upper bound and closing the symmetric case of the open problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Attiya, H., Ellen, F.: Impossibility results for distributed computing. Synthesis Lectures on Distributed Computing Theory 5(1), 1–162 (2014)
Aspnes, J., Herlihy, M.: Fast randomized consensus using shared memory. Journal of Algorithms 11(3), 441–461 (1990)
Ben-Or, M.: Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In: Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, PODC 1983, pp. 27–30. ACM, New York (1983)
Fich, F., Herlihy, M., Shavit, N.: On the space complexity of randomized synchronization. Journal of the ACM (JACM) 45(5), 843–862 (1998)
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM) 32(2), 374–382 (1985)
Giakkoupis, G., Helmi, M., Higham, L., Woelfel, P.: An \(O(\sqrt{n})\) space bound for obstruction-free leader election. In: Afek, Y. (ed.) DISC 2013. LNCS, vol. 8205, pp. 46–60. Springer, Heidelberg (2013)
Giakkoupis, G., Helmi, M., Higham, L., Woelfel, P.: Test-and-set in optimal space. In: Accepted to STOC 2015 (2014–2015)
Guerraoui, R., Ruppert, E.: What can be implemented anonymously? In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol. 3724, pp. 244–259. Springer, Heidelberg (2005)
Giakkoupis, G., Woelfel, P.: On the time and space complexity of randomized test-and-set. In: Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, pp. 19–28. ACM (2012)
Styer, E., Peterson, G.L.: Tight bounds for shared memory symmetric mutual exclusion problems. In: Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, pp. 177–191. ACM (1989)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gelashvili, R. (2015). On the Optimal Space Complexity of Consensus for Anonymous Processes. In: Moses, Y. (eds) Distributed Computing. DISC 2015. Lecture Notes in Computer Science(), vol 9363. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48653-5_30
Download citation
DOI: https://doi.org/10.1007/978-3-662-48653-5_30
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48652-8
Online ISBN: 978-3-662-48653-5
eBook Packages: Computer ScienceComputer Science (R0)