James Aspnes, Bernhard Haeupler, Alexander Tong, and Philipp Woelfel. Allocate-on-use space complexity of shared-memory algorithms. 32nd International Symposium on Distributed Computing (DISC 2018), October 2018, pp. 8:1–8:17.
Many fundamental problems in shared-memory distributed computing, including mutual exclusion, consensus, and implementations of many sequential objects, 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.
@inproceedings{AspnesHTW2018,
author = {James Aspnes and
Bernhard Haeupler and
Alexander Tong and
Philipp Woelfel},
editor = {Ulrich Schmid and
Josef Widder},
title = {Allocate-On-Use Space Complexity of Shared-Memory Algorithms},
booktitle = {32nd International Symposium on Distributed Computing, {DISC} 2018,
New Orleans, LA, USA, October 15--19, 2018},
series = {LIPIcs},
volume = {121},
pages = {8:1--8:17},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
year = {2018},
url = {https://dx.doi.org/10.4230/LIPIcs.DISC.2018.8},
doi = {10.4230/LIPIcs.DISC.2018.8},
timestamp = {Mon, 08 Oct 2018 11:31:47 +0200},
biburl = {https://dblp.org/rec/bib/conf/wdag/AspnesHTW18},
bibsource = {dblp computer science bibliography, https://dblp.org}
}