Step
*
of Lemma
new_23_sig_decided_property
∀[Cmd:ValueAllType]. ∀[eq:EqDecider(Cmd)]. ∀[reps,clients:bag(Id)]. ∀[coeff,flrs:ℤ]. ∀[propose,notify:Atom List].
∀[slots:set-sig{i:l}(ℤ)]. ∀[f:new_23_sig_headers_type{i:l}(Cmd;notify;propose)]. ∀[es:EO+(Message(f))].
(new_23_sig_message-constraint{i:l}(Cmd;clients;eq;coeff;flrs;notify;propose;reps;slots;f)
⇒ (∀e:E. ∀c:Cmd. ∀n:ℤ.
(<n, c> ∈ new_23_sig_decided'base(Cmd;notify;propose;f)(e)
⇒ (↓∃x:Id
∃rnd:ℕ
∃L:Id List
(no_repeats(Id;L)
∧ (||L|| = ((coeff * flrs) + 1) ∈ ℤ)
∧ (∀vtr∈L.↓∃e':E. mk-msg-interface(x;make-Msg(``new_23_sig vote``;<<<n, rnd>, c>, vtr>)) ∈ new_23_sig_ma\000Cin()(e')))))))
BY
{ (Unfold `vatype` 0
THEN Auto
THEN AddMessageHeaderTypes
THEN (UseMessageConstraint (-3) THENA Auto)
THEN SquashExRepD
THEN D (-1)
THEN SquashExRepD
THEN Try ((InstLemma `poss-maj-unanimous` [⌈Cmd⌉;⌈eq⌉;⌈[snd(fst(msgval(e'))) /
(fst(new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, 0>;e\000Cs.e1;e')))]⌉;⌈snd(fst(msgval(e')))⌉;⌈c⌉]⋅
THENA Complete ((Auto
THEN Reduce 0
THEN (RW (AddrC [2] (LemmaC `pair-eta`)) 0 THENA Auto)
THEN EqCD
THEN Auto
THEN GenConclAtAddr [2;1]
THEN Auto))
))) }
1
1. Cmd : {T:Type| valueall-type(T)}
2. eq : EqDecider(Cmd)
3. reps : bag(Id)
4. clients : bag(Id)
5. coeff : ℤ
6. flrs : ℤ
7. propose : Atom List
8. notify : Atom List
9. slots : set-sig{i:l}(ℤ)
10. f : new_23_sig_headers_type{i:l}(Cmd;notify;propose)
11. es : EO+(Message(f))
12. new_23_sig_message-constraint{i:l}(Cmd;clients;eq;coeff;flrs;notify;propose;reps;slots;f)@i'
13. e : E@i
14. c : Cmd@i
15. n : ℤ@i
16. <n, c> ∈ new_23_sig_decided'base(Cmd;notify;propose;f)(e)@i
17. (f propose) = (ℤ × Cmd) ∈ Type
18. (f notify) = (ℤ × Cmd) ∈ Type
19. (f ``new_23_sig decided``) = (ℤ × Cmd) ∈ Type
20. (f ``new_23_sig retry``) = (ℤ × ℤ × Cmd) ∈ Type
21. (f ``new_23_sig vote``) = (ℤ × ℤ × Cmd × Id) ∈ Type
22. f ∈ Name ─→ Type
23. e' : E
24. delay : ℤ
25. (e' < e)
26. loc(e') ↓∈ reps
27. e1 : {e1:E| e1 ≤loc e' }
28. z1 : ℤ
29. z2 : Cmd
30. ((header(e1) = propose ∈ Name) ∧ has-es-info-type(es;e1;f;ℤ × Cmd) ∧ (<z1, z2> = msgval(e1) ∈ (ℤ × Cmd)))
∨ ((header(e1) = ``new_23_sig vote`` ∈ Name)
∧ has-es-info-type(es;e1;f;ℤ × ℤ × Cmd × Id)
∧ (z1 = (fst(fst(fst(msgval(e1))))) ∈ ℤ)
∧ (z2 = (snd(fst(msgval(e1)))) ∈ Cmd))
31. ¬↑(set-sig-member(slots) z1 new_23_sig_ReplicaStateFun(Cmd;notify;propose;slots;f;es;e1))
32. (no new_23_sig_Notify(Cmd;clients;notify;propose;f) z1 between e1 and e')
33. (no new_23_sig_Quorum(Cmd;eq;coeff;flrs;notify;propose;reps;f) <z1, 0> between e1 and e')
34. header(e') = ``new_23_sig vote`` ∈ Name
35. has-es-info-type(es;e';f;ℤ × ℤ × Cmd × Id)
36. ↑(new_23_sig_newvote(Cmd) <z1, 0> msgval(e') new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, 0>;es.e1;e'))
37. ||fst(new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, 0>;es.e1;e'))|| = (coeff * flrs) ∈ ℤ
38. delay = 0 ∈ ℤ
39. (fst(poss-maj(eq;[snd(fst(msgval(e'))) / (fst(new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, 0>;es.e1;e')))];sn\000Cd(fst(msgval(e')))))) = ((coeff * flrs) + 1) ∈ ℤ
40. loc(e) ↓∈ reps
41. msg-authentic(info(e)) = ff
42. n = (fst(fst(fst(msgval(e'))))) ∈ ℤ
43. c = (snd(poss-maj(eq;[snd(fst(msgval(e'))) / (fst(new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, 0>;es.e1;e')))\000C];snd(fst(msgval(e')))))) ∈ Cmd
44. (∀z∈[snd(fst(msgval(e'))) / (fst(new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, 0>;es.e1;e')))].z = c ∈ Cmd)
⊢ ↓∃x:Id
∃rnd:ℕ
∃L:Id List
(no_repeats(Id;L)
∧ (||L|| = ((coeff * flrs) + 1) ∈ ℤ)
∧ (∀vtr∈L.↓∃e':E. mk-msg-interface(x;make-Msg(``new_23_sig vote``;<<<n, rnd>, c>, vtr>)) ∈ new_23_sig_main()(e')))
2
1. Cmd : {T:Type| valueall-type(T)}
2. eq : EqDecider(Cmd)
3. reps : bag(Id)
4. clients : bag(Id)
5. coeff : ℤ
6. flrs : ℤ
7. propose : Atom List
8. notify : Atom List
9. slots : set-sig{i:l}(ℤ)
10. f : new_23_sig_headers_type{i:l}(Cmd;notify;propose)
11. es : EO+(Message(f))
12. new_23_sig_message-constraint{i:l}(Cmd;clients;eq;coeff;flrs;notify;propose;reps;slots;f)@i'
13. e : E@i
14. c : Cmd@i
15. n : ℤ@i
16. <n, c> ∈ new_23_sig_decided'base(Cmd;notify;propose;f)(e)@i
17. (f propose) = (ℤ × Cmd) ∈ Type
18. (f notify) = (ℤ × Cmd) ∈ Type
19. (f ``new_23_sig decided``) = (ℤ × Cmd) ∈ Type
20. (f ``new_23_sig retry``) = (ℤ × ℤ × Cmd) ∈ Type
21. (f ``new_23_sig vote``) = (ℤ × ℤ × Cmd × Id) ∈ Type
22. f ∈ Name ─→ Type
23. e' : E
24. delay : ℤ
25. (e' < e)
26. loc(e') ↓∈ reps
27. e1 : {e1:E| e1 ≤loc e' }
28. z1 : ℤ
29. z2 : Cmd
30. ((header(e1) = propose ∈ Name) ∧ has-es-info-type(es;e1;f;ℤ × Cmd) ∧ (<z1, z2> = msgval(e1) ∈ (ℤ × Cmd)))
∨ ((header(e1) = ``new_23_sig vote`` ∈ Name)
∧ has-es-info-type(es;e1;f;ℤ × ℤ × Cmd × Id)
∧ (z1 = (fst(fst(fst(msgval(e1))))) ∈ ℤ)
∧ (z2 = (snd(fst(msgval(e1)))) ∈ Cmd))
31. ¬↑(set-sig-member(slots) z1 new_23_sig_ReplicaStateFun(Cmd;notify;propose;slots;f;es;e1))
32. (no new_23_sig_Notify(Cmd;clients;notify;propose;f) z1 between e1 and e')
33. e2 : {e1:E| e1 ≤loc e' }
34. z6 : ℤ
35. z7 : Cmd
36. new_23_sig_NewRoundsStateFun(Cmd;notify;propose;f;z1;es.e1;e2) < z6
37. ((header(e2) = ``new_23_sig retry`` ∈ Name)
∧ has-es-info-type(es;e2;f;ℤ × ℤ × Cmd)
∧ (<<z1, z6>, z7> = msgval(e2) ∈ (ℤ × ℤ × Cmd)))
∨ ((header(e2) = ``new_23_sig vote`` ∈ Name)
∧ has-es-info-type(es;e2;f;ℤ × ℤ × Cmd × Id)
∧ (<<z1, z6>, z7> = (fst(msgval(e2))) ∈ (ℤ × ℤ × Cmd)))
38. (no new_23_sig_Quorum(Cmd;eq;coeff;flrs;notify;propose;reps;f) <z1, z6> between e2 and e')
39. header(e') = ``new_23_sig vote`` ∈ Name
40. has-es-info-type(es;e';f;ℤ × ℤ × Cmd × Id)
41. ↑(new_23_sig_newvote(Cmd) <z1, z6> msgval(e') new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, z6>;es.e2;e'))
42. ||fst(new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, z6>;es.e2;e'))|| = (coeff * flrs) ∈ ℤ
43. delay = 0 ∈ ℤ
44. (fst(poss-maj(eq;[snd(fst(msgval(e'))) / (fst(new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, z6>;es.e2;e')))];s\000Cnd(fst(msgval(e')))))) = ((coeff * flrs) + 1) ∈ ℤ
45. loc(e) ↓∈ reps
46. msg-authentic(info(e)) = ff
47. n = (fst(fst(fst(msgval(e'))))) ∈ ℤ
48. c = (snd(poss-maj(eq;[snd(fst(msgval(e'))) / (fst(new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, z6>;es.e2;e'))\000C)];snd(fst(msgval(e')))))) ∈ Cmd
⊢ ↓∃x:Id
∃rnd:ℕ
∃L:Id List
(no_repeats(Id;L)
∧ (||L|| = ((coeff * flrs) + 1) ∈ ℤ)
∧ (∀vtr∈L.↓∃e':E. mk-msg-interface(x;make-Msg(``new_23_sig vote``;<<<n, rnd>, c>, vtr>)) ∈ new_23_sig_main()(e')))
Latex:
Latex:
\mforall{}[Cmd:ValueAllType]. \mforall{}[eq:EqDecider(Cmd)]. \mforall{}[reps,clients:bag(Id)]. \mforall{}[coeff,flrs:\mBbbZ{}].
\mforall{}[propose,notify:Atom List]. \mforall{}[slots:set-sig\{i:l\}(\mBbbZ{})].
\mforall{}[f:new\_23\_sig\_headers\_type\{i:l\}(Cmd;notify;propose)]. \mforall{}[es:EO+(Message(f))].
(new\_23\_sig\_message-constraint\{i:l\}(Cmd;clients;eq;coeff;flrs;notify;propose;reps;slots;f)
{}\mRightarrow{} (\mforall{}e:E. \mforall{}c:Cmd. \mforall{}n:\mBbbZ{}.
(<n, c> \mmember{} new\_23\_sig\_decided'base(Cmd;notify;propose;f)(e)
{}\mRightarrow{} (\mdownarrow{}\mexists{}x:Id
\mexists{}rnd:\mBbbN{}
\mexists{}L:Id List
(no\_repeats(Id;L)
\mwedge{} (||L|| = ((coeff * flrs) + 1))
\mwedge{} (\mforall{}vtr\mmember{}L.\mdownarrow{}\mexists{}e':E
mk-msg-interface(x;make-Msg(``new\_23\_sig vote``;<<<n, rnd>, c>, vtr>)) \mmember{}\000C new\_23\_sig\_main()(e')))))))
By
Latex:
(Unfold `vatype` 0
THEN Auto
THEN AddMessageHeaderTypes
THEN (UseMessageConstraint (-3) THENA Auto)
THEN SquashExRepD
THEN D (-1)
THEN SquashExRepD
THEN Try ((InstLemma `poss-maj-unanimous` [\mkleeneopen{}Cmd\mkleeneclose{};\mkleeneopen{}eq\mkleeneclose{};
\mkleeneopen{}[snd(fst(msgval(e'))) / (fst(new\_23\_sig\_QuorumStateFun(Cmd;notify;propose;f;<z1, 0>es.\000Ce1;e')))]\mkleeneclose{};\mkleeneopen{}snd(fst(msgval(e')))\mkleeneclose{};\mkleeneopen{}c\mkleeneclose{}]\mcdot{}
THENA Complete ((Auto
THEN Reduce 0
THEN (RW (AddrC [2] (LemmaC `pair-eta`)) 0 THENA Auto)
THEN EqCD
THEN Auto
THEN GenConclAtAddr [2;1]
THEN Auto))
)))
Home
Index