Common use of Proof of the algorithm Clause in Contracts

Proof of the algorithm. The proof considers the system model BAMPn,t[t < n/(m + 1), LRC], the algorithmic safety and liveness constraints on W , namely, W (k + 1) > n and n − t ≥ (W − 1)k + 1, and the non-triviality condition (k < m) ∧ (k ≤ t). Preliminary remark 1 The proof considers the semantic of the messages DECIDE() described pre- viously. This is equivalent to consider that, after it has decided, a correct process continues executing while skipping line 8. Notation Given a round r, let EST [r] be the set of estimate values of the correct processes when they start round r, and AUX [r] be the set including the values of the auxi variables of the correct processes at the end of the first phase of round r (i.e., just after line 5). let us notice that AUX [r] can contain ⊥. Preliminary remark 2 The proof of the MV-Obligation property requires that at most m different val- ues are MV-broadcast. Hence, this requirement extends to the invocations SMV broadcastPHASE[r, x](), where x ∈ {1, 2}. By assumption, this requirement is initially satisfied, namely, |EST [1]| ≤ m. We will see in the proof that (i) AUX [r] contains at most k values proposed by correct processes plus pos- sibly ⊥, (ii) viewi[r, 2] is a subset of AUX [r], and (iii) mv validi[1, 1] contains only values proposed by correct processes. From the previous observations we conclude that at most m different values are SMV-broadcast at line 4 and line 6 of Algorithm 4.