To prove our conjecture that 2
n 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.
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.
These results will be used repeatedly to obtain a tight lower bound when there are two readers.
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 3
n 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 2
n+ 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
2.
b1 = a1 and b0 ≡ a0 + 1 (mod 3).
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).
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,
$$ \ell(r_{0})=(0,0),\ \ell(r_{1})=(1,0),\ \text{and}\ \ell(s)=(1,1), $$
so the label invariants are satisfied.
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.
$$ \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)
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)).
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,
$$ \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)
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.
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
$$ \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} $$
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.
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.