LIPIcs.DISC.2018.8.pdf
- Filesize: 0.55 MB
- 17 pages
Document
Allocate-On-Use Space Complexity of Shared-Memory Algorithms
Authors
-
Part of:
Volume:
32nd International Symposium on Distributed Computing (DISC 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-10-04
Cite AsGet BibTex
James Aspnes, Bernhard Haeupler, Alexander Tong, and Philipp Woelfel. Allocate-On-Use Space Complexity of Shared-Memory Algorithms. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.8
https://doi.org/10.4230/LIPIcs.DISC.2018.8
Abstract
Many fundamental problems in shared-memory distributed computing, including mutual exclusion [James E. Burns and Nancy A. Lynch, 1993], consensus [Leqi Zhu, 2016], and implementations of many sequential objects [Prasad Jayanti et al., 2000], are known to require linear space in the worst case. However, these lower bounds all work by constructing particular executions for any given algorithm that may be both very long and very improbable. The significance of these bounds is justified by an assumption that any space that is used in some execution must be allocated for all executions. This assumption is not consistent with the storage allocation mechanisms of actual practical systems.
We consider the consequences of adopting a per-execution approach to space complexity, where an object only counts toward the space complexity of an execution if it is used in that execution. This allows us to show that many known randomized algorithms for fundamental problems in shared-memory distributed computing have expected space complexity much lower than the worst-case lower bounds, and that many algorithms that are adaptive in time complexity can also be made adaptive in space complexity.
For the specific problem of mutual exclusion, we develop a new algorithm that illustrates an apparent trade-off between low expected space complexity and low expected RMR complexity. Whether this trade-off is necessary is an open problem.
For some applications, it may be helpful to pay only for objects that are updated, as opposed to those that are merely read. We give a data structure that requires no space to represent objects that are not updated at the cost of a small overhead on those that are.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed computing models
- Computing methodologies → Shared memory algorithms
- Software and its engineering → Mutual exclusion
Keywords
- Space complexity
- memory allocation
- mutual exclusion
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
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, 2011.
- Dan Alistarh, Hagit Attiya, Seth Gilbert, Andrei Giurgiu, and Rachid Guerraoui. Fast randomized test-and-set and renaming. In Nancy A. Lynch and Alexander A. Shvartsman, editors, Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings, volume 6343 of Lecture Notes in Computer Science, pages 94-108. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15763-9_9.
-
James Aspnes. Faster randomized consensus with an oblivious adversary. In 2012 ACM Symposium on Principles of Distributed Computing, pages 1-8, 2012.
- James Aspnes and Faith Ellen. Tight bounds for adopt-commit objects. Theory of Computing Systems, 55(3):451-474, 2014. URL: http://dx.doi.org/10.1007/s00224-013-9448-1.
- Hagit Attiya, Danny Hendler, and Philipp Woelfel. Tight RMR lower bounds for mutual exclusion and other problems. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 217-226, 2008. URL: http://dx.doi.org/10.1145/1374376.1374410.
- Hagit Attiya, Fabian Kuhn, C. Greg Plaxton, Mirjam Wattenhofer, and Roger Wattenhofer. Efficient adaptive collect using randomization. Distributed Computing, 18(3):179-188, 2006. URL: http://dx.doi.org/10.1007/s00446-005-0143-6.
- Michael A. Bender and Seth Gilbert. Mutual exclusion with o(log^2 log n) amortized work. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 728-737. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.84.
- James E. Burns and Nancy A. Lynch. Bounds on shared memory for mutual exclusion. Inf. Comput., 107(2):171-184, 1993. URL: http://dx.doi.org/10.1006/inco.1993.1065.
- P. Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, 21(2):194-203, March 1975. URL: http://dx.doi.org/10.1109/TIT.1975.1055349.
- Rati Gelashvili. On the optimal space complexity of consensus for anonymous processes. In Yoram Moses, editor, Distributed Computing: 29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9, 2015, Proceedings, pages 452-466, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. URL: http://dx.doi.org/10.1007/978-3-662-48653-5_30.
- 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: http://dx.doi.org/10.1145/2332432.2332436.
- George Giakkoupis and Philipp Woelfel. Randomized abortable mutual exclusion with constant amortized RMR complexity on the CC model. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 221-229. ACM, 2017. URL: http://dx.doi.org/10.1145/3087801.3087837.
- Danny Hendler and Philipp Woelfel. Randomized mutual exclusion with sub-logarithmic rmr-complexity. Distributed Computing, 24(1):3-19, 2011. URL: http://dx.doi.org/10.1007/s00446-011-0128-6.
- Prasad Jayanti, King Tan, and Sam Toueg. Time and space lower bounds for nonblocking implementations. SIAM J. Comput., 30(2):438-456, 2000. URL: http://dx.doi.org/10.1137/S0097539797317299.
- Leslie Lamport. A fast mutual exclusion algorithm. ACM Trans. Comput. Syst., 5(1):1-11, 1987. URL: http://dx.doi.org/10.1145/7351.7352.
-
Mark Moir and James H. Anderson. Wait-free algorithms for fast, long-lived renaming. Sci. Comput. Program., 25(1):1-39, 1995.
- Jae-Heon Yang and James H. Anderson. A fast, scalable mutual exclusion algorithm. Distributed Computing, 9(1):51-60, 1995. URL: http://dx.doi.org/10.1007/BF01784242.
- Leqi Zhu. A tight space bound for consensus. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 345-350. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897565.