Lemma 3.1 — no two distinct values acquire locks with the same associated phase
ProvedDLSConsensus.BasicRound.lemma_3_1consensusdistributed-computingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider any run of Algorithm 1 in the basic round model, with arbitrary initial values, delivery pattern and choice function. Say that a processor locks at phase () if it receives the message in round .
It is impossible for two distinct values to acquire locks with the same associated phase: for all processors , all and all values ,
Phase numbers thus identify the locked value uniquely; this is used in the proof of Lemma 3.2 to exclude a competing lock with the same phase.
Formalization Note No hypothesis on , on the delivery pattern or on the choice function is needed, and none is assumed.
Preamble
import Mathlib import Definitions.Def_DLSConsensus_BasicRound_Model
Formal statement
namespace DLSConsensus.BasicRound
/-- Lemma 3.1 (p. 296): it is impossible for two distinct values to acquire locks with the same
associated phase. If processor `p` locks `v` at phase `k` and processor `q` locks `w` at the
same phase `k`, then `v = w`. -/
theorem lemma_3_1 {N : ℕ} {V : Type*} (t : ℕ) (pick : ℕ → Set V → V) (init : Fin N → V)
(deliv : ℕ → Fin N → Fin N → Prop) (k : ℕ) (p q : Fin N) (v w : V)
(hp : LocksAt t pick init deliv p k v) (hq : LocksAt t pick init deliv q k w) :
v = w := by sorry
end DLSConsensus.BasicRound
Source
Dwork, Lynch, Stockmeyer, Consensus in the presence of partial synchrony, J. ACM 35 (1988), p. 296, Lemma 3.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.