Theorem 3.1 — for N ≥ 2t + 1, Algorithm 1 achieves consistency, strong unanimity and termination
ProvedDLSConsensus.BasicRound.theorem_3_1Assume the basic round model with fail-stop or omission faults, and assume . Then Algorithm 1 achieves consistency, strong unanimity and termination for an arbitrary value domain.
Precisely: for every value type and initial values , every set of processors with (the correct processors), every round , every delivery pattern in which all messages sent between processors of at rounds are delivered (any other message may be lost), and every admissible choice of proposals, the run of Algorithm 1 satisfies
- consistency: any two decisions by processors in are equal;
- strong unanimity: if all initial values are , every decision by a processor in is ;
- termination: every processor in decides.
This is the upper-bound half of the paper's result for omission and fail-stop faults with partially synchronous communication: suffices, which the paper later shows to be optimal.
Formalization Note Faulty processors are processors outside that run Algorithm 1 but whose messages (sent and received) may be lost at any round; this omission model contains fail-stop. The arbitrary choice among candidates is a universally quantified admissible choice function. Runs of the basic model are infinite, so the paper's "if is infinite" in the termination condition is automatic.
import Mathlib import Definitions.Def_DLSConsensus_BasicRound_Model
namespace DLSConsensus.BasicRound
/-- Theorem 3.1 (p. 297): in the basic round model with omission (in particular fail-stop)
faults, if `N ≥ 2t + 1`, Algorithm 1 achieves consistency, strong unanimity and termination
for an arbitrary value domain `V`: for every set `C` of at least `N - t` correct processors,
every round `GST`, every message-loss pattern allowed by the model, every initial values and
every admissible choice of proposals. -/
theorem theorem_3_1 {N t : ℕ} (hN : 2 * t + 1 ≤ N) {V : Type*} (init : Fin N → V)
(C : Finset (Fin N)) (hC : N - t ≤ C.card) (GST : ℕ) (deliv : ℕ → Fin N → Fin N → Prop)
(hdeliv : DelivOK C GST deliv) (pick : ℕ → Set V → V) (hpick : PickAdmissible pick) :
Consistency t pick init deliv C ∧ StrongUnanimity t pick init deliv C ∧
Termination t pick init deliv C := by sorry
end DLSConsensus.BasicRound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.