Lemma 3.3 — after a lock-release phase at or after GST, correct processors lock at most one value
ProvedDLSConsensus.BasicRound.lemma_3_3Consider any run of Algorithm 1 in the basic round model whose delivery pattern is allowed for the set of correct processors and the round (every message between processors of sent at a round is delivered). Let with , so that lock-release phase (round ) occurs at or after GST. Then, immediately after round , the set
contains at most one value.
This is the step of the termination proof that guarantees that, after GST, the owner of the next trying phase finds a value acceptable to all correct processors.
Formalization Note "Immediately after" is the state after the computation subround of round . A processor's lock-release message to itself is subject to the same delivery rule as any other message, so it is delivered when the processor is in and the round is at or after GST.
import Mathlib import Definitions.Def_DLSConsensus_BasicRound_Model
namespace DLSConsensus.BasicRound
/-- Lemma 3.3 (p. 297): immediately after any lock-release phase `k` (round `4k`) that occurs at
or after GST, the set of values locked by processors in `C` has at most one element. -/
theorem lemma_3_3 {N : ℕ} {V : Type*} (t : ℕ) (pick : ℕ → Set V → V) (init : Fin N → V)
(C : Finset (Fin N)) (GST : ℕ) (deliv : ℕ → Fin N → Fin N → Prop)
(hdeliv : DelivOK C GST deliv) (k : ℕ) (hk : 1 ≤ k) (hGST : GST ≤ 4 * k) :
{v : V | ∃ p ∈ C, (exec t pick init deliv (4 * k) p).lock v ≠ none}.Subsingleton := by sorry
end DLSConsensus.BasicRound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.