Monitors Pipeline Sample Clauses

Monitors Pipeline. The basic monitor protocol runs a sequence of monitors and tests the number of faults’ threshold every 4 rounds (Line 5). This allows the adversary to expose more faults in the following round, and be able to further expand the tree before the threshold is noticed the next time the processes execute Line 5. To circumvent this we will run a pipeline of 3 additional sequences of monitors on top of the basic one appearing above. Doing this we obtain that in every round r one of the 4 monitor sequences will be testing the threshold on the number of faults − ≤ ≤ − D ≡ − ≡ Monitor sequence i, for 1 i 4 begins in round i and invokes protocols every 4 rounds, in every round r, 1 < r = i + 4k < t 1, it invokes protocol t−i−4k. Moni- tor sequence 1 is the basic monitor sequence defined in the previous subsection. Each monitor sequence independently runs the basic monitor protocol ( Figure 1) every 4 rounds. In the monitor protocol, the test r¯ = j, which stands for r¯ r (mod 4) in the basic monitor sequence, is replaced with r¯i = j, which stands for r¯i r + 1 i (mod 4) = j (naturally only for r + 1 i > 0). Each of the four monitor sequences decides and halts separately, as in the previous section above. D ⊥ Notice that protocol t is invoked only by the basic se- quence ( Sequence 1). For each of the three other monitor sequences, the decision rule is: decide bad, if any invoked protocol (in this sequence) outputs bad, and otherwise. Observe that Lemma 3 and 4 hold for each individual se- quence. We now state the global decision and global halting rules: Definition 2 (Global Halting). If any monitor se- quence halts with bad, or all 4 monitor sequences halt, the process halts. D