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