Aspnes, James ;
Haeupler, Bernhard ;
Tong, Alexander ;
Woelfel, Philipp
AllocateOnUse Space Complexity of SharedMemory Algorithms
Abstract
Many fundamental problems in sharedmemory 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 perexecution 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 sharedmemory distributed computing have expected space complexity much lower than the worstcase 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 tradeoff between low expected space complexity and low expected RMR complexity. Whether this tradeoff 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.
BibTeX  Entry
@InProceedings{aspnes_et_al:LIPIcs:2018:9797,
author = {James Aspnes and Bernhard Haeupler and Alexander Tong and Philipp Woelfel},
title = {{AllocateOnUse Space Complexity of SharedMemory Algorithms}},
booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)},
pages = {8:18:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770927},
ISSN = {18688969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9797},
URN = {urn:nbn:de:0030drops97974},
doi = {10.4230/LIPIcs.DISC.2018.8},
annote = {Keywords: Space complexity, memory allocation, mutual exclusion}
}
2018
Keywords: 

Space complexity, memory allocation, mutual exclusion 
Seminar: 

32nd International Symposium on Distributed Computing (DISC 2018)

Issue date: 

2018 
Date of publication: 

2018 