1 Introduction
1.1 The Signal Detection Problem
Consider a system consisting of n + 1 processes, one signaller, s, and n readers, \(r_{1},\dots ,r_{n}\), that communicate through a shared blackboard. The blackboard can contain one value from a domain of size m. Processes are scheduled to take steps one at a time by an adversarial scheduler. Whenever a process takes a step, it atomically reads the blackboard and can modify its contents arbitrarily without interruption from other processes.
In the signal detection problem, each time a reader, ri, has taken a step, it must return a Boolean value. If ri has no preceding step, it can return either true or false. Otherwise, it must return true if and only if the signaller has taken a step since ri’s preceding step. We are concerned with how large m has to be for this problem to be solvable.
Advertisement
1.2 Simple Signal Detection Algorithms
For large or unbounded values of m, there are some simple solutions to the signal detection problem. For example, the blackboard could store an unbounded signal counter that is initially 0. Each time the signaller takes a step, it increments the counter. When a reader is scheduled, it simply memorizes the counter value, but does not change it. To detect whether a signal has occurred since its last step, a reader only needs to compare the current counter value with the one it read in its previous step. The value stored on the blackboard grows with the number of signals that have occurred, which can be unbounded.
A similar algorithm is for the signaller to increment the counter whenever it sees the value is odd and for each reader to increment the counter whenever it sees the value is even. A reader also memorizes the resulting value of the counter. It detects whether a signal has occurred since its last step by comparing this value with the value it previously memorized. If there are many consecutive steps by the signaller, the value of the counter grows more slowly than in the previous algorithm.
The following simple algorithm stores an n-bit string \((b_{1},\dots ,b_{n})\) on the blackboard, i.e. the domain size is m = 2n. Initially, \(b_{1}=\dots =b_{n}=0\). Whenever the signaller takes a step, it sets all bits to 1. For each \(j\in \{1,\dots ,n\}\), reader rj resets bit bj to 0, it returns false if the old value of bj was 0, and it returns true if the old value of bj was 1.
1.3 ABA Detection
Signal detection is related to the fundamental ABA detection problem in asynchronous shared memory systems. In such systems, a process that observes the same value A in some shared object in two successive accesses cannot tell whether the value of the object remained unchanged between them. More formally, it cannot distinguish between an execution in which the shared object did not change and an execution in which the value of the object changed from A to some other value B and then back to A. Many shared memory algorithms have to deal with this problem.
Advertisement
A well-known example is the double-collect algorithm for performing an atomic scan of an array [1]: A process repeatedly performs a collect (reading all components of the array one by one) until the sequences of values read in two consecutive collects are the same. This algorithm is only correct (linearizable) if no ABAs occur, meaning that any two consecutive reads of the same array entry return the same value if and only if the value of the array entry was not changed between the two reads. This is because it can be shown that, provided no ABAs occur, the sequence returned by a scan must be the contents of the array at the end of its second last collect and the beginning of its last collect. However, in executions in which ABAs occur, this implementation might incorrectly return a sequence of values that was not the contents of the array at any point during the execution.
A standard approach to dealing with ABAs is tagging, as introduced by IBM [4], whereby a shared object gets augmented with a tag that changes with every write operation. If tags are never reused, the ABA problem can be avoided. From a theory perspective, this solution is unsatisfactory: If there is no bound on the length of executions, then unbounded sized objects are required to accommodate ever increasing tag values. Even though, in many practical scenarios, a system may never run out of tags, it is often desirable or even necessary to use an entire word for data. In such scenarios, the tag associated with a data word could be stored in a subsequent memory location and double-width atomic instructions could be used. However, these are not supported by most of today’s mainstream architectures [7].
In some cases, it is possible to store the tag in an unrelated memory location [6], but this requires technically difficult algorithms and tedious correctness proofs. As a result, algorithm designers often deal with ABAs in an ad-hoc way. For example, a pair of handshaking bits between each pair of processes can be used to detect changes in the components of the array in a wait-free implementation of a snapshot object [1]. Such solutions are algorithm specific and require individual correctness proofs.
ABAs can also occur when using compare-and-swap (CAS) objects, which are provided by most existing multiprocessor systems and are much more powerful than read/write registers. Algorithms devised in theoretical research often use load-linked store-conditional (LL/SC) objects, which do not suffer from ABAs, and can easily replace CAS objects. Unfortunately, only a small number of multiprocessor systems provide LL/SC and they are weaker than the LL/SC specification used in theoretical research. Variants of LL/SC available in modern hardware restrict programmers severely in how the objects can be used [9], and “offer little or no help with preventing the ABA problem” [8].
To study the complexity of ABA detection, Aghazadeh and Woelfel [2] defined an ABA detecting register, which extends a read/write register with the ability to detect ABAs. It supports the operations
DWrite(x), which changes the value of the object to x, and DRead(), which returns the current value of the object together with a Boolean flag. The flag is true if and only if the process has previously performed DRead() and, since its last preceding DRead(), some process performed DWrite(). The authors proved space lower bounds and time-space-tradeoffs for linearizable implementations of ABA detecting registers in shared memory systems with n processors that provide bounded atomic base objects, such as bounded read/write registers or bounded CAS objects. For example, if only bounded read/write registers are available as base objects, then at least n − 1 of them are needed to obtain an obstruction-free ABA detecting register. If bounded CAS objects are also available, then any implementation using m base objects has step-complexity Ω(n/m).All the lower bound results in [2] are specific to the base objects provided by the system, and provide no insights for systems using different sets of base objects. But we conjecture that there is a large, general lower bound for the amount of information that needs to be stored in a system for processes to detect ABAs: Intuitively, the system state needs to keep track of whether the value of the object has changed since each process last accessed the object. This requires at least n bits of information. Hence, it seems believable that detecting ABAs in any system with arbitrarily powerful base objects requires at least n bits of information to be stored either in the base object or in the hardware implementing the base objects (for example, implementing LL/SC objects). Using the reasonable assumption that a single base object can store \(O(\log n)\) bits of information, this would imply that \({\Omega }(n/\log n)\) base objects are required for implementing a single ABA detecting object.
The signal detection problem is a restricted version of the problem of detecting ABAs in asynchronous shared memory systems, stripped down to the essentials necessary for determining the information theoretic requirements. Its definition is self-contained, and the problem can be studied without any background knowledge of shared memory systems. If n processes can detect ABAs in a standard asynchronous shared memory system with arbitrarily strong primitives, then they can also solve signal detection. A reader simply remembers the last value it read from the blackboard. When it reads the blackboard again, it returns true if it sees a different value or it detected an ABA; otherwise it returns false. Therefore, if signal detection requires that the blackboard has domain size at least m∗, then \(\log _{2} m^{\ast }\) is a lower bound for the number of bits needed for ABA detection.
1.4 Results
We conjecture that any solution to the signal detection problem requires the domain size, m, of the blackboard to be at least 2n. Although we prove this conjecture when there are n ≤ 2 readers, a proof when n ≥ 3 has eluded us. This simply defined combinatorial problem does not seem to have a simple solution. Even a proof of a polynomial lower bound is surprisingly non-trivial. We show the following result in Section 6.
Theorem 1
In any algorithm for the signal detection problem, the blackboard has domain size at least n(n + 1)/2.
To obtain better understanding, we consider several restricted versions of the signal detection problem and prove tight upper and lower bounds for them.
First, we consider the b-read-bounded version of signal detection, where no reader takes more than b steps, but the signaller can take arbitrarily many steps. In this case, the second algorithm from Section 1.2 uses a domain of size 2bn + 1. We show how to improve this algorithm.
Theorem 2
For b ≥ 2, the b-read-bounded signal detection problem can be solved using a blackboard with domain size (b − 1)n + 1.
Thus, the b-read-bounded problem is strictly easier than the unrestricted problem when b ≤⌈n/2⌉. For b = 2, we also prove that this algorithm is optimal.
Theorem 3
In any algorithm for the 2-read-bounded signal detection problem, the blackboard has domain size at least n + 1.
Next, we consider signal detection when the actions of the signaller do not depend on what steps the readers have taken. Signal detection with fixed signals is the special case where the signaller writes the same sequence of values to the blackboard in every execution. Note that the simple algorithm above with m = 2n uses fixed signals.
Theorem 4
In any algorithm for the signal detection problem with fixed signals, the blackboard has domain size at least 2n.
Then we consider the case of write oblivious processes. Here each process p is equipped with a fixed function \(f_{p}:\{0,\dots ,m-1\}\to \{0,\dots ,m-1\}\). When taking a step it replaces the blackboard contents x with fp(x). Hence, what a process writes to the blackboard is independent of the internal state of the process. However, the return value of a reader’s step may depend on its internal state. In the simple algorithm above, which uses m = 2n blackboard values, processes are write oblivious. We prove that, when processes are write oblivious, no better algorithm exists.
Theorem 5
In any algorithm for the signal detection problem with write oblivious processes, the blackboard has domain size at least 2n.
The signal detection problem with write oblivious processes is similar to determining the minimum size of a dictionary in a sequential system. A dictionary supports three operations, insert(x), query(x), and reset(), where x is a parameter chosen from a domain of size n. A call to query(x) returns true if there has been an insert(x) operation since the last reset() operation or since the beginning of the execution, if there has been no reset(). Otherwise, it returns false. A dictionary implemented using b(n) bits immediately yields a solution to the signal detection problem with oblivious processes as follows: A blackboard with m = 2b(n) possible values is used to store the dictionary. When a signaller takes a step, it simulates a reset() operation on the dictionary stored on the blackboard. Similarly, when reader ri takes a step, it simulates query(i) followed by insert(i) on the dictionary and then returns the return value of its query operation. However, an arbitrary solution to the signal detection problem does not seem to yield an implementation of a dictionary. The difficulty is that the return value of a step by a reader ri can depend on the state of the reader and, thus, its entire past execution. In contrast, the result of a query(i) operation is only a function of the state of the dictionary. Hence, the n-bit information theory lower bound for implementing a dictionary cannot be used to obtain Theorem 5.
In the simple algorithm that uses m = 2n blackboard values, the response each reader returns also does not depend on its internal state, but only on the contents of the blackboard. We call such processes response oblivious. The same lower bound holds for any algorithm with response oblivious processes, even if the algorithm supports only 2 steps by each reader.
Theorem 6
In any algorithm for 2-read-bounded signal detection with response oblivious processes, the blackboard has domain size at least 2n.
Theorem 2 implies that, for the unrestricted signal detection problem when there is only n = 1 reader, the domain size is at least 2 = 2n. In Section 7, we investigate the unrestricted signal detection problem for the case of n = 2 readers. First, we prove a tight lower bound of 4 for the size of the blackboard domain. Then we present an algorithm for two readers, r1 and r2, which uses a bounded number of blackboard values, and for which every reachable configuration C satisfies the following property: As long as only readers take steps starting in C, at most three different blackboard values are obtained. This observation indicates that a tight lower bound of m ≥ 2n for n readers for the unrestricted signal detection problem may have to be fundamentally different from our lower bound proof for fixed signals. In that proof, we showed that one can reach a configuration, C, from which 2n different blackboard values result from the 2n schedules that are sub-sequences of \((r_{1},\dots ,r_{n})\). In our third simple algorithm for n readers in Section 1.2, each execution that ends with the signaller taking a step results in a configuration with this property. But our two reader algorithm indicates that a lower bound proof for the unrestricted signal detection problem cannot rely on this property.
2 Preliminaries
We consider a deterministic, asynchronous system in which n + 1 processes, \(s,r_{1},\dots ,r_{n}\) communicate with one another using a single shared blackboard. Each time a process takes a step, it atomically reads the blackboard, may change the value of the blackboard based on its state and the value it read, and updates its state.
A configuration C consists of a value, v(C), for the blackboard and a state for each process. An execution is an alternating sequence of configurations and steps, starting and ending with a configuration, such that each step can be performed in the configuration that precedes it, resulting in the configuration that follows it. Configuration C is reachable if there is an execution starting with an initial configuration and ending with C. For any set of processes, P, a P-only execution is an execution in which only processes in P take steps in the execution. A solo execution is a P-only execution in which P contains only one process, i.e., all steps in the execution are by the same process.
A schedule is a sequence of processes (in which the same process can occur multiple times). A P-only schedule is a schedule in which only processes in P appear. For any deterministic algorithm and for any configuration C, a schedule determines a unique execution starting from C in which the processes take steps in the order specified by the schedule. If α is a finite schedule, then Cα denotes the configuration at the end of this execution.
Two configurations, C and \(C^{\prime }\), are indistinguishable to a set of processes, P, if \(\mathsf {v}(C) = \mathsf {v}(C^{\prime })\) and each process in P has the same state in C as it does in \(C^{\prime }\). If C and \(C^{\prime }\) are indistinguishable to P and α is a finite P-only schedule, then the same sequence of steps is taken in the executions determined by α from C and \(C^{\prime }\). Moreover, Cα and \(C^{\prime }\alpha \) are indistinguishable to P.
Given a set of readers, R, let R denote the schedule consisting of one occurrence of each reader in R, in order of their identifiers, and let M(R) denote the set {ri : i ≤ j for some rj ∈ R} of all readers whose identities are less than or equal to the largest identity of the readers in R. In particular, M(∅) = ∅. For example, \(M(\{r_{1},r_{4},r_{8}\}) = \{r_{1},r_{2},\dots ,r_{8}\}\). Notice that, for any two sets of readers R and \(R^{\prime }\), either \(M(R) \subseteq M(R^{\prime })\) or \(M(R^{\prime }) \subseteq M(R)\). There are n + 1 such sets, i.e., \(|\{M(R) : R \subseteq \{r_{1},\dots ,r_{n}\}\}| = n+1\).
Lemma 1
For every signal detection algorithm in which the domain size of the blackboard is finite, there is a reachable configuration D such that, for every set of readers, T, v(DTsβT) = v(DT) for some (M(T) ∪{s})-only schedule βT.
Proof
Consider any signal detection algorithm. Assume that, for each reachable configuration C, there is a set of readers, T, such that v(CTsβ)≠v(CT) for all (M(T) ∪{s})-only schedules β. We define an infinite sequence of reachable configurations as follows. Let C0 be the initial configuration. Let j ≥ 1 and suppose that Cj− 1 is a reachable configuration. Let Tj be a set of readers such that v(Cj− 1Tjsβ)≠v(Cj− 1Tj) for all (M(Tj) ∪{s})-only schedules β. The existence of Tj follows from the assumption, since Cj− 1 is reachable. Let Cj = Cj− 1Tjs.
Since there is only a finite number of readers, there exists a set M such that \(\{ j \in \mathbb {Z}^{+} : M(T_{j}) = M\}\) is infinite. Let M be the largest such set, let \(J = \{ j \in \mathbb {Z}^{+} : M(T_{j}) = M\}\), and let \(k^{*} = {\min \limits } \{ k \geq 1 : M(T_{j}) \subseteq M \textrm { for all } j \geq k \}\). Note that, for all k,ℓ ∈ J such that k∗≤ k < ℓ, the schedule Tk+ 1sTk+ 2s⋯Tℓ is (M ∪{s})-only. Thus, by definition of Tk, v(CkTk)≠v(CkTksTk+ 1s⋯Tℓ) = v(CℓTℓ). Hence, the domain size of the blackboard is infinite. □
3 Read-Bounded Signal Detection
In the b-read-bounded signal detection problem, no reader takes more than b steps, but the signaller can take arbitrarily many steps.
Consider the following algorithm that solves this restricted problem for b = 2 using a blackboard with domain size m = n + 1:
-
The blackboard initially has value 0.
-
Whenever s takes a step, it resets the blackboard contents to 0.
-
When ri takes its first step, it changes the blackboard contents to i if it reads 0; otherwise it leaves the blackboard unchanged. In either case, ri locally stores the value vi≠ 0 of the blackboard immediately after its first step and returns true.
-
When ri takes its second step, it returns false if it reads vi from the blackboard; otherwise it returns true. It does not change the value of the blackboard in either case.
Note that only the signaller changes the blackboard contents to 0 and readers only change the blackboard contents from 0. Thus, if the signaller does not take any steps between the two steps of reader ri, then the value of the blackboard remains vi during this interval and ri returns false.
If the signaller does take a step between the two steps of reader ri, then the blackboard is reset to 0. Consider the last step, \(S^{\prime }\), by the signaller during this interval. If no reader takes its first step after \(S^{\prime }\), but before the second step by ri, then ri will read 0 from the blackboard on its second step and return true. Otherwise, consider the first step after \(S^{\prime }\) in which a reader rj takes its first step. It will change the blackboard contents to j. Note that j≠vi, since rj is the only reader that can change the blackboard contents to j and rj has not previously taken a step. In this case, ri will read j from the blackboard on its second step and return true.
A similar algorithm works for b-read-bounded signal detection for any larger b, but the size of the blackboard domain also increases.
Theorem 2
For b ≥ 2, the b-read-bounded signal detection problem can be solved using a blackboard with domain size (b − 1)n + 1.
Proof
Consider the following algorithm for a signaller and n readers:
The counter ci is initially 0. Before changing the blackboard to (i,ci), reader ri increments ci and checks that it is less than b. Hence, the blackboard only contains values in its domain. Note that only ri changes the blackboard to (i,j) for 1 ≤ j ≤ b − 1. Thus, whenever the blackboard is changed to a nonzero value, its new value is a value that it never previously had.
-
The blackboard domain is {0}∪{(i,j) : 1 ≤ i ≤ n and 1 ≤ j ≤ b − 1}. The blackboard initially has value 0.
-
Whenever s takes a step, it resets the blackboard contents to 0.
-
Each reader ri has a local b-bounded counter ci, which is initially 0 and is incremented each time ri reads 0 from the blackboard. It also has a local variable vi in which it stores a non-zero value from the blackboard domain. It initially contains (i,1).
-
When ri takes a step, it reads the blackboard. It will return false if the value read is the same as the value stored in vi. Otherwise, it returns true. If the value read is non-zero, it stores the result in vi and does not change the blackboard. If ri reads 0, it increments ci and, if ci < b, it changes the blackboard to (i,ci) and also sets vi to the same value. When ci = b, reader ri can take no additional steps.
Since the blackboard initially contains 0 and vi initially contains (i,1), the first time ri takes a step, it will read a value different from vi and will return true.
At the end of each step by ri, the blackboard contains vi. Readers only change the blackboard when it contains 0. Thus, if the signaller does not take any steps between two steps of reader ri, then the value of the blackboard remains vi during this interval and ri returns false.
If the signaller does take a step between two consecutive steps of reader ri, then the blackboard is reset to 0. Then either the blackboard has value 0 when it is later read during the second of these steps, or some other process changed the blackboard to have a value it never previously had. In either case, its value is not equal to vi and ri returns true.
The counter ci is incremented each time ri reads 0 from the blackboard. Since it is initially 0 and otherwise is not incremented, it records the number of times that ri reads 0 from the blackboard. If ri takes at most b steps, then ci < b at the beginning of each of its steps, so ri does not stop prematurely. □
Note that, if b ≤⌈n/2⌉, then (b − 1)n + 1 ≤ (n − 1)n/2 + 1 < n(n + 1)/2 for n ≥ 2. Hence, the domain size used in this algorithm is strictly less than the lower bound in Theorem 1 for any algorithm solving signal detection with an unbounded number of reads.
When b = 2, we can show that the domain size of this algorithm cannot be any smaller. The following simple lemma is the key to our lower bound for 2-read-bounded signal detection.
Lemma 2
Let C be a configuration and let r be a reader. If α is an \((\{r_{1},\dots ,r_{n}\} - \{r\})\)-only schedule and β is a \((\{s,r_{1},\dots ,r_{n}\}-\{r\})\)-only schedule, then, for every configuration D in the execution determined by α from \(C^{\prime } = Cr\) and for every configuration E in the execution determined by β from \(C^{\prime }\alpha s\), v(D)≠v(E).
Proof
Suppose not. Then there are some such configurations D and E such that v(D) = v(E). Since r does not occur in the schedule αsβ, D and E are indistinguishable to r. Note that r must return false if it takes a step in configuration D, because s has not taken any steps since r last took a step. However, r must return true if it takes a step in configuration E, because s has taken a step since r last took a step. This is impossible, because D and E are indistinguishable to r. □
We can now prove Theorem 3.
Theorem 3
In any algorithm for the 2-read-bounded signal detection problem, the blackboard has domain size at least n + 1.
Proof
Let C0 be the initial configuration. For 1 ≤ j ≤ n, let Cj = Cj− 1srj and let Cn+ 1 = Cns. Let α denote the empty schedule.
For 1 ≤ i < n, let β denote the schedule ri+ 1⋯srns. By Lemma 2 with \(C^{\prime } = C_{i}\) and r = ri, v(Ci)≠v(E) for all configurations E in the execution starting from Cis determined by β. In particular, v(Ci)≠v(Cj) for i + 1 ≤ j ≤ n + 1.
For i = n, let β denote the empty schedule. By Lemma 2 with \(C^{\prime } = C_{n}\) and r = rn, v(Cn)≠v(Cn+ 1).
Hence \(|\{\mathsf {v}(C_{1}),\dots ,\mathsf {v}(C_{n}), \mathsf {v}(C_{n+1})\}| = n+1\). □
4 Fixed Signals
Suppose that, whenever the signaller takes a step, the resulting value of the blackboard does not depend on what its value was. In other words, for all k ≥ 1, there exists a value vk in the blackboard domain such that, immediately after the signaller’s k’th step in any execution, the blackboard has value vk. For example, this is the case if the signaller always resets the contents of the blackboard to a fixed value, say 0. Using Lemma 1, we can show that, under this restriction, the blackboard has domain size at least 2n.
Theorem 4
In any algorithm for the signal detection problem with fixed signals, the blackboard has domain size at least 2n.
Proof
Suppose the domain size of the blackboard is finite. Then, by Lemma 1, it is possible to reach a configuration D such that, for any set of readers T, there is a (M(T) ∪{s})-only schedule βT such that v(DTsβT) = v(DT).
Suppose there exist two different sets of readers \(R, R^{\prime } \subseteq \{r_{1},\dots ,r_{n}\}\) such that \(\mathsf {v}(D\mathbf {R}) = \mathsf {v}(D\mathbf {R^{\prime }})\). Without loss of generality, R = TxX and \(\mathbf {R^{\prime }} = \mathbf {T} \mathbf {X^{\prime }}\), where \(x \in R - R^{\prime }\) and T is the longest common prefix of R and \(\mathbf {R}^{\prime }\). Note that M(T) is disjoint from \(\{x\} \cup X \cup X^{\prime }\), since R and \(\mathbf {R}^{\prime }\) are sorted. By definition of D, there is a (M(T) ∪{s})-only schedule βT such that v(DTsβT) = v(DT). The signaller s occurs exactly once in each of the schedules Ts and Txs. Since s has fixed signals, v(DTs) = v(DTxs). The configurations DTs and DTxs are indistinguishable to M(T), so, by induction on the length of β, the configurations DTsβ and DTxsβ are indistinguishable to M(T) for every prefix β of βT. In particular, v(DTxsβT)= v(DTsβT) = v(DT). Since M(T) ∪{s,x} is disjoint from \(X^{\prime }\), configurations DTxsβT and DT are indistinguishable to the set of readers \(X^{\prime }\). Thus \(\mathsf {v}(D\mathbf {T}xs{\upbeta }_{T}\mathbf {X^{\prime }}) = \mathsf {v}(D\mathbf {T}\mathbf {X^{\prime }}) = \mathsf {v}(D\mathbf {R^{\prime }}) = \mathsf {v}(D\mathbf {R}) = \mathsf {v}(D\mathbf {T}x\mathbf {X})\). Since \( x \notin M(T) \cup X \cup X^{\prime } \cup \{s\}\), it follows that \(D\mathbf {T}xs{\upbeta }_{T}\mathbf {X^{\prime }}\) and DTxX are indistinguishable to x. Note that x must return false if it takes a step in configuration DTxX, because s has not taken any steps since x last took a step. However, x must return true if it takes a step in configuration \(D\mathbf {T}xs{\upbeta }_{T}\mathbf {X^{\prime }}\), because s has taken a step since x last took a step. This is impossible, because these two configurations are indistinguishable to x.
Hence, \(\mathsf {v}(D\mathbf {R}) \neq \mathsf {v}(D\mathbf {R^{\prime }})\) for all different sets of readers R and \(R^{\prime }\). It follows that \(|\{\mathsf {v}(D\mathbf {R}) : R \subseteq \{r_{1},\dots ,r_{n}\}\}| = 2^{n}\). □
5 Oblivious Processes
In this section, we consider processes whose actions are oblivious to their states, either when writing to the blackboard or responding to a read.
Recall that a process is write oblivious if what it writes to the blackboard in a step only depends on the value of the blackboard at the beginning of that step. We prove that the simple algorithm in Section 1.2 with domain size 2n is optimal if both the signaller and the readers are write oblivious.
Theorem 5
In any algorithm for the signal detection problem with write oblivious processes, the blackboard has domain size at least 2n.
Proof
Suppose the domain size of the blackboard is finite. For any (possibly empty) set of readers R and any positive integer i, consider the schedule (sR)i which consists of sR repeated i times. Because the domain size of the blackboard is finite, there exist 0 < i < j such that v(C0(sR)i) = v(C0(sR)j), where C0 is the initial configuration.
Let \(R^{\prime } \neq R\) be a different set of readers and let \(0 < i^{\prime } < j^{\prime }\) be such that \(\mathsf {v}(C_{0}(s\mathbf {R^{\prime }})^{i^{\prime }}) = \mathsf {v}(C_{0} (s\mathbf {R^{\prime }})^{j^{\prime }})\). Without loss of generality, suppose there is a reader \(r_{k} \in R^{\prime } - R\).
To obtain a contradiction, assume that \(\mathsf {v}(C_{0}(s\mathbf {R})^{i}) = \mathsf {v}(C_{0}(s\mathbf {R^{\prime }})^{i^{\prime }})\). Since processes are write oblivious, it follows that \(\mathsf {v}(C_{0} (s\mathbf {R^{\prime }})^{i^{\prime }}(s\mathbf {R})^{j-i}) = \mathsf {v}(C_{0} (s\mathbf {R})^{i} (s\mathbf {R})^{j-i}) = \mathsf {v}(C_{0} (s\mathbf {R})^{j}) = \mathsf {v}(C_{0} (s\mathbf {R})^{i}) = \mathsf {v}(C_{0}(s\mathbf {R^{\prime }})^{i^{\prime }})\). Since rk takes no steps in (sR)j−i, configurations \(C_{0} (s\mathbf {R^{\prime }})^{i^{\prime }}(s\mathbf {R})^{j-i}\) and \(C_{0}(s\mathbf {R^{\prime }})^{i^{\prime }}\) are indistinguishable to rk. The signaller has taken a step after rk’s last step in the execution determined by \((s\mathbf {R^{\prime }})^{i^{\prime }}(s\mathbf {R})^{j-i}\) starting from C0, so rk must return true if it takes a step in configuration \(C_{0} (s\mathbf {R^{\prime }})^{i^{\prime }}(s\mathbf {R})^{j-i}\). However, the signaller has not taken a step after rk’s last step in the execution determined by \((s\mathbf {R^{\prime }})^{i^{\prime }}\) starting from C0, so rk must return false if it takes a step in configuration \(C_{0}(s\mathbf {R^{\prime }})^{i^{\prime }}\). This is impossible, so \(\mathsf {v}(C_{0}(s\mathbf {R})^{i}) \neq \mathsf {v}(C_{0}(s\mathbf {R^{\prime }})^{i^{\prime }})\).
Since this holds for any two different sets of readers R and \(R^{\prime }\), it follows that the blackboard domain has size at least 2n. □
We now consider response oblivious readers, whose responses only depend on the contents of the blackboard, but not their current state. However, processes can modify the blackboard based on both the blackboard contents and their current state. Even for the 2-read-bounded signal detection problem, at least 2n different blackboard values are necessary when readers are response oblivious.
Theorem 6
In any algorithm for 2-read-bounded signal detection with response oblivious processes, the blackboard has domain size at least 2n.
Proof
Consider a set of readers R and let Q = {r1,…,rn}− R. Note that, in the execution from the initial configuration C0 determined by schedule QsR, each reader takes exactly one step.
Let \(R^{\prime } \neq R\) be a different set of readers and let \(Q^{\prime } = \{r_{1},\ldots ,r_{n}\} -R^{\prime }\). Without loss of generality, suppose there is a reader \(r_{k} \in R^{\prime } - R\). In the execution from C0 determined by schedule \(\mathbf {Q^{\prime }}s\mathbf {R^{\prime }}\), reader rk takes a step after the signaller’s last step, so rk must return false if it takes a step in configuration \(C_{0} \mathbf {Q^{\prime }}s\mathbf {R^{\prime }}\). However, in the execution from C0 determined by schedule QsR, reader rk does not take a step after the signaller’s last step, so rk must return true if it takes a step in configuration C0QsR. By response obliviousness, this implies that \(\mathsf {v}(C_{0}\mathbf {Q}s\mathbf {R}) \neq \mathsf {v}(C_{0}\mathbf {Q^{\prime }}s\mathbf {R^{\prime }})\).
Since this holds for any two different sets of readers R and \(R^{\prime }\), the blackboard domain has size at least 2n. □
6 The General Setting
Let \({\mathcal M} = \{M(R) : R \subseteq \{r_{1},\dots ,r_{n}\}\}\). Recall that \(|{\mathcal M} | = n+1\). For any schedule α, let M(α) denote M(R), where R is the set of readers that take steps in α.
Lemma 3
If the blackboard can only store a finite number of different values, then, from any configuration, it is possible to reach a configuration D such that, for any schedules α and β, there exists an (M(α) ∪ M(β) ∪{s})-only schedule γ such that v(Dαγ) = v(Dβ).
Proof
Let C0 be an arbitrary configuration. Suppose that, for each configuration C reachable from C0, there are two schedules, α and β, such that, for each (M(α) ∪ M(β) ∪{s})-only schedule γ, v(Cαγ)≠v(Cβ).
We inductively define an infinite sequence of configurations Cj, for j ≥ 0, such that Cj+ 1 is reachable from Cj. Given Cj, which is reachable from C0, there exist two schedules, αj+ 1 and βj+ 1, such that v(Cjαj+ 1γ)≠v(Cjβj+ 1) for all (M(αj+ 1) ∪ M(βj+ 1) ∪{s})-only schedules γ. Let Cj+ 1 = Cjαj+ 1.
For j ≥ 1, let \(M_{j} = M(\alpha _{j}) \cup M({\upbeta }_{j}) \in {\mathcal M}\). Since \({\mathcal M}\) is finite, there exists at least one set that is equal to Mj for an infinite number of j’s. Let \(M^{\prime }\) denote the largest such set and let \(J = \{ j \geq 1 : M_{j} = M^{\prime } \}\) be the set of indices of the occurrences of \(M^{\prime }\). Let \(k^{*} = {\min \limits } \{ k \geq 1 : M_{j} \subseteq M^{\prime } \textrm { for all } j \geq k \}\) be the first index after which no set larger than \(M^{\prime }\) occurs. Note that, if k∗≤ k < ℓ, then γ = αk+ 1⋯αℓ− 1βℓ is an \((M^{\prime } \cup \{s\})\)-only schedule. Hence, if k,ℓ ∈ J, then v(Ck− 1βk)≠v(Ck− 1αkγ) = v(Cℓ− 1βℓ). Thus {v(Ck− 1βk) : k ≥ k∗ and k ∈ J} is an infinite set of values that can appear on the blackboard. □
For 0 ≤ i < j ≤ n, let δ(i,j) denote the schedule \(r_{1} s r_{2} s {\dots } r_{i} s r_{i+1} r_{i+2}{\dots } r_{j}\). For example, δ(0,3) = r1r2r3 and δ(2,5) = r1sr2sr3r4r5. Note that δ(i,j) contains i occurrences of s.
Lemma 4
Let D be a reachable configuration such that, for any schedules α and β, there exists an (M(α) ∪ M(β) ∪{s})-only schedule γ such that v(Dαγ) = v(Dβ). If 0 ≤ i < j ≤ n, \(0 \leq i^{\prime } < j^{\prime } \leq n\), and either \(i \neq i^{\prime }\) or \(j \neq j^{\prime }\), then \(\mathsf {v}(D\delta {(i,j)}) \neq \mathsf {v}(D\delta {(i^{\prime },j^{\prime })})\).
Proof
First consider the case when \(i \neq i^{\prime }\). Without loss of generality, suppose that \(i < i^{\prime }\). The state of reader ri+ 1 is the same in configurations Dδ(i,j) and \(D\delta {(i^{\prime },j^{\prime })}\). In configuration Dδ(i,j), if ri+ 1 takes a step, it must return false, because s has not taken any steps since ri+ 1 last took a step. In configuration \(D\delta {(i^{\prime },j^{\prime })}\), if ri+ 1 takes a step, it must return true, because s has taken \(i^{\prime } - i\) steps since ri+ 1 last took a step. If \(\mathsf {v}(D\delta {(i,j)}) = \mathsf {v}(D\delta {(i^{\prime },j^{\prime })})\), then configurations Dδ(i,j) and \(D\delta {(i^{\prime },j^{\prime })}\) are indistinguishable to ri+ 1, which is impossible. Thus \(\mathsf {v}(D\delta {(i,j)}) \neq \mathsf {v}(D\delta {(i^{\prime },j^{\prime })})\).
Now consider the case when \(i = i^{\prime }\) and \(j \neq j^{\prime }\). Without loss of generality, suppose that \(j < j^{\prime }\), so \(\delta {(i^{\prime },j^{\prime })} = \delta {(i,j)}r_{j+1} {\cdots } r_{j^{\prime }}\). Let α = δ(i,j)s and β = δ(i,j). By assumption, there exists an {r1,…,rj,s}-only schedule γ such that v(Dδ(i,j)sγ) = v(Dδ(i,j)). To obtain a contradiction, suppose that \(\mathsf {v}(D\delta {(i^{\prime },j^{\prime })}) = \mathsf {v}(D\delta {(i,j)})\). Configurations \(D\delta {(i^{\prime },j^{\prime })}\) and Dδ(i,j) are indistinguishable to r1,…,rj, and s, since the signaller and these readers take no steps in \(r_{j+1} {\cdots } r_{j^{\prime }}\). Then \( \mathsf {v}(D\delta {(i^{\prime },j^{\prime })}s\gamma ) = \mathsf {v} (D\delta {(i,j)}s\gamma ) = \mathsf {v}(D\delta {(i,j)}) = \mathsf {v}(D\delta {(i^{\prime },j^{\prime })})\). Since rj+ 1 does not appear in sγ, configurations \(D\delta {(i^{\prime },j^{\prime })}s\gamma \) and \(D\delta {(i^{\prime },j^{\prime })}\) are indistinguishable to rj+ 1. Note that rj+ 1 must return false if it takes a step in configuration \(D\delta {(i^{\prime },j^{\prime })}\), because s has not taken any steps since rj+ 1 last took a step. However, rj+ 1 must return true if it takes a step in configuration \(D\delta {(i^{\prime },j^{\prime })}s\gamma \), because s has taken a step since rj+ 1 last took a step. This is impossible, because \(D\delta {(i^{\prime },j^{\prime })}s\gamma \) and \(D\delta {(i^{\prime },j^{\prime })}\) are indistinguishable to rj+ 1. □
Using this lemma, we obtain Theorem 1.
Theorem 1
In any algorithm for the signal detection problem, the blackboard has domain size at least n(n + 1)/2.
Proof
Consider any algorithm for signal detection in which the blackboard stores a finite number of different values. By Lemma 3, there is a reachable configuration D such that, for any schedules α and β, there exists an (M(α) ∪ M(β) ∪{s})-only schedule γ such that v(Dαγ) = v(Dβ). By Lemma 4, for all different choices of 0 ≤ i < j ≤ n, the value of the blackboard in configuration Dδ(i,j) is different. There are n(n + 1)/2 ∈Ω(n2) such choices. □
7 Two Readers
In this section, we examine the special case when there are exactly two readers. The simple signal detection algorithm presented in Section 1.2 with one bit for each reader has a blackboard domain of size 22 = 4. First, we prove that this is optimal.
To prove our conjecture that 2n blackboard values are necessary for n readers, one approach would be to show the existence of a configuration from which P-only executions lead to different blackboard configurations for different subsets P of the readers. When n = 2, we show that such a configuration does not always exist. In particular, in Section 7.2, we present an algorithm for two readers, r1 and r2, with the property that, from every reachable configuration C, any reader-only execution leads to at most three different blackboard values. Thus, in order to show that four different blackboard values can be reached from some reachable configuration C, the signaller must also take steps, as is the case in our lower bound in Section 7.1. We conjecture that there are similar counterexample algorithms for n > 2.
7.1 A Tight Lower Bound
We begin with a straightforward observation about when two configurations have the same blackboard value.
Observation 7
For any configuration C and any schedule α such that v(C) = v(Cα), if β is a schedule consisting of processes that don’t take steps in α, then v(Cβ) = v(Cαβ).
The proof follows from the fact that configurations C and Cα are indistinguishable to the processes that take steps in β.
In some situations, it is also easy to prove that two configurations have different blackboard values.
Lemma 5
If C is a reachable configuration, ρ is a schedule that contains reader r but not the signaller s, σ is a schedule that contains s but not r, and γ is a schedule that contains neither s nor r, then v(Cρσ)≠v(Cργ).
Proof
If reader r takes a step in configuration Cρσ, it must return true, because r’s previous step occurred during ρ and s took a step during σ. However, if r takes a step in configuration Cργ, it must return false, because s takes no steps during ργ.
Since r takes no steps in σ or γ, the state of r in configurations Cρσ and Cργ must be the same. Now suppose that v(Cρσ) = v(Cργ). Then configurations Cρσ and Cργ are indistinguishable to r, so it must return the same value if it takes a step in Cρσ and Cργ. This is a contradiction. □
Corollary 1
If C is a reachable configuration, ρ is a schedule that contains reader r but not the signaller s, and σ is a schedule that contains s but not r, then v(Cρσ)≠v(Cρ).
These results will be used repeatedly to obtain a tight lower bound when there are two readers.
Theorem 8
Any algorithm for signal detection among n = 2 readers requires blackboard domain size at least 4.
Proof
Consider any algorithm, let C0 be its initial configuration, and let D = C0r1r2. Since the blackboard domain size is finite, there are two integers k,ℓ ≥ 1, such that v(Dsk) = v(Dsk+ℓ). We first show that v(Dskr1)≠v(Dsk)≠v(Dskr2). To obtain a contradiction, suppose that v(Dsk) = v(Dskri) for some i ∈{1,2}. Then v(Dsk+ℓ) = v(Dskrisℓ) by Observation 7 with C = Dsk, α = ri and β = sℓ. Hence v(Dskri) = v(Dsk) = v(Dsk+ℓ) = v(Dskrisℓ). But v(Dskrisℓ)≠v(Dskri) by Corollary 1 with C = Dsk, r = ri, ρ = ri, and σ = sℓ. This is a contradiction. Therefore v(Dsk)≠v(Dskr1),v(Dskr2).
Applying Corollary 1 with C = C0, r = r2, ρ = r1r2, and σ = skr1 gives v(Dskr1) = v(C0r1r2skr1)≠v(C0r1r2) = v(D). Similarly, v(Dskr2)≠v(D). Applying Corollary 1 with C = C0, r = r1, ρ = r1r2, and σ = sk, gives v(Dsk) = v(C0r1r2sk)≠v(C0r1r2) = v(D). If v(Dskr1)≠v(Dskr2), then v(D), v(Dsk), v(Dskr1), and v(Dskr2) are all distinct, so suppose that v(Dskr1) = v(Dskr2).
Applying Corollary 1 with C = C0, r = r2, ρ = r1r2, and σ = skr1s gives v(Dskr1s) = v(C0r1r2skr1s)≠v(C0r1r2) = v(D). Applying Corollary 1 with C = Dsk, r = r1, ρ = r1, and σ = s gives v(Dskr1s)≠v(Dskr1). If v(Dskr1s)≠v(Dsk), then v(D), v(Dsk), v(Dskr1), and v(Dskr1s) are all distinct, so suppose that v(Dskr1s) = v(Dsk).
By Observation 7 with C = Dsk, α = r1s and β = r2, it follows that v(Dskr1sr2) = v(Dskr2), so v(Dskr1sr2) = v(Dskr1). Applying Corollary 1 with C = Dsk, r = r1, ρ = r1, and σ = sr2 gives v(Dskr1sr2)≠v(Dskr1). This is a contradiction. Therefore, either v(Dskr1)≠v(Dskr2) or v(Dskr1s)≠v(Dsk) and, hence, the domain size is at least 4. □
7.2 An Algorithm for Two Readers Based on a Bounded Sequential Timestamp System
A bounded sequential timestamp system for a set of processes consists of a finite set of labels, L, and a dominance relation ≺ between every two different labels, i.e. if ℓ1 and ℓ2 are two different labels then exactly one of ℓ1 ≺ ℓ2 and ℓ2 ≺ ℓ1 is true. At every configuration, each process has a different label. There is one atomic operation, getTimestamp(), which may change the label of the process that called it and which ensures that its label dominates the labels of all other processes. A solution to the signal detection problem can be obtained from a bounded sequential timestamp system by using the blackboard to store the timestamps of the signaller and each reader. When either a reader or the signaller takes a step, it performs getTimestamp() and updates its timestamp stored on the blackboard, if it has changed. A reader returns true if and only if its timestamp was smaller (with respect to ≺) than the timestamp of the signaller before it was updated. The domain size of the blackboard is |L|n+ 1 in this algorithm, where n is the number of readers. Note that this algorithm provides a lot more information than is required by the signal detection problem. Specifically, each reader can also determine which of the other readers have taken steps since it last took a step.
Israeli and Li [5] gave a construction of a bounded sequential timestamp system for n + 1 processes with a label set of size 3n and proved that, for any 𝜖 > 0, there exists a bounded sequential timestamp system for n + 1 processes whose label set has size (2 + 𝜖)n+ 1, for n sufficiently large. They also proved a lower bound of 2n+ 1 − 1 for the size of the label set of any bounded sequential timestamp system for n + 1 processes.
The algorithm below is based on the bounded timestamp system of Israeli and Li for three processes with 32 = 9 labels, but it stores only two labels on the blackboard: the signaller’s label and the larger (with respect to ≺) of the two readers’ labels. This results in a blackboard with domain size 81, which is much larger than the number of labels used in the optimal algorithm. However, this algorithm has the property that, starting from any reachable configuration, at most three different blackboard configurations can be reached by executions in which only readers take steps.
Let B = {0,1,2}. The set of labels is B2 = B × B. We define the dominance relation ≺ as follows: For (a1,a0),(b1,b0) ∈ B2, (a1,a0) ≺ (b1,b0) if and only if
Note that, for any two distinct labels a,b ∈ B2, either a ≺ b or b ≺ a. Israeli and Li view the set of all labels with the same first component as being the labels of a separate copy of a bounded sequential timestamp for 2 processes (which uses labels in B).
1.
b1 ≡ a1 + 1 (mod 3) or
2.
b1 = a1 and b0 ≡ a0 + 1 (mod 3).
The algorithm maintains the following label invariants: In each reachable configuration, each process p ∈{s,r0,r1} has a different label \(\ell (p)=\left (\ell _{1}(p),\ell _{0}(p)\right )\in B^{2}\). In addition, each reader has a label from a different copy (i.e. ℓ1(r0)≠ℓ1(r1)) and the signaller has a label from one of these copies (i.e. ℓ1(s) ∈{ℓ1(r0),ℓ1(r1)}). In the initial configuration,
so the label invariants are satisfied.
$$ \ell(r_{0})=(0,0),\ \ell(r_{1})=(1,0),\ \text{and}\ \ell(s)=(1,1), $$
In each reachable configuration, the readers have different labels, so one of the reader’s labels dominates the other reader’s label. We call the reader with this label the dominating reader.
In other words, the signaller’s label as well as the dominating reader’s label are stored on the blackboard. Thus, initially, the blackboard contains ((1,1),(1,0)).
$$ \begin{array}{@{}rcl@{}} &&\text{The blackboard stores the pair}~ \left( \ell(s),\ell(r_{d})\right),\\ && \text{where} d\in\{0,1\} \text{and} \ell(r_{1-d})\prec\ell(r_{d}). \end{array} $$
(B)
When a process takes a step, it applies the rules described below, which might change its label. We prove that the label invariants remain satisfied. If its label is changed, the process updates the blackboard so that (B) remains true. We will show that, in addition,
Therefore, a reader can easily provide the proper response when it takes a step: If a reader’s label dominates ℓ(s) at the beginning of its step, then the reader returns false. Otherwise it returns true.
$$ \begin{array}{@{}rcl@{}} && \text{immediately after each step by } s, \text{ its label } \ell(s) \text{ dominates both } \ell(r_{0}) \text{ and } \ell(r_{1}) \text{ and}\\ && \text{immediately after each step by a reader } r_{i}, \text{ its label } \ell(r_{i}) \text{ dominates } \ell(s). \end{array} $$
(S)
Consider any configuration that satisfies (B) and the label invariants. Let d ∈{0,1} be such that ℓ(r1−d) ≺ ℓ(rd). Since ℓ1(r1−d)≠ℓ1(rd), it follows that ℓ1(rd) ≡ ℓ1(r1−d) + 1 (mod 3).
The Signaller’s Step.
When the signaller s takes a step, it compares its label with ℓ(rd), which is stored on the blackboard. If ℓ(rd) ≺ ℓ(s), then s retains its old label and does not update the blackboard, so (B) and the label invariants remain satisfied. In this case, ℓ1(s)≠ℓ1(r1−d), so, by the label invariants, ℓ1(s) = ℓ1(rd) and, hence, ℓ(r1−d) ≺ ℓ(s). Thus, (S) is true.
Now consider the case when ℓ(s) ≺ ℓ(rd). The new label of s is
$$ \begin{array}{@{}rcl@{}} \ell^{\prime}(s)=(\ell_1(r_d),(\ell_0(r_d)+1)\text{mod} 3). \end{array} $$
By definition, \(\ell (r_{d})\prec \ell ^{\prime }(s)\). Since \(\ell _{1}^{\prime }(s) = \ell _{1}(r_{d}) \equiv \ell _{1}(r_{1-d}) +1 ~(\text {mod}~ 3)\), we have \(\ell (r_{1-d}) \prec \ell ^{\prime }(s)\). Thus (S) is satisfied and the labels of all three processes are different. By definition, \(\ell ^{\prime }_{1}(s) = \ell _{1}(r_{d}) \in \{\ell _{1}(r_{0}), \ell _{1}(r_{1})\}\). Since the labels of r0 and r1 do not change, ℓ1(r0)≠ℓ1(r1). Hence, the label invariants remain satisfied. After determining its new label \(\ell ^{\prime }(s)\), the signaller updates the first component of the pair stored on the blackboard with \(\ell ^{\prime }(s)\), so (B) remains satisfied.
The Reader’s Step.
When reader ri, i ∈{0,1}, takes a step, it compares its label with ℓ(s), which is stored on the blackboard. If ℓ(s) ≺ ℓ(ri), then ri does not change its label and (S) is true. In this case, none of the label invariants are affected, the reader does not change the blackboard, and (B) remains satisfied.
So suppose that ℓ(ri) ≺ ℓ(s). Then ri’s new label is
In both cases, \(\ell (s)\prec \ell ^{\prime }(r_{i})\), so (S) is satisfied and \(\ell ^{\prime }(r_{i}) \neq \ell (s)\). If ℓ1(ri) = ℓ1(s), then, by construction, \(\ell _{1}^{\prime }(r_{i})=\ell _{1}(s)=\ell _{1}(r_{i})\). By the label invariants, ℓ1(ri)≠ℓ1(r1−i), so \(\ell _{1}^{\prime }(r_{i}) \neq \ell _{1}(r_{1-i})\). If ℓ1(ri)≠ℓ1(s), then, since ℓ1(s) ∈{ℓ1(r0),ℓ1(r1)}, we have ℓ1(s) = ℓ1(r1−i). By construction, \(\ell _{1}^{\prime }(r_{i})\neq \ell _{1}(s)\), so \(\ell _{1}^{\prime }(r_{i}) \neq \ell _{1}(r_{1-i})\). In both cases, \(\ell ^{\prime }(r_{i}) \neq \ell (r_{1-i})\). Since ℓ(r1−i)≠ℓ(s), the labels of all three processes are different. Hence, the label invariants remain satisfied.
$$ \ell^{\prime}(r_{i})= \begin{cases} \left( \ell_{1}(s),(\ell_{0}(s)+1)\text{mod} 3\right) & \text{if } \ell_{1}(r_{i})=\ell_{1}(s)\\ \left( (\ell_{1}(s)+1)\text{mod} 3,0\right) & \text{otherwise.} \end{cases} $$
If ℓ1(ri) = ℓ1(s) and d = 1 − i (i.e., the second label on the blackboard is not equal to ℓ(ri)), then ri does not change the blackboard. In this case, by (B), ℓ(ri) ≺ ℓ(r1−i) and, by the label invariants, ℓ1(ri)≠ℓ1(r1−i). Therefore, it follows that ℓ1(r1−i) ≡ (ℓ1(ri) + 1) (mod 3). By construction, \(\ell ^{\prime }_{1}(r_{i}) = \ell _{1}(s)\), so \(\ell _{1}(r_{1-i}) \equiv (\ell ^{\prime }_{1}(r_{i}) +1) ~(\text {mod}~ 3)\) and, hence, \(\ell ^{\prime }(r_{i}) \prec \ell (r_{1-i})\). Thus (B) remains satisfied.
If ℓ1(ri) = ℓ1(s) and d = i, then ri changes the second component of the blackboard to \(\ell ^{\prime }(r_{i}) = \left (\ell _{1}(s),(\ell _{0}(s)+1)\text {mod} 3\right )\). Since ℓ(r1−i) ≺ ℓ(ri) and, by the label invariants, ℓ1(r1−i)≠ℓ1(ri), it follows that \(\ell ^{\prime }_{1}(r_{i}) \equiv \ell _{1}(r_{1-i}) +1 ~(\text {mod}~ 3)\). Hence \(\ell (r_{1-i}) \prec \ell ^{\prime }(r_{i})\) and (B) remains satisfied.
The last case is when ℓ1(ri)≠ℓ1(s). Then ri changes the second component of the blackboard to \(\ell ^{\prime }(r_{i}) = \left ((\ell _{1}(s)+1)\text {mod} 3,0\right )\). By the label invariants, ℓ1(s) = ℓ1(r1−i), so \(\ell ^{\prime }_{1}(r_{i}) = (\ell _{1}(r_{1-i})+1) \text {mod} 3\). Hence \(\ell (r_{1-i}) \prec \ell ^{\prime }(r_{i})\) and (B) remains satisfied.
Lemma 6
For any reachable configuration C,
$$ \begin{array}{@{}rcl@{}} \left|\left\{\mathsf{v}(C\alpha): \alpha\in\{r_0,r_1\}^\ast \right\}\right|\leq 3. \end{array} $$
Proof
Without loss of generality, we may assume that either C is the initial configuration or the last step in the execution leading to C was taken by the signaller. Let \(\ell ^{\ast }(p)=\left (\ell _{1}^{\ast }(p),\ell _{0}^{\ast }(p)\right )\) denote the label of process p ∈{s,r0,r1} in configuration C. By (S) and the definition of the initial configuration, the label of the signaller, ℓ∗(s), dominates the labels, ℓ∗(r0) and ℓ∗(r1), of the readers. By the label invariants, there is an index d ∈{0,1} such that \(\ell _{1}^{\ast }(s)=\ell _{1}^{\ast }(r_{d})\neq \ell _{1}^{\ast }(r_{1-d})\). Since ℓ∗(r1−d) is dominated by ℓ∗(s), it is also dominated by ℓ∗(rd). Thus, by (B), \(\mathsf {v}(C)=\left (\ell ^{\ast }(s),\ell ^{\ast }(r_{d})\right )\).
The signaller takes no steps in α, so its label remains unchanged. If rd takes at least one step in α, its label changes to \(\ell ^{\prime }(r_{d}) =\left (\ell _{1}^{\ast }(s),(\ell _{0}^{\ast }(s)+1)\text {mod} 3\right )\) and, if r1−d takes at least one step in α, its label changes to \( \ell ^{\prime }(r_{1-d}) ={\left ((\ell _{1}^{\ast }(s)+1)\text {mod} 3,0\right )}\). By (S), after a reader has taken a step, its new label dominates ℓ∗(s), so its label does not change when it takes additional steps in α.
When a reader takes a step, either it does not change the blackboard, or it replaces the second component of the blackboard with its new label. Thus, for all \(\alpha \in \{r_{0},r_{1}\}^{\ast }\),
$$ \begin{array}{@{}rcl@{}} \mathsf{v}(C\alpha)=(\ell^\ast(s), \ell), \ \text{where}\ \ell\in\left\{\ell^\ast(r_d),\ell^{\prime}(r_d),\ell^{\prime}(r_{1-d})\right\}. \end{array} $$
Hence, \(\left |\left \{\mathsf {v}(C\alpha ): \alpha \in \{r_{0},r_{1}\}^{\ast }\right \}\right |\leq 3\). □
8 Discussion
This paper introduces the signal detection problem, gives some simple algorithms for solving it, proves that domain size at least n(n + 1)/2 is necessary, and proves that domain size 2n is necessary and sufficient for three restricted versions of the problem: when the processes are write oblivious, when the readers are response oblivious, or when the signaller writes a fixed sequence of values to the blackboard. We conjecture that domain size must be at least 2n for the unrestricted version of the problem. It would also be interesting to prove this bound for two other restricted versions of the problem: when only the signaller is write oblivious or only the readers are write oblivious.
We also consider another restricted version of the problem, where each reader takes no more than b ≥ 2 steps. We give an algorithm with domain size (b − 1)n + 1 and prove this is optimal when b = 2. It remains open whether it is optimal when b > 2. If the signaller takes no more that B steps, then one of our simple algorithms uses a domain of size B + 1. It is unclear whether it is possible to have an algorithm for this restricted version that has a smaller domain.
Acknowledgements
Support is gratefully acknowledged from the Natural Science and Engineering Research Council of Canada (NSERC) under Discovery Grant RGPIN-2015-05080, Discovery Grant RGPIN-2019-04852, the Canada Research Chairs program, and a Postgraduate Scholarship, and from a University of Toronto Faculty of Arts and Science Postdoctoral Fellowship.
A preliminary version of this paper appeared in [3].
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.