Nuprl Lemma : Paxos-spec6-VoteState-invariant
[Info:Type]
es:EO+(Info). failset:Id List.
[T:Type]
f:
. acceptors:Id List. Reserve,NoProposal,NewBallot:EClass(). VoteState:EClass(AcceptorState).
Proposal:EClass( 
T). AcceptOrReject:EClass( T 
). leader: 
Id. Decide,Input:EClass(T).
Vote:EClass(Id ). Collect:EClass( 
T).
(Paxos-spec6-body{i:l}(Info;es;T;f;acceptors;
Reserve;VoteState;Proposal;
AcceptOrReject;leader;Decide;
Vote;Input;Collect;NoProposal;
NewBallot;failset)
(vs:E(VoteState)
p:E(Proposal). ((p < vs) 
((fst(Proposal(p))) = Ballot(VoteState(vs))))
supposing 0 
Ballot(VoteState(vs))))
Proof not projected
Definitions occuring in Statement :
Paxos-spec6-body: Paxos-spec6-body,
paxos-state-ballot: Ballot(s),
paxos-acceptor-state: AcceptorState,
es-E-interface: E(X),
eclass-val: X(e),
eclass: EClass(A[eo; e]),
event-ordering+: EO+(Info),
es-causl: (e < e'),
Id: Id,
bool: ,
nat_plus: ,
nat: ,
uimplies: b supposing a,
uall: [x:A]. B[x],
pi1: fst(t),
le: A B,
all: x:A. B[x],
exists: x:A. B[x],
implies: P Q,
and: P Q,
function: x:A B[x],
product: x:A B[x],
list: type List,
natural_number: $n,
int: ,
universe: Type,
equal: s = t
Definitions :
uall: [x:A]. B[x],
all: x:A. B[x],
implies: P Q,
uimplies: b supposing a,
le: A B,
member: t 
T,
not: 
A,
false: False,
assert: 
b,
so_lambda: 
x y.t[x; y],
btrue: tt,
ifthenelse: if b then t else f fi ,
true: True,
paxos-state-ballot: Ballot(s),
paxos-state-reservation: Reservation(s),
paxos-state-name: Name(s),
paxos-state-info: Info(s),
and: P Q,
exists: x:A. B[x],
pi1: fst(t),
subtype: S 
T,
pi2: snd(t),
cand: A c B,
prop: 
,
top: Top,
so_lambda: x.t[x],
Paxos-spec6-body: Paxos-spec6-body,
es-E-interface: E(X),
so_apply: x[s1;s2],
sq_type: SQType(T),
guard: {T},
es-class-causal-rel-fail: es-class-causal-rel-fail,
MaxVote: MaxVote(es;T;Vote;e;s),
nat: ,
paxos-acceptor-state: AcceptorState,
so_apply: x[s],
es-class-causal-mrel-fail: es-class-causal-mrel-fail,
!hyp_hide: x
Lemmas :
paxos-state-ballot_wf,
eclass-val_wf,
paxos-acceptor-state_wf,
es-E_wf,
event-ordering+_inc,
event-ordering+_wf,
subtype_base_sq,
bool_wf,
bool_subtype_base,
le_wf,
es-E-interface_wf,
es-interface-top,
Paxos-spec6-body_wf,
nat_plus_inc,
eclass_wf,
nat_wf,
Id_wf,
nat_plus_wf,
assert_elim,
in-eclass_wf,
es-tagged-true-class_wf,
top_wf,
es-interface-subtype_rel2,
es-locl_wf,
pi1_wf_top,
nat_properties,
es-loc_wf,
es-causle_wf,
not_wf,
assert_wf,
pi2_wf,
tagged-true-subtype,
tagged-true-val,
es-causl_weakening,
es-causl_transitivity1,
es-causl_transitivity2,
es-causl_wf
\mforall{}[Info:Type]
\mforall{}es:EO+(Info). \mforall{}failset:Id List.
\mforall{}[T:Type]
\mforall{}f:\mBbbN{}\msupplus{}. \mforall{}acceptors:Id List. \mforall{}Reserve,NoProposal,NewBallot:EClass(\mBbbN{}).
\mforall{}VoteState:EClass(AcceptorState). \mforall{}Proposal:EClass(\mBbbN{} \mtimes{} T). \mforall{}AcceptOrReject:EClass(\mBbbN{} \mtimes{} T \mtimes{} \mBbbB{}).
\mforall{}leader:\mBbbN{} {}\mrightarrow{} Id. \mforall{}Decide,Input:EClass(T). \mforall{}Vote:EClass(Id \mtimes{} \mBbbN{} \mtimes{} \mBbbB{}).
\mforall{}Collect:EClass(\mBbbN{} \mtimes{} \mBbbZ{} \mtimes{} T).
(Paxos-spec6-body\{i:l\}(Info;es;T;f;acceptors;
Reserve;VoteState;Proposal;
AcceptOrReject;leader;Decide;
Vote;Input;Collect;NoProposal;
NewBallot;failset)
{}\mRightarrow{} (\mforall{}vs:E(VoteState)
\mexists{}p:E(Proposal). ((p < vs) \mwedge{} ((fst(Proposal(p))) = Ballot(VoteState(vs))))
supposing 0 \mleq{} Ballot(VoteState(vs))))
Date html generated:
2011_10_20-PM-04_34_18
Last ObjectModification:
2011_06_18-PM-02_02_06
Home
Index