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: https://drops.dagstuhl.de/opus/volltexte/2019/10265/
 Go to the corresponding LIPIcs Volume Portal

### Space Lower Bounds for the Signal Detection Problem

 pdf-format:

### 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

DROPS-Home | Fulltext Search | Imprint | Privacy