Nuprl Lemma : Paxos-spec3-one-value-per-ballot

[Info:Type]. [es:EO+(Info)]. [T:Type]. [f:]. [VoteState:EClass(AcceptorState)]. [Proposal:EClass(  T)].
[leader:  Id].
  [e1,e2:E(Proposal)].  Proposal(e1) = Proposal(e2) supposing (fst(Proposal(e1))) = (fst(Proposal(e2))) 
  supposing e:E(Proposal)
              e is first@ leader (fst(Proposal(e))) s.t. 
               q.||filter(e'.(Reservation(VoteState(e')) = fst(Proposal(e)));(VoteState)(q))|| = (f + 1)


Proof not projected




Definitions occuring in Statement :  paxos-state-reservation: Reservation(s),  paxos-acceptor-state: AcceptorState,  es-interface-predecessors: (X)(e),  es-E-interface: E(X),  eclass-val: X(e),  eclass: EClass(A[eo; e]),  event-ordering+: EO+(Info),  es-first-at: e is first@ i s.t.  e.P[e],  Id: Id,  length: ||as||,  eq_int: (i = j),  nat: ,  uimplies: b supposing a,  uall: [x:A]. B[x],  pi1: fst(t),  all: x:A. B[x],  apply: f a,  lambda: x.A[x],  function: x:A  B[x],  product: x:A  B[x],  add: n + m,  natural_number: $n,  int: ,  universe: Type,  equal: s = t,  filter: filter(P;l)
Definitions :  axiom: Ax,  alle-lt: e<e'.P[e],  eq_id: a = b,  sqequal: s ~ t,  iff: P  Q,  so_apply: x[s],  or: P  Q,  append: as @ bs,  locl: locl(a),  Knd: Knd,  atom: Atom$n,  list: type List,  pair: <a, b>,  record: record(x.T[x]),  es-interface-val: val(X,e),  strong-subtype: strong-subtype(A;B),  ge: i  j ,  less_than: a < b,  uiff: uiff(P;Q),  intensional-universe: IType,  fpf: a:A fp-> B[a],  real: ,  grp_car: |g|,  l_member: (x  l),  and: P  Q,  es-loc: loc(e),  limited-type: LimitedType,  void: Void,  true: True,  guard: {T},  btrue: tt,  sq_type: SQType(T),  bool: ,  decide: case b of inl(x) => s[x] | inr(y) => t[y],  isl: isl(x),  can-apply: can-apply(f;x),  in-eclass: e  X,  assert: b,  natural_number: $n,  add: n + m,  es-interface-predecessors: (X)(e),  paxos-state-reservation: Reservation(s),  eq_int: (i = j),  filter: filter(P;l),  length: ||as||,  eclass-val: X(e),  pi1: fst(t),  prop: ,  implies: P  Q,  false: False,  not: A,  le: A  B,  es-E-interface: E(X),  int: ,  so_lambda: x.t[x],  es-first-at: e is first@ i s.t.  e.P[e],  uimplies: b supposing a,  Id: Id,  product: x:A  B[x],  union: left + right,  subtype: S  T,  subtype_rel: A r B,  atom: Atom,  apply: f a,  top: Top,  token: "$token",  ifthenelse: if b then t else f fi ,  record-select: r.x,  paxos-acceptor-state: AcceptorState,  event_ordering: EO,  es-E: E,  lambda: x.A[x],  set: {x:A| B[x]} ,  so_lambda: x y.t[x; y],  eclass: EClass(A[eo; e]),  nat: ,  dep-isect: Error :dep-isect,  eq_atom: x =a y,  eq_atom: eq_atom$n(x;y),  record+: record+,  all: x:A. B[x],  function: x:A  B[x],  isect: x:A. B[x],  uall: [x:A]. B[x],  universe: Type,  member: t  T,  event-ordering+: EO+(Info),  equal: s = t,  tactic: Error :tactic,  IdLnk: IdLnk,  sq_stable: SqStable(P),  rev_implies: P  Q,  exists: x:A. B[x],  so_apply: x[s1;s2],  squash: T,  MaAuto: Error :MaAuto,  CollapseTHEN: Error :CollapseTHEN,  Complete: Error :Complete,  CollapseTHENA: Error :CollapseTHENA,  it:
Lemmas :  es-first-at-unique,  int_subtype_base,  es-interface-subtype_rel2,  squash_wf,  member_wf,  eclass_wf,  in-eclass_wf,  assert_elim,  bool_wf,  bool_subtype_base,  subtype_base_sq,  assert_wf,  event-ordering+_wf,  event-ordering+_inc,  subtype_rel_self,  es-E_wf,  nat_wf,  top_wf,  eclass-val_wf,  pi1_wf_top,  Id_wf,  es-first-at_wf,  es-interface-top,  es-E-interface_wf,  paxos-acceptor-state_wf,  es-interface-predecessors_wf,  filter_wf,  length_wf1,  es-loc_wf,  eq_int_wf,  paxos-state-reservation_wf,  subtype_rel_wf,  intensional-universe_wf,  false_wf,  ifthenelse_wf,  true_wf,  event_ordering_wf,  length_wf_nat,  list-subtype,  l_member_wf,  filter_type,  uiff_inversion,  iff_weakening_uiff,  assert-eq-id,  nat_properties,  pi1_wf

\mforall{}[Info:Type].  \mforall{}[es:EO+(Info)].  \mforall{}[T:Type].  \mforall{}[f:\mBbbN{}].  \mforall{}[VoteState:EClass(AcceptorState)].
\mforall{}[Proposal:EClass(\mBbbN{}  \mtimes{}  T)].  \mforall{}[leader:\mBbbN{}  {}\mrightarrow{}  Id].
    \mforall{}[e1,e2:E(Proposal)].
        Proposal(e1)  =  Proposal(e2)  supposing  (fst(Proposal(e1)))  =  (fst(Proposal(e2))) 
    supposing  \mforall{}e:E(Proposal)
                            e  is  first@  leader  (fst(Proposal(e)))  s.t. 
                              q.||filter(\mlambda{}e'.(Reservation(VoteState(e'))  =\msubz{}  fst(Proposal(e)));\mleq{}(VoteState)(q))||
                            =  (f  +  1)


Date html generated: 2011_10_20-PM-04_29_27
Last ObjectModification: 2011_06_18-PM-01_57_07

Home Index