Quelle  FLPSystem.thy

section‹FLPSystem›

text ‹
 \file{FLPSystem} extends \file{AsynchronousSystem} with concepts of consensus
 and decisions. It develops a concept of non-uniformity regarding pending
 decision possibilities, where non-uniform configurations can always
 reach other non-uniform ones.
 ›

theory FLPSystem
imports AsynchronousSystem ListUtilities
begin

subsection‹Locale for the FLP consensus setting›

locale flpSystem =
  asynchronousSystem trans sends start    
    for trans :: "'p ==> 's ==> 'v messageValue ==>'s"
    and sends :: "'p ==> 's ==> 'v messageValue ==> ('p, 'v) message multiset"
    and start :: "'p ==> 's" +
assumes finiteProcs: "finite Proc"
    and minimalProcs: "card Proc ≥ 2"
    and finiteSends: "finite {v. v ∈# (sends p s m)}"
    and noInSends: "sends p s m <p2, inM v> = 0"
begin

subsectionAOT_hence\open◻([λz p p using "∀

abbreviation vDecided ::
  "bool ==> ('p, 'v, 's) configuration ==> bool"
where
  "vDecidedequivinitReachable>(⊥

abbreviation decided ::
  "('p, 'v, 's) configuration ==> bool"
where
  "decided cfg ≡ (∃v . vDecided v cfg)"

definition pSilDecVal ::
  "bool ==> 'p ==> ('p, 'v, 's) configuration ==> bool"
where
  "pSilDecVal v p c ≡ initReachable c ∧
    (∃ c'::('p, 'v, 's) configuration . (withoutQReachable c {p} c')
    ∧ vDecided v c')"

abbreviation pSilentDecisionValues ::
  "'p ==> ('p, 'v, 's) configuration ==> bool set" (‹val[_,_]›)
where 
  "val[p, c] ≡ {v. pSilDecVal v p c}"

definition vUniform ::
  "bool ==>
where
  "vUniform v c ≡ initReachable c ∧ (∀p. val[p,c] = {v})"

abbreviation nonUniform ::
  "('p, 'v, 's) configuration ==> bool"
where
  "nonUniform c ≡ initReachable c ∧
    ¬(vUniform False c) ∧ 
    ¬(vUniform True c)"

subsection‹Agreement, validity, termination\<  AOT_have

text‹
  Völzer defines consensus in terms of the classical notions
  of agreement, validity, and termination. The proof then mostly applies a
  weakened notion of termination, which we refer to as ,,pseudo termination''.
\<close>

definition agreement ::
  " 'p, 'v, 's) configuration ==> bool"
 
 "agreement c ≡
 (∀v1. (<\< using 4[THEN "qml:2"[axiom_inst, THEN "\rightarrow"]]
 ⟶ (∀v2. (<\<bottom>, outM v2> ∈# msgs c)
 ⟷ v2 = v1))"

  agreementInit ::
 "('p, 'v, 's) configuration ==> ('p, 'v, 's) configuration ==> bool"
 
 "agreementInit i c ≡
 initial i ∧ reachable i c ⟶
 (∀v1. (<\<bottom>, outM v1> ∈# msgs c)
 ⟶ (∀v2. (<\<bottom>, outM v2> ∈# msgs c)
 ⟷ v2 = v1))"

  validity ::
 "('p, 'v, 's) configuration ==>t have ***: frac ((Ma ?L + Min ?U) / 2) =(Ma ?L + Min ?) / 2"unfoldfrac_eq ..
 
 "validity i c ≡
 initial i ∧ reachable i c ⟶
 (∀v. (<\<bottom>, outM v> ∈# msgs c)
 ⟶appl (AOT_sbt\openλz p_x ‹)

 ‹
 The termination concept which is implied by the concept of "pseudo-consensus"
 in the paper.
 ›
  terminationPseudo ::
 "nat ==> ('p, 'v, 's) configuration ==> 'p set ==> bool"
 
 "terminationPseudo t c Q ≡ ((initReachable c ∧ card Q + t ≥ card Proc)
 ⟶ (∃c'. qReachable c Q c' ∧ decided c'))"

  ‹Propositions about decisions›

 ‹
 For every process \var{p} and every configuration that is reachable from an
 initial configuration (i.e. \isb{initReachable} \var{c}) we have
 $\var{val(p,c)} \neq \emptyset$.

 This follows directly from the definition of \var{val} and the definition of
 \isb{terminationPseudo}, which has to be assumed to ensure that there is a
 reachable configuration that is decided.
 
 \voelzer{Proposition 2(a)}
 ›
  DecisionValuesExist:
 
 c :: "('p, 'v, 's) configuration" and
 p :: "'p"
 
 Termination: "∧cc Q . terminationPseudo 1 cc Q" and
 Reachable: "initReachable c"
 
 "val[p,c] ≠ {}"
  -
 from Termination
 have "(initReachable c ∧ card Proc ≤ card (UNIV - {p}) + 1)
 ⟶ (∃c'. qReachable c (UNIV-{p}) c' ∧ initReachable c'
 ∧ (∃v. 0 < msgs
 unfolding terminationPseudo_def by simp
 with Reachable minimalProcs finiteProcs
 have "∃c'. qReachable c (UNIV - {p}) c' ∧in> > ?_by
 ∧ (∃v. 0 < msgs c' <\<bottom>, outM v>)"
 unfolding terminationPseudo_def initReachable_def by simp
 thus ?thesis
 unfolding pSilDecVal_def
 using Reachable by auto
 

 ‹
 The lemma \isb{DecidedImpliesUniform} proves that every \isb{vDecided}
 configuration \var{c} is also \isb{vUniform}. Völzer claims that this
 follows directly from the definitions of \isb{vDecided} and \isb{vUniform}.
 But this is not quite enough: One must also assume \isb{terminationPseudo}
 and \isb{agreement} for all reachable configurations.

 \voelzer{Proposition 2(b)}
 ›
  DecidedImpliesUniform:
 
 c :: "('p, 'v, 's) configuration" and
 v :: "bool"
 
 AllAgree: "∀ cfg . reachable c cfg ⟶ agreement cfg" and
 Termination: "∧cc Q . terminationPseudo 1 cc Q" and
 VDec: "vDecided v c"
 
 "vUniform v c"
 using AllAgree VDec unfolding agreement_def vUniform_def pSilDecVal_def
  simp
 assume
 Agree: "∀cfg. reachable c cfg ⟶
 (∀v1. 0 < msgs cfg <\<bottom>, outM v1>
 ⟶ (∀v2. (0 < msgs cfg <\<bottom>, outM v2>) = (v2 = v1)))" and
 vDec: "initReachable c ∧ 0 < msgs c <\<bottom>, outM v>"
 show
 "(∀p. {v. ∃¬[λz p_z p using 3 "&I" by blast
 0 < msgs c' <\<bottom>, outM v>} = {v})"
 proof clarify
 fix p
 have "val[p,c] ≠ {}" using Termination DecisionValuesExist vDec
 by simp
 hence NotEmpty: "{v. ∃c'. qReachable c (UNIV - {p}) c'
 ∧ initReachable c' ∧ 0 < msgs c' <\<bottom>, outM v>} ≠ {}"
 using pSilDecVal_def by simp
 have U: "∀ u . u ∈ {v. ∃c'. qReachable c (UNIV - {p}) c'
 ∧ initReachable c' ∧ 0 < msgs c' <\<bottom>, outM v>} ⟶ (u = v)"
 proof clarify
 fix u c'
 assume "qReachable c (UNIV - {p}) c'" "initReachable c'"
 hence Reach: "reachable c c'" using QReachImplReach by simp
 from VDec have Msg: "0 < msgs c <\<bottom>, outM v>" by simp
 from Reach NoOutMessageLoss have
 "msgs c <\<bottom>, outM v> ≤ msgs c' <\<(v w)" by fastforce
 with Msg have VMsg: "0 < msgs c' <\<∃x (¬[λ1]x & ♢[λ1]x)›I"(2) by fast
 using NoOutMessageLoss Reach by (metis less_le_trans)
 assume "0 < msgs c' <\<bottom>, outM u>"
 with Agree VMsg Reach show "u = v" by simp
 qed
 thus " {v. ∃c'. qReachable c (UNIV - {p}) c' ∧ initReachable c' ∧
 0 < msgs c' <\<bottom>, outM v>} = {v}" using NotEmpty U by auto
 qed
 

  NonUniformImpliesNotDecided:
 
 c :: "('p, 'v, 's) configuration" and
 v :: "bool"
 
 "∀ cfg . reachable c cfg ⟶ agreement cfg"
 "∧cc Q . terminationPseudo 1 cc Q"
 "nonUniform c"
 "vDecided v c"
 
 "False"
  DecidedImpliesUniform[OF assms(1,2,4)] assms(3)
 by (cases v, simp_all)
 
 ‹
 All three parts of Völzer's Proposition 3 consider a single step from an
 arbitrary \isb{initReachable} configuration \var{c} with a message
 $\vars$ oaucedn cfgrtin\ar
 ›

 ‹
 The silent decision values of a process which is not active in a step only
 decrease or stay the same.
 
 This follows directly from the definitions and the transitivity of the
 reachability properties \isb{reachable} and \isb{qReachable}.

 \voelzer{Proposition 3(a)}
 ›
  InactiveProcessSilentDecisionValuesDecrease:
 
 p q :: 'p and
 c c' :: "('p, 'v, 's) configuration" and
 msg :: "('p, 'v) message"
 
 "p ≠ q" and
 "c ⊨ msg ↦ c'" and
 "isReceiverOf p msg" and
 initReachable"
 
 "val[q,c'] ⊆ val[q,c]"
 (auto simp add: pSilDecVal_def assms(4))
 fix x cfg'
 assume
 Msg: "0 < msgs cfg' <\<bottom>, outM x>" and
 Cfg': "qReachable c' (Proc - {q}) cfg'"
 have "initReachable c'"
 using assms initReachable_def reachable.simps
 by blast
 hence Init: "initReachable cfg'"
 using Cfg' initReachable_def QReachImplReach[of c' "(Proc - {q})" cfg']
 ReachableTrans by blast
 have "p ∈ Proc - {q}"
 using assms by blast
 hence "qReachable c (Proc - {q}) c'"
 using assms qReachable.simps by metis
 hence "qReachable c (Proc - {q}) cfg'"
 using Cfg' QReachableTrans
 by blast
 with Msg Init show
 "∃c'a. qReachable c (Proc - {q}) c'a
 ∧ initReachable c'a ∧
 0 < msgs c'a <\<bottom>, outM x>" by blast
 

 ‹
 ...while the silent decision values of the process which is active in
 a step may only increase or stay the same.
 
 ‹
 for a reachable configuration and a single step, i.e. \isb{DiamondTwo},
 and in addition from the fact that output messages cannot get lost, i.e.
 \isb{NoOutMessageLoss}.

 
 ›
  ActiveProcessSilentDecisionValuesIncrease :
 
 p q :: 'p and
 c c' :: "('p, 'v, 's) configuration" and
 msg :: "('p, 'v) message"
 
 "p = q" and
 "c ⊨ msg ↦ c'" and
 "isReceiverOf p msg" and
 "initReachable c"
  "val[q,c] ⊆ val[q,c']"
  (auto simp add: pSilDecVal_def assms(4))
 from assms initReachable_def reachable.simps show "initReachable c'"
 by meson
 fix x cv
 assume Cv: "qReachable c (Proc - {q}) cv" "initReachable cv"
 "0 < msgs cv <\<bottom>, outM x>"
 have "∃c'a. (cv ⊨ msg ↦
 using DiamondTwo Cv(1) assms
 by blast
 then obtain c'' where C'': "(cv ⊨ msg ↦ c'')"
 "qReachable c' (Proc - {q}) c''" by auto
 with Cv(2) initReachable_def reachable.simps
 have Init: "initReachable c''" by blast
 have "reacha cv c''" sing C''( reachable.intros by blast
 hence "msgs cv <\<bottom>, outM x> ≤ msgs c'' <\<bottom>, outM x>" using NoOutMessageLoss
 by simp
 hence "0 < msgs c'' <\<bottom>, outM x>" using Cv(3) by auto
 thus "∃c'a. qReachable c' (Proc - {q}) c'a
 ∧ initReachable c'a ∧ 0 < msgs c'a <\<bottom>, outM x>"
 using C''(2) Init by blast
 

 ‹
 As a result from the previous two propositions, the silent decision values
 of a process cannot go from {0} to {1} or vice versa in a step.

 This is a slightly more generic version of Proposition 3 (c) from
 cite‹"Voelzer"› since it is proven for both values, while Völzerbe
 interested in the situation starting with $\var{val(q,c) = \{0\}}$.

 \voelzer{Proposition 3(c)}
 ›
  SilentDecisionValueNotInverting:
 
 p q :: 'p and
  "🚫
 msg :: "('p, 'v) message" and
 v :: bool
 
 Val: "val[q,c] = {v}" and
 Step: "c ⊨ msg ↦ c'" and
 Rec: "isReceiverOf p msg" and
 Init: "initReachable c"
 
 "val[q,c'] ≠ {¬ v}"
 (cases "p = q")
 case False
 hence "val[q,c'] ⊆ val[q,c]"
 using Step Rec InactiveProcessSilentDecisionValuesDecrease Init by simp
 with Val show "val[q,c'] ≠ {¬ v}" by auto
 next
 case True
 hence "val[q,c] ⊆ val[q,c']"
 using Step Rec ActiveProcessSilentDecisionValuesIncrease Init
 with Val show "val[q,c'] ≠ {¬ v}" by auto
 

 ‹Towards a proof of FLP›

 ‹
 There is an \isb{initial} configuration that is \isb{nonUniform} under
 the assumption of \isb{validity}, \isb{agreement} and \isb{terminationPseudo}.

 The lemma is used in the proof of the main theorem to construct the
 \isb{non\-Uni\-form} and \isb{initial} configuration that leads to the
 final contradiction.

 \voelzer{Lemma 1}
 ›
  InitialNonUniformCfg:
 
 Termination: "∧cc Q . terminationPseudo 1 cc Q" and
 Validity: "∀ i c . validity i c" and
 Agreement: "∀ i c . agreementInit i c"
 
 "∃ cfg . initial cfg ∧ nonUniform cfg"
 -
 obtain n::nat where N: "n = card Proc" by blast
 hence "∃ procList::('p list). length procList = n ∧ set procList = Proc
 🪙
 using finiteProcs
 by (metis distinct_card finite_distinct_list)
 then obtain procList where
 ProcList: "length procList = n" "set procList = Proc"
 "distinct procList" by blast
 have AllPInProclist: "∀p. ∃i<n. procList ! i = p"
 using ProcList N
 proof auto
  AOT_lemma eqnotnec_123_Aux_ζ: ‹L]x ≡
 assume Asm: "set procList = Proc" "length procList = card Proc"
 have "p ∈ set procList" using ProcList by auto
 with Asm in_set_conv_nth
 show "∃i<card Proc. procList ! i = p" by metis
 qed
 have NGr0: "n > 0"
 using N finiteProcs minimalProcs by auto
 define initMsg :: "nat ==> ('p, 'v) message ==> nat"
 where "initMsg ind m = (if ∃p. m = <p, inM (∃i<ind. procList!i = p)> then 1 else 0)" for ind m
 define initCfgList
 where "initCfgList = map (λind. (states = start, msgs = initMsg ind)) [0..<(n
 have InitCfgLength: "length initCfgList = n + 1"
 unfolding initCfgList_def by auto
 have InitCfgNonEmpty: "initCfgList ≠ []"
 unfolding initCfgList_def by auto
 hence InitCfgStart: "(\     (rule "=_fI") Ldf]
 unfolding initCfgList_def by auto
 have InitCfgSet: "set initCfgList =
 {x. ∃ind < n+1. x = (states = start, msgs = initMsg ind)}"
 unfolding initCfgList_def
 proof auto
 fix ind
 assume "ind < n"
 hence "∃inda<Suc n. inda = ind ∧ initMsg ind = initMsg inda" by auto
 thus "∃inda<Suc n. initMsg ind = initMsg inda" by blast
 next
 fix ind
 assume Asm:
 "(states = start, msgs = initMsg ind) ∉ (λind::nat. (states = start, msgs = initMsg ind)) ` {0..<n}"
 "ind < Suc n"
 hence "ind ≥ n" by auto
 with Asm have "ind = n" by auto
 thus "initMsg ind = initMsg n" by auto
 qed
 have InitInitial: "∀c ∈ set initCfgList . initial c"
 unfolding initial_def initCfgList_def initMsg_def using InitCfgStart
 by auto
 with InitCfgSet have InitInitReachable:
 "∀ c ∈ set initCfgList . initReachable c"
 using reachable.simps
 unfolding initReachable_def
 by blast

 define c0 where "c0 = initCfgist 0
 hence "c0 = ( states = start, msgs = initMsg 0 )"
 using InitCfgLength nth_map_upt[of 0 "n+1" 0]
 unfolding initCfgList_def by auto
 hence MsgC0: "msgs c0 = (λm. if ∃p. m = <p, inM False> then 1 else 0)"
 unfolding initMsg_def by simp
 
 define cN where "cN = initCfgList ! n"
 hence "cN = (
 using InitCfgLength nth_map_upt[of n "n+1" 0]
 unfolding initCfgList_def
 by auto
 hence MsgCN: "msgs cN = (λm. if ∃p. m = <p, inM True> then 1 else 0)"
 unfolding initMsg_def
 using AllPInProclist
 by auto

 have C0NotCN: "c0 ≠ cN"
 proof
 assume "c0 = cN"
 hence StrangeEq: "(λm::('p, 'v) message.
 if ∃p. m = <p, inM False> then 1 else 0 :: nat) =
 (λm. if ∃p. m = <p, inM True> then 1 else 0)"
 using InitCfgLength N minimalProcs MsgC0 MsgCN
 unfolding c0_def cN_def by auto
 thus "False"
 by (metis message.inject(1) zero_neq_one)
 qed

 have C0NAreUniform: "∧ cX . (cX = c0) ∨ (cX = cN)
 ==> vUniform (cX = cN) cX"
 proof-
 fix cX
 assume xIs0OrN: "(cX = c0) ∨
 have xInit: "initial cX"
 using InitCfgLength InitCfgSet set_conv_nth[of initCfgList] xIs0OrN
 unfolding c0_def cN_def
 by (auto simp add: InitInitial)
 from Validity
 have COnlyReachesOneDecision:
 "∀ c . reachable cX c ∧ decided c ⟶ (vDecided (cX = cN) c)"
 unfolding validity_def initReachable_def
 proof auto
 fix c cfg0 v
 assume
 Validity: "(∀i c. ((initial i) ∧ (reachable i c)) ⟶
 (∀v. (0 < msgs
 ⟶ (∃p. (0 < msgs i (<p, inM v>)))))" and
 OutMsg: "0 < msgs c <\<bottom>, outM v>" and
 InitCXReachable: "reachable cX c"
 thus "0 < msgs c <\<bottom>, outM (cX = cN)>"
 using xIs0OrN
 proof (cases "v = (cX = cN)", simp)
 assume "v ≠ (cX = cN)"
 hence vDef: "v = (cX ≠ cN)" by auto
 with Validity InitCXReachable OutMsg xInit
 have ExistMsg: "∃p. (0 < msgs cX (<p, inM
 with initMsg_def have False
 using xIs0OrN
 by (auto simp add: MsgC0 MsgCN C0NotCN)
 thus "0 < msgs c <\<bottom>, outM cX = cN>" by simp
 qed
 qed
 have InitRInitC: "initReachable cX" using xInit InitialIsInitReachable
 by auto
 have NoWrongDecs: "∧ v p cc::('p, 'v, 's) configuration.
 qReachable cX (Proc - {p}) cc ∧ initReachable cc
 ∧ 0 < msgs cc <\<bottom>, outM v>
 ==> v = (cX = cN)"
 proof clarify
 fix v p cc
 assume Asm: "qReachable cX (Proc - {p}) cc" "initReachable cc"
 "0 < msgs cc <\<bottom>, outM v>"
 hence "reachable cX cc" "decided cc" using QReachImplReach by auto
 hence "¬(vDecided (cX ≠ cN) cc)"
 using COnlyReachesOneDecision Agreement Asm C0NotCN xInit xIs0OrN
 unfolding agreementInit_def by metis
 with Asm C0NotCN xIs0OrN show "v = (cX = cN)"
 by (auto, metis (full_types) neq0_conv)
 qed
 have ExRightDecs: "∧p. ∃cc. qReachable (cX) (Proc - {p}) cc
 ∧ initReachable cc ∧ 0 < msgs cc <\<bottom>, outM (cX = cN)>"
 proof-
 fix p
 show "∃cc::('p, 'v, 's) configuration.
 qReachable cX (Proc - {p}) cc ∧ initReachable cc
 ∧ cc <\<bottom>, outM cX = cN>"
 using Termination[of "cX" "Proc - {p}"] finiteProcs minimalProcs
 InitRInitC
 unfolding terminationPseudo_def
 proof auto
 fix cc v
 assume
 Asm: "initReachable cX" "qReachable (cX) (Proc - {p}) cc"
 "initReachable cc" "0 < msgs cc <\<bottom>, outM v>"
 with COnlyReachesOneDecision[rule_format, of "cc"] QReachImplReach
 have "0 < msgs cc <\<bottom>, outM cX = cN>" by auto
 with Asm
 show "∃cc::('p, 'v, 's) configuration.
 qReachable cX (Proc - {p}) cc
 ∧ initReachable cc ∧ (0::nat) < msgs cc <\<bottom>, outM cX = cN>"
  f "frac ?l e
 qed
 qed
 have ZeroinPSilent: "∀ p v . v ∈ val[p, cX] ⟷ v = (cX = cN)"
 proof clarify
 fix p v
 show "v ∈ val[p, cX] ⟷ v = (cX = cN)"
 unfolding pSilDecVal_def
 s0OrN0C oWoDec ExihDec y auo
 qed
 thus "vUniform (cX = cN) cX" using InitRInitC
 unfolding vUniform_def by auto
 qed
 hence
 C0Is0Uniform: "vUniform False c0" and
 CNNot0Uniform: "¬ vUniform False cN"
 using C0NAreUniform unfolding vUniform_def using C0NotCN by auto
 hence "∃ j < n. vUniform False (initCfgList ! j)
 ∧ ¬(vUniform False (initCfgList ! Suc j))"
 unfolding c0_def cN_def
 using NatPredicate
 [of n "λx. vUniform False (initCfgList ! x)"] NGr0 by auto
 then obtain j
 where J: "j < n"
 "vUniform False (initCfgList ! j)"
 "¬(vUniform False (initCfgList ! Suc j))" by blast
 define pJ where "pJ = procList ! j"
 define cJ where "cJ = initCfgList ! j"
 hence cJDef: "cJ = ( states = start, msgs = initMsg j)"
 using J(1) InitCfgLength nth_map_upt[of 0 "j- 1" 1]
 nth_map_upt[of "j" "n + 1" 0]
 unfolding initCfgList_def
 by auto
 hence MsgCJ: "msgs cJ = (λm::('p, 'v) message.
 if ∃p::'p. m = <p, inM ∃i<j. procList ! i = p> then 1::nat
 else (0::nat))"
 unfolding initMsg_def
 using AllPInProclist
 by auto
 define cJ1 where "cJ1 = initCfgList ! (Suc j)"
 hence cJ1Def: "cJ1 = ( states = start, msgs = initMsg (Suc j))"
 using rivate AOT_lemm eqnotnec_123_Aux_θφ ≡ ∀x([L]x ≡z φ
 nth_map_upt[of "j + 1" "n + 1" 0]
 unfolding initCfgL note T = this
 by auto
 hence MsgCJ1: "msgs cJ1 = (λm::('p, 'v) message.
 if ∃p::'p. m = <p, inM ∃i<(Suc j). procList ! i = p> then 1::nat
 else (0::nat))"
 unfolding initMsg_def
 using AllPInProclist
 by auto
 have CJ1Init: "initial cJ1"
 using InitInitial[rule_format, of cJ1] J(1) InitCfgLength
 unfolding cJ1_def by auto
 hence CJ1InitR: "initReachable cJ1"
 using InitialIsInitReachable by simp
 have ValPj0: "False ∈ val[pJ, cJ]"
 using J(2) unfolding cJ_def vUniform_def by auto
 hence "∃cc. vDecided False cc ∧ withoutQReachable cJ {pJ} cc"
 unfolding pSilDecVal_def by auto
 then obtain cc
 where CC: "vDecided False cc" "withoutQReachable cJ {pJ} cc"
 by blast
 hence "∃Q. qReachable cJ Q cc ∧ Q = Proc - {pJ}" by blast
 then obtain ccQ where CCQ: "qReachable cJ ccQ cc" "ccQ = Proc - {pJ}"
 by blast
 have StatescJcJ1: "states cJ = states cJ1"
 using cJ_def cJ1_def initCfgList_def
 by (metis InitCfgLength InitCfgStart J(1) Suc_eq_plus1 Suc_mono
 less_SucI nth_mem)
 have Distinct: "∧ i . distinct procList ==> i<j 
  show ?thesis
 by (metis J(1) ProcList(1) distinct_conv_nth less_trans
 not_less_iff_gr_or_eq)
 have A: "msgs cJ (<pJ 
 using pJ_def ProcList J(1) MsgCJ using Distinct by auto
 have B: "msgs cJ1 (<pJ ,inM True>) = 1"
 using pJ_def ProcList J(1) MsgCJ1 by auto
 have C: "msgs cJ (<pJ ,inM True>) = 0"
 using pJ_def ProcList J(1) MsgCJ using Distinct by auto
 have D: "msgs cJ1 (<pJ ,inM False>) = 0"
 using pJ_def ProcList J(1) MsgCJ1 by auto
 define msgsCJ' where
 "msgsCJ' m = (if m = (<pJ "?U= {}")
 have MsgsCJ': "msgsCJ' = ((msgs cJ) -# (<pJ ,inM False>))"
 using A C msgsCJ'_def by auto
 have AllOther: "∀ m . msgsCJ' m = ((msgs cJ1) -# (<pJ ,inM True>)) m"
 using B D MsgCJ1 MsgCJ J(1) N ProcList AllPInProclist
 unfolding msgsCJ'_def pJ_def
 proof(clarify)
 fix m
 show "(if m = <procList ! j, inM False> ∨x
 m = <procList ! j, inM True> then 0 else msgs cJ m)
 = (msgs cJ1 -# <procList 
 proof(cases "m = <procList ! j, inM False> ∨ m
 = <procList ! j, inM True>",auto)
 assume "0 < (msgs cJ1 <procList 
 thus False using D pJ_def by (metis less_nat_zero_code)
 next
 show "msgs cJ1 <procList ! j, inM True> ≤ Suc 0"
 by (metis B One_nat_def order_refl pJ_def)
 next
 assume AssumpMJ: "m ≠ <procList ! j, inM False>"
 "m ≠ <procList ! j, inM True>"
 hence "(if ∃p. m = <p, inM ∃i<j. procList ! i = p> then 1 else 0)
 = (if ∃p. m = <p, inM ∃i<Suc j. procList ! i = p> then 1 else 0)"
 by (induct m, auto simp add: less_Suc_eq)
 thus "msgs cJ m = msgs cJ1 m"
 using MsgCJ MsgCJ1 by auto
 qed
 qed ― ‹of AllOther›

 with MsgsCJ' have InitMsgs: "((msgs cJ) -# (<pJ ,inM False>))
 = ((msgs cJ1) -# (<pJ, inM True>))"
 by simp
 hence F: "(((msgs cJ) -# (<pJ ,inM False>)) ∪# ({#<pJ, inM True>})) =
 (((msgs cJ1) -# (<pJ, inM True>)) ∪# ({#<pJ, inM True>}))"
 by (metis (full_types))
 from B have One: "(((msgs cJ1) -# (<pJ,case False
 ∪# ({#<pJ, inM True>})) <pJ, inM True> = 1" by simp
 with B have "∀ m :: ('p, 'v) message . (msgs cJ1) m
 = (((msgs cJ1) -# (<pJ, inM True>)) ∪#
 ({#<pJ, inM True>})) with T have "frac ?l = 0" b
 with B have "(((msgs cJ1) -# (<pJ, inM True>)) ∪# ({#<pJ, inM True>}))
 = (msgs cJ1)" by simp
 with F have InitMsgs: "(((msgs cJ) -# (<pJ ,inM False>))
 ∪# ({#<pJ, inM True>})) = (msgs cJ1)"
 by simp
 define cc' where "cc' = (states = (states cc),
 msgs = (((msgs cc) -# (<pJ,φ›
 have "[qReachable cJ ccQ cc; ccQ = Proc - {pJ};
 (((msgs cJ) -# (<pJ ,inM False>)) ∪# ({#<pJ, inM True>}))
 = (msgs cJ1); states cJ = states cJ1]
 ==> withoutQReachable cJ1 {pJ} (states = (states cc),
 msgs = (((msgs cc) -# (<pJ,
 proof (induct rule: qReachable.induct)
 fix cfg1::"('p, AOT_h ‹23z.
 fix Q
 assume
 Assm: "(((msgs cfg1) -#(<pJ, inM False>)) ∪# {# <pJ, inM True> })
 = msgs cJ1"
 "states cfg1 = states cJ1"
 hence CJ1: "cJ1 = (states = states cfg1,
 msgs = ((msgs cfg1) -# <pJ,>
 have "qReachable cJ1 (Proc - {pJ}) cJ1" using qReachable.simps
 by blast
 with Assm show "qReachable cJ1 (Proc - {pJ})
 (states = states cfg1, msgs = ((msgs cfg1) -# <pJ,
 ∪# {# <pJ, inM True> })" using CJ1 by blast
 fix cfg1 cfg2 cfg3 :: "('p, 'vusing "if-p-then-p" 1 "\equivII yip
 fix msg
 assume Q: "Q = (Proc - {pJ})"
 assume "(((msgs cfg1) -# <pJ,
 = (msgs cJ1)"
 "(states cfg1) = (states cJ1)"
 "Q = (Proc - {pJ}) ==>
 (((msgs cfg1) -# <pJ, inM False>) ∪# {# <pJ, inM True> })
 = (msgs cJ1)
 ==> (states cfg1 statescJ1
 ==> qReachable cJ1 (Proc - {pJ})
 (states = (states cfg2),
 msgs = (((msgs cfg2) -# <pJ, inM False>) ∪# {# <pJ, inM True> }))"
 with Q have Cfg2:
 "qReachable cJ1 (Proc - {pJ}) (states = (states cfg2),
 msgs = (((msgs cfg2) -# <pJ, inM False>) ∪# {# <pJ, inM True> }))"
 mp
 assume "qReachable cfg1 Q cfg2"
 "cfg2 ⊨ msg ↦ then havel: "?l= c + MMa ?L" "fr ?l = Ma ?L" us Max_in[OF fi(1)‹
 "∃(p::'p)∈Q. (isReceiverOf p msg)"
 with Q have Step: "qReachable cfg1 (Proc - {pJ}) cfg2"
 "cfg2 ⊨ msg ↦ cfg3"
 "∃(p::'p)∈(Proc - {pJ}). (isReceiverOf p msg)" by auto
 then obtain p where P: "p∈(Proc - {pJ})" "isReceiverOf p msg" by blast
 hence NotEq: "pJ ≠ p" by blast
 with UniqueReceiverOf[of "p" "msg" "pJ"] P(2)
 have notRec: "¬ (isReceiverOf pJ msg)" by blast
 hence MsgNoIn:"msg ≠ <pJ, inM False> ∧ msg ≠ <pJ,finally AOT_show 🚫L]x ≡ [λz φ]x›
 by auto
 from Step(2) have "enabled cfg2 msg" using steps.simps
 by (auto, cases msg, auto)
 hence MsgEnabled: "enabled (states = (states cfg2),
 msgs = (((msgs cfg2) -# <pJ, inM False>)
 ∪# {# <pJ, inM True> })) msg"
 using MsgNoIn by (simp add: enabled_def)
 have "(states = (states cfg2),
 msgs = (((msgs cfg2) -# <pJ, inM False>)
 ∪# {# <pJ, inM True> }))
 ⊨ msg ↦ (states = (states cfg3),
 msgs = (((msgs cfg3) -# <pJ,
 ∪
 proof (cases msg)
 fix p' bool
 assume MsgIn :"(msg = <p', inM bool>)"
 with noInSends MsgIn MsgNoIn MsgEnabled
 show "(states = (states cfg2),
 msgs = (((msgs cfg2) -# <pJ,
 ⊨ msg ↦ (states = (states cfg3),
 msgs = (((msgs cfg3) -# <pJ, inM False>)
 ∪# {# <pJ,
 using steps.simps(1) Step(2) select_convs(2) select_convs(1)
 by auto
 next
 fix bool
 assume "(msg = <\<bottom>, outM bool>)"
 thus "(states = (states cfg2),
 msgs = (((msgs cfg2) -# <pJ, inM False>) ∪# {# <pJ, inM True> }))
 
 msgs = (((msgs cfg3) -# <pJ, inM False>)
 ∪# {# <pJ, inM True> }))"
 using steps_def Step(2) by auto
 next
 fix p v
 assume "(msg = <p, v>)"
 with noInSends MsgNoIn MsgEnabled show "(states = (states cfg2),
 msgs = (((msgs cfg2) -# <pJ, inM False>) ∪# {# <pJ, inM True> }))
 ⊨ \equivl>z 🚫
 msgs = (((msgs cfg3) -# <pJ, inM False>)
 ∪# {# <pJ, inM True> }))"
 using steps.simps(1) Step(2) select_convs(2) select_convs(1) by auto
 qed
 with Cfg2 Step(3) show "qReachable cJ1 (Proc - {pJ})
 (states = (states cfg3),
 msgs = (((msgs cfg3) -# <pJ, inM False>) ∪# {# <pJ, inM True> }))"
 using
 qReachable.simps[of "cJ1" "(Proc - {pJ})"
 "(states = (states cfg3),
 msgs = (((msgs cfg3) -# <pJ, inM False>)
 ∪[L]x ≡ [λz φ]x› using "∀
 qed
 with CCQ(1) CCQ(2) InitMsgs StatescJcJ1 have CC':
 "withoutQReachable cJ1 {pJ} (states = (states cc),
 msgs = (((msgs cc) -# (<pJ, auto
 ∪# {# (<pJ, inM True>)}) )" by auto
 with QReachImplReach CJ1InitR initReachable_def reachable.simps
 ReachableTrans
 have "initReachable (states = (states cc),
 msgs = (((msgs cc) -# (<pJ,inM False>))
 ∪# {# (<pJ, inM True>)}) )" by meson
 with CC' have "False ∈ val[pJ, cJ1]"
 unfolding pSilDecVal_def
 using CJ1InitR CC(1) select_convs(2) by auto
 hence "¬(vUniform True (cJ1))"
  so AOT_have \ ‹ φ›
 using CJ1InitR by blast
 hence "nonUniform cJ1"
 using J(3) CJ1InitR unfolding cJ1_def by auto
 thus ?thesis
 using CJ1Init by blast
 

 ‹
 Völzer's Lemma 2 proves that for every process $p$ in the consensus setting
 \isb{nonUniform} configurations can reach a configuration where the silent
 decision values of $p$ are True and False. This is key to the construction of
 non-deciding executions.

 \voelzer{Lemma 2}
 ›
  NonUniformCanReachSilentBivalence:
 
 p:: 'p and
 c:: "('p, 'v, 's) configuration"
 
 NonUni: "nonUniform c" and
 PseudoTermination: "∧cc Q . terminationPseudo 1 cc Q" and
 Agree: "∧ cfg . reachable c cfg ⟶ agreement cfg"
 
 "∃ c' . reachable c c' ∧ val[p,c'] = {True, False}"
 (cases "val[p,c] = {True, False}")
 case True
 have "reachable c c" using reachable.simps by metis
 thus ?thesis
 using True by blast
 
 case False
 hence notEq: "val[p,c] ≠ {True, False}" by simp
 from NonUni PseudoTermination DecisionValuesExist
 have notE: "∀q. val[q,c] ≠ {}" by simp
 hence notEP: "val[p,c] ≠ {}" by blast
 have valType: "∀q. val[q,c] ⊆ {True, False}" using pSilDecVal_def
 by (metis (full_types) insertCI subsetI)
 hence "val[p,c] ⊆ {True, False}" by blast
 with notEq notEP have "∃b:: bool. val[p,c] = {b}" by blast
 then obtain b where B: "val[p,c] = {b}" by auto
 from NonUni vUniform_def have
 NonUni: "(∃q. val[q,c] ≠ {True}) ∧ (∃q. val[q,c] ≠ {False})" by simp
 have Bool: "b = True ∨ b = False" by simp
 with NonUni have "∃q. val[q,c] ≠ {b}" by blast
  oq where Q: "val[q,c] \noteq{b}" by auto

 have "val[q,c] = {True} ∨ val[q,c] = {False} ∨ val[q,c] = {True, False}"
 by auto
 with Bool Q have "val[q,c] = {¬b} ∨ val[q,c] = {b, ¬b}" by blast
 hence "(¬b) ∈ val[q,c]" by blast
 with pSilDecVal_def
 have "∃ c'::('p, 'v, 's) configuration . (withoutQReachable c {q} c') ∧
 vDecided (¬b) c'" by simp
 then obtain c' where C': "withoutQReachable c {q} c'" "vDecided (¬b) c'"
 by auto
 hence Reach: "reachable c c'" using QReachImplReach by simp
 have "∀ cfg . reachable c' cfg ⟶ agreement cfg"
  carify
 fix cfg
 assume "reachable c' cfg"
 with Reach have "reachable c cfg"
 using ReachableTrans[of c c'] by simp
 with Agree show "agreement cfg" by simp
 qed
 C'(2DecidedI have "vUniform (\<>)
 by simp
 hence notB: "val[p,c'] = {¬b}" using vUniform_def by simp
 with Reach B show "∃ cfg. reachable c cfg ∧ val[p,cfg] = {True, False}"
 proof(induct rule: reachable.induct, simp)
 fix cfg1 cfg2 cfg3 msg
 assume
 IV: "val[p,cfg1] = {b} ==>
 val[p,cfg2] = {¬ b} ==>
 ∃cfg::('p, 'v, 's) configuration. reachable cfg1 cfg
 ∧ val[p,cfg] = {True, False}" and
 Reach: "reachable cfg1 cfg2" and
 Step: "cfg2 ⊨ msg ↦ cfg3" and
 ValCfg1: "val[p,cfg1] = {b}" and
 ValCfg3: "val[p,cfg3] = {¬ b}"
 from ValCfg1 have InitCfg1: "initReachable cfg1"
 using pSilDecVal_def by auto
 from Reach InitCfg1 initReachable_def reachable.simps ReachableTrans
 have InitCfg2: "initReachable cfg2" by blast
 with PseudoTermination DecisionValuesExist
 have notE: "∀q. val[q,cfg2] ≠ {}" by simp
 have valType: "∀finally AOT_show 🚫
 by (metis (full_types) insertCI subsetI)
 from notE valType
 have "val[p,cfg2] = {True} ∨ val[p,cfg2] = {False}
 ∨ val[p,cfg2] = {True, False}"
 by auto
 with Bool have Val: "val[p,cfg2] = {b} ∨ val[p,cfg2] = {¬b}
 ∨ val[p,cfg2] = {True, False}"
 by blast
 show "∃cfg::('p, 'v, 's) configuration. reachable cfg1 cfg
 ∧ val[p,cfg] = {True, False}"
 proof(cases "val[p,cfg2] = {b}")
 case True
 hence B: "val[p,cfg2] = {b}" by simp
 from Step have RecOrOut: "∃q. isReceiverOf q msg" by(cases msg, auto)
 then obtain q where Rec: "isReceiverOf q msg" by auto
 with B Step InitCfg2 SilentDecisionValueNotInverting
 have "val[p,cfg3] ≠ {¬
 with ValCfg3 have "False" by simp
 thus "∃cfg::('p, 'v, 's) configuration. reachable cfg1 cfg ∧
 val[p,cfg] = {True, False}" by simp
 next
 case False
 with Val have Val: "val[p,cfg2] = {¬b} ∨ val[p,cfg2] = {True, False}"
 by simp
 show "∃
 val[p,cfg] = {True, False}"
 proof(cases "val[p,cfg2] = {¬b}")
 case True
 hence "val[p,cfg2] = {¬b}" by simp
 with ValCfg1 IV show
 "∃cfg::('p, 'v, 's) configuration.
 reachable cfg1 cfg ∧ val[p,cfg] = {True, False}"
 by simp
 next
 case False
 with Val have "val[p,cfg2] = {True, False}" by simp
 with Reach have "reachable cfg1 cfg2 ∧ val[p,cfg2] = {True, False}"
 by blast
 from this show "∃cfg::('p, 'v, 's) configuration.
 reachable cfg1 cfg ∧ val[p,cfg] = {True, False}" by blast
 qed
 qed
 qed