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 oneshot 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:126:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771009},
ISSN = {18688969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss DagstuhlLeibnizZentrum 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 