License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2019.26
URN: urn:nbn:de:0030-drops-102654
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10265/
Ellen, Faith ;
Gelashvili, Rati ;
Woelfel, Philipp ;
Zhu, Leqi
Space Lower Bounds for the Signal Detection Problem
Abstract
Many shared memory algorithms have to deal with the problem of determining whether the value of a shared object has changed in between two successive accesses of that object by a process when the responses from both are the same. Motivated by this problem, we define the signal detection problem, which can be studied on a purely combinatorial level. Consider a system with n+1 processes consisting of n readers and one signaller. The processes communicate through a shared blackboard that can store a value from a domain of size m. Processes are scheduled by an adversary. When scheduled, a process reads the blackboard, modifies its contents arbitrarily, and, provided it is a reader, returns a Boolean value. A reader must return true if the signaller has taken a step since the reader's preceding step; otherwise it must return false.
Intuitively, in a system with n processes, signal detection should require at least n bits of shared information, i.e., m >= 2^n. But a proof of this conjecture remains elusive. We prove a lower bound of m >= n^2, as well as a tight lower bound of m >= 2^n for two restricted versions of the problem, where the processes are oblivious or where the signaller always resets the blackboard to the same fixed value. We also consider a one-shot version of the problem, where each reader takes at most two steps. In this case, we prove that it is necessary and sufficient that the blackboard can store m=n+1 values.
BibTeX - Entry
@InProceedings{ellen_et_al:LIPIcs:2019:10265,
author = {Faith Ellen and Rati Gelashvili and Philipp Woelfel and Leqi Zhu},
title = {{Space Lower Bounds for the Signal Detection Problem}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {26:1--26:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-100-9},
ISSN = {1868-8969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10265},
doi = {10.4230/LIPIcs.STACS.2019.26},
annote = {Keywords: Signal detection, ABA problem, space complexity, lower bound}
}
|
Keywords: |
|
Signal detection, ABA problem, space complexity, lower bound |
|
Collection: |
|
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
12.03.2019 |
