Nuprl Lemma : new_23_sig-retry

[Cmd:{T:Type| valueall-type(T)} ]. ∀[clients:bag(Id)]. ∀[cmdeq:EqDecider(Cmd)]. ∀[coeff,flrs:ℤ].
[notify,propose:Atom List]. ∀[reps:bag(Id)]. ∀[slots:set-sig{i:l}(ℤ)].
[f:new_23_sig_headers_type{i:l}(Cmd;notify;propose)]. ∀[es:EO+(Message(f))]. ∀[e:E]. ∀[d:ℤ]. ∀[i:Id]. ∀[auth:𝔹].
[k,k1:ℤ]. ∀[v:Cmd].
  (<d, i, mk-msg(auth;``new_23_sig retry``;<<k, k1>v>)> ∈ new_23_sig_main()(e)
  ⇐⇒ loc(e) ↓∈ reps
      ∧ (↓∃e':{e':E| e' ≤loc 
           ∃z1:ℤ
            ∃z2:Cmd
             (((((header(e') propose ∈ Name) ∧ has-es-info-type(es;e';f;ℤ × Cmd) ∧ (<z1, z2> msgval(e') ∈ (ℤ × Cmd))\000C)
              ∨ ((header(e') ``new_23_sig vote`` ∈ Name)
                ∧ has-es-info-type(es;e';f;ℤ × ℤ × Cmd × Id)
                ∧ (z1 (fst(fst(fst(msgval(e'))))) ∈ ℤ)
                ∧ (z2 (snd(fst(msgval(e')))) ∈ Cmd)))
              ∧ (¬↑(set-sig-member(slots) z1 new_23_sig_ReplicaStateFun(Cmd;notify;propose;slots;f;es;e'))))
             ∧ (no new_23_sig_Notify(Cmd;clients;notify;propose;f) z1 between e' and e)
             ∧ (((no new_23_sig_Quorum(Cmd;cmdeq;coeff;flrs;notify;propose;reps;f) <z1, 0> between e' and e)
               ∧ ((header(e) ``new_23_sig vote`` ∈ Name) ∧ has-es-info-type(es;e;f;ℤ × ℤ × Cmd × Id))
               ∧ (↑(new_23_sig_newvote(Cmd) <z1, 0> msgval(e) new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, 0>;es.\000Ce';e)))
               ∧ (||fst(new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, 0>;es.e';e))|| (coeff flrs) ∈ ℤ)
               ∧ (d 0 ∈ ℤ)
               ∧ ((fst(poss-maj(cmdeq;[snd(fst(msgval(e))) 
                                         (fst(new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, 0>;es.e';e)))];snd(fst\000C(msgval(e))))))
                 ((coeff flrs) 1)
                 ∈ ℤ))
               ∧ (i loc(e) ∈ Id)
               ∧ auth ff
               ∧ ((k (fst(fst(fst(msgval(e))))) ∈ ℤ) ∧ (k1 ((snd(fst(fst(msgval(e))))) 1) ∈ ℤ))
               ∧ (v
                 (snd(poss-maj(cmdeq;[snd(fst(msgval(e))) 
                                        (fst(new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, 0>;es.e';e)))];snd(fst(\000Cmsgval(e))))))
                 ∈ Cmd))
               ∨ (∃e1:{e1:E| e1 ≤loc 
                   ∃z6:ℤ
                    ∃z7:Cmd
                     (new_23_sig_NewRoundsStateFun(Cmd;notify;propose;f;z1;es.e';e1) < z6
                     ∧ (((header(e1) ``new_23_sig retry`` ∈ Name)
                       ∧ has-es-info-type(es;e1;f;ℤ × ℤ × Cmd)
                       ∧ (<<z1, z6>z7> msgval(e1) ∈ (ℤ × ℤ × Cmd)))
                       ∨ ((header(e1) ``new_23_sig vote`` ∈ Name)
                         ∧ has-es-info-type(es;e1;f;ℤ × ℤ × Cmd × Id)
                         ∧ (<<z1, z6>z7> (fst(msgval(e1))) ∈ (ℤ × ℤ × Cmd))))
                     ∧ (no new_23_sig_Quorum(Cmd;cmdeq;coeff;flrs;notify;propose;reps;f) <z1, z6> between e1 and e)
                     ∧ ((header(e) ``new_23_sig vote`` ∈ Name) ∧ has-es-info-type(es;e;f;ℤ × ℤ × Cmd × Id))
                     ∧ (↑(new_23_sig_newvote(Cmd) <z1, z6> msgval(e) new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1,\000C z6>;es.e1;e)))
                     ∧ (||fst(new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, z6>;es.e1;e))|| (coeff flrs) ∈ ℤ)
                     ∧ (d 0 ∈ ℤ)
                     ∧ ((fst(poss-maj(cmdeq;[snd(fst(msgval(e))) 
                                               (fst(new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, z6>;es.e1;e)))];\000Csnd(fst(msgval(e))))))
                       ((coeff flrs) 1)
                       ∈ ℤ))
                     ∧ (i loc(e) ∈ Id)
                     ∧ auth ff
                     ∧ ((k (fst(fst(fst(msgval(e))))) ∈ ℤ) ∧ (k1 ((snd(fst(fst(msgval(e))))) 1) ∈ ℤ))
                     ∧ (v
                       (snd(poss-maj(cmdeq;[snd(fst(msgval(e))) 
                                              (fst(new_23_sig_QuorumStateFun(Cmd;notify;propose;f;<z1, z6>;es.e1;e)))];s\000Cnd(fst(msgval(e))))))
                       ∈ Cmd)))))))


Proof




Definitions occuring in Statement :  new_23_sig_main: new_23_sig_main() new_23_sig_ReplicaStateFun: new_23_sig_ReplicaStateFun(Cmd;notify;propose;slots;f;es;e) new_23_sig_Notify: new_23_sig_Notify(Cmd;clients;notify;propose;f) new_23_sig_NewRoundsStateFun: new_23_sig_NewRoundsStateFun(Cmd;notify;propose;f;x;es;e) new_23_sig_Quorum: new_23_sig_Quorum(Cmd;cmdeq;coeff;flrs;notify;propose;reps;f) new_23_sig_QuorumStateFun: new_23_sig_QuorumStateFun(Cmd;notify;propose;f;x;es;e) new_23_sig_newvote: new_23_sig_newvote(Cmd) new_23_sig_headers_type: new_23_sig_headers_type{i:l}(Cmd;notify;propose) msg-interface: Interface mk-msg: mk-msg(auth;hdr;val) es-info-body: msgval(e) has-es-info-type: has-es-info-type(es;e;f;T) es-header: header(e) Message: Message(f) no-classrel-in-interval: (no between start and e) classrel: v ∈ X(e) eo-forward: eo.e event-ordering+: EO+(Info) es-le: e ≤loc e'  es-loc: loc(e) es-E: E Id: Id name: Name poss-maj: poss-maj(eq;L;x) deq: EqDecider(T) length: ||as|| cons: [a b] nil: [] list: List valueall-type: valueall-type(T) assert: b bfalse: ff bool: 𝔹 less_than: a < b uall: [x:A]. B[x] pi1: fst(t) pi2: snd(t) exists: x:A. B[x] iff: ⇐⇒ Q not: ¬A squash: T or: P ∨ Q and: P ∧ Q set: {x:A| B[x]}  apply: a pair: <a, b> product: x:A × B[x] multiply: m add: m natural_number: $n int: token: "$token" atom: Atom universe: Type equal: t ∈ T bag-member: x ↓∈ bs bag: bag(T) set-sig-member: set-sig-member(s) set-sig: set-sig{i:l}(Item)
Lemmas :  sq_stable__and equal_wf vatype_wf cons_wf_listp cons_wf nil_wf listp_wf sq_stable__equal squash_wf int_seg_wf length_wf name_wf new_23_sig_headers_wf l_all_iff l_member_wf new_23_sig_headers_fun_wf cons_member equal-wf-base list_subtype_base atom_subtype_base iff_weakening_equal name_eq_wf eqtt_to_assert assert-name_eq sq_stable__no_repeats true_wf eqff_to_assert bool_wf bool_cases_sqequal subtype_base_sq bool_subtype_base assert-bnot classrel_wf msg-interface_wf new_23_sig_main_wf make-msg-interface_wf mk-msg_wf subtype_rel_weakening ext-eq_weakening bag-member_wf es-loc_wf event-ordering+_subtype exists_wf es-E_wf es-le_wf or_wf equal-wf-T-base es-header_wf has-es-info-type_wf es-info-body_wf equal-wf-base-T int_subtype_base not_wf assert_wf set-sig-member_wf new_23_sig_ReplicaStateFun_wf no-classrel-in-interval_wf new_23_sig_Notify_wf new_23_sig_Quorum_wf new_23_sig_newvote_wf new_23_sig_QuorumStateFun_wf eo-forward_wf member-eo-forward-E list_wf poss-maj_wf nat_wf es-info-type_wf pi1_wf_top top_wf subtype_rel_product subtype_top subtype_rel_transitivity eo-forward-E-subtype less_than_wf new_23_sig_NewRoundsStateFun_wf event-ordering+_wf Message_wf subtype_rel_dep_function new_23_sig_headers_type_wf set-sig_wf deq_wf bag_wf Id_wf set_wf valueall-type_wf new_23_sig-ilf eo-forward-header eo-forward-has-es-info-type make-Msg_wf eo-forward-info-body eclass0_wf new_23_sig_decided'base_wf new_23_sig_decision_wf msg-header_wf hdrmkmsg_lemma hdrmakeMsg_lemma false_wf and_wf make-Msg-as-mk-msg mk-msg-equal bfalse_wf subtype_rel_set eo-forward-loc equal_functionality_wrt_subtype_rel2

Latex:
\mforall{}[Cmd:\{T:Type|  valueall-type(T)\}  ].  \mforall{}[clients:bag(Id)].  \mforall{}[cmdeq:EqDecider(Cmd)].  \mforall{}[coeff,flrs:\mBbbZ{}].
\mforall{}[notify,propose:Atom  List].  \mforall{}[reps:bag(Id)].  \mforall{}[slots:set-sig\{i:l\}(\mBbbZ{})].
\mforall{}[f:new\_23\_sig\_headers\_type\{i:l\}(Cmd;notify;propose)].  \mforall{}[es:EO+(Message(f))].  \mforall{}[e:E].  \mforall{}[d:\mBbbZ{}].
\mforall{}[i:Id].  \mforall{}[auth:\mBbbB{}].  \mforall{}[k,k1:\mBbbZ{}].  \mforall{}[v:Cmd].
    (<d,  i,  mk-msg(auth;``new\_23\_sig  retry``;<<k,  k1>,  v>)>  \mmember{}  new\_23\_sig\_main()(e)
    \mLeftarrow{}{}\mRightarrow{}  loc(e)  \mdownarrow{}\mmember{}  reps
            \mwedge{}  (\mdownarrow{}\mexists{}e':\{e':E|  e'  \mleq{}loc  e  \} 
                      \mexists{}z1:\mBbbZ{}
                        \mexists{}z2:Cmd
                          (((((header(e')  =  propose)
                            \mwedge{}  has-es-info-type(es;e';f;\mBbbZ{}  \mtimes{}  Cmd)
                            \mwedge{}  (<z1,  z2>  =  msgval(e')))
                            \mvee{}  ((header(e')  =  ``new\_23\_sig  vote``)
                                \mwedge{}  has-es-info-type(es;e';f;\mBbbZ{}  \mtimes{}  \mBbbZ{}  \mtimes{}  Cmd  \mtimes{}  Id)
                                \mwedge{}  (z1  =  (fst(fst(fst(msgval(e'))))))
                                \mwedge{}  (z2  =  (snd(fst(msgval(e')))))))
                            \mwedge{}  (\mneg{}\muparrow{}(set-sig-member(slots)  z1 
                                        new\_23\_sig\_ReplicaStateFun(Cmd;notify;propose;slots;f;es;e'))))
                          \mwedge{}  (no  new\_23\_sig\_Notify(Cmd;clients;notify;propose;f)  z1  between  e'  and  e)
                          \mwedge{}  (((no  new\_23\_sig\_Quorum(Cmd;cmdeq;coeff;flrs;notify;propose;reps;f)  <z1,  0>  between  e\000C'  and  e)
                              \mwedge{}  ((header(e)  =  ``new\_23\_sig  vote``)  \mwedge{}  has-es-info-type(es;e;f;\mBbbZ{}  \mtimes{}  \mBbbZ{}  \mtimes{}  Cmd  \mtimes{}  Id))
                              \mwedge{}  (\muparrow{}(new\_23\_sig\_newvote(Cmd)  <z1,  0>  msgval(e)  new\_23\_sig\_QuorumStateFun(Cmd;notify;p\000Cropose;f;<z1,  0>es.e';e)))
                              \mwedge{}  (||fst(new\_23\_sig\_QuorumStateFun(Cmd;notify;propose;f;<z1,  0>es.e';e))||  =  (coeff  \000C*  flrs))
                              \mwedge{}  (d  =  0)
                              \mwedge{}  (\mneg{}((fst(poss-maj(cmdeq;[snd(fst(msgval(e)))  / 
                                                                                  (fst(new\_23\_sig\_QuorumStateFun(Cmd;notify;propose;f;<z1,  0>\000C;es.e';e)))];snd(fst(msgval(e))))))
                                  =  ((coeff  *  flrs)  +  1)))
                              \mwedge{}  (i  =  loc(e))
                              \mwedge{}  auth  =  ff
                              \mwedge{}  ((k  =  (fst(fst(fst(msgval(e))))))  \mwedge{}  (k1  =  ((snd(fst(fst(msgval(e)))))  +  1)))
                              \mwedge{}  (v
                                  =  (snd(poss-maj(cmdeq;[snd(fst(msgval(e)))  / 
                                                                                (fst(new\_23\_sig\_QuorumStateFun(Cmd;notify;propose;f;<z1,  0>\000Ces.e';e)))];snd(fst(msgval(e))))))))
                              \mvee{}  (\mexists{}e1:\{e1:E|  e1  \mleq{}loc  e  \} 
                                      \mexists{}z6:\mBbbZ{}
                                        \mexists{}z7:Cmd
                                          (new\_23\_sig\_NewRoundsStateFun(Cmd;notify;propose;f;z1;es.e';e1)  <  z6
                                          \mwedge{}  (((header(e1)  =  ``new\_23\_sig  retry``)
                                              \mwedge{}  has-es-info-type(es;e1;f;\mBbbZ{}  \mtimes{}  \mBbbZ{}  \mtimes{}  Cmd)
                                              \mwedge{}  (<<z1,  z6>,  z7>  =  msgval(e1)))
                                              \mvee{}  ((header(e1)  =  ``new\_23\_sig  vote``)
                                                  \mwedge{}  has-es-info-type(es;e1;f;\mBbbZ{}  \mtimes{}  \mBbbZ{}  \mtimes{}  Cmd  \mtimes{}  Id)
                                                  \mwedge{}  (<<z1,  z6>,  z7>  =  (fst(msgval(e1))))))
                                          \mwedge{}  (no  new\_23\_sig\_Quorum(Cmd;cmdeq;coeff;flrs;notify;propose;reps;f)  <z1,  z6>  be\000Ctween  e1  and  e)
                                          \mwedge{}  ((header(e)  =  ``new\_23\_sig  vote``)
                                              \mwedge{}  has-es-info-type(es;e;f;\mBbbZ{}  \mtimes{}  \mBbbZ{}  \mtimes{}  Cmd  \mtimes{}  Id))
                                          \mwedge{}  (\muparrow{}(new\_23\_sig\_newvote(Cmd)  <z1,  z6>  msgval(e)  new\_23\_sig\_QuorumStateFun(Cmd;n\000Cotify;propose;f;<z1,  z6>es.e1;e)))
                                          \mwedge{}  (||fst(new\_23\_sig\_QuorumStateFun(Cmd;notify;propose;f;<z1,  z6>es.e1;e))||  =  \000C(coeff  *  flrs))
                                          \mwedge{}  (d  =  0)
                                          \mwedge{}  (\mneg{}((fst(poss-maj(cmdeq;[snd(fst(msgval(e)))  / 
                                                                                              (fst(new\_23\_sig\_QuorumStateFun(Cmd;notify;...;f;<z1
                                                                                                                                                                                              ,  z6
                                                                                                                                                                                              >es.\000Ce1;e)))];snd(fst(msgval(e))))))
                                              =  ((coeff  *  flrs)  +  1)))
                                          \mwedge{}  (i  =  loc(e))
                                          \mwedge{}  auth  =  ff
                                          \mwedge{}  ((k  =  (fst(fst(fst(msgval(e))))))  \mwedge{}  (k1  =  ((snd(fst(fst(msgval(e)))))  +  1)))
                                          \mwedge{}  (v
                                              =  (snd(poss-maj(cmdeq;[snd(fst(msgval(e)))  / 
                                                                                            (fst(new\_23\_sig\_QuorumStateFun(Cmd;notify;...;f;<z1
                                                                                                                                                                                            ,  z6
                                                                                                                                                                                            >es.e\000C1;e)))];snd(fst(msgval(e)))))))))))))



Date html generated: 2015_07_23-PM-03_56_04
Last ObjectModification: 2015_02_04-PM-03_41_41

Home Index