Nuprl Lemma : rsc4_quorum_invariant
es:EO'. e1:E. Cmd:ValueAllType. n,round:
. p:Cmd List 
(Id List).
(p 
rsc4_QuorumState(Cmd) <n, round>(e1)
let cmds,locs = p
in no_repeats(Id;locs)
(||locs|| = ||cmds||)
(i:
||locs||. (
e:E. ((e <loc e1) <<<n, round>, cmds[i]>, locs[i]> rsc4_vote'base(Cmd)(e)))))
Proof
Definitions occuring in Statement :
rsc4_QuorumState: rsc4_QuorumState(Cmd),
rsc4_vote'base: rsc4_vote'base(Cmd),
Message: Message,
classrel: v X(e),
event-ordering+: EO+(Info),
es-locl: (e <loc e'),
es-E: E,
Id: Id,
select: l[i],
length: ||as||,
int_seg: {i..j
},
all: x:A. B[x],
exists: x:A. B[x],
squash: T,
implies: P Q,
and: P Q,
apply: f a,
spread: spread def,
pair: <a, b>,
product: x:A B[x],
list: type List,
natural_number: $n,
int: ,
equal: s = t,
no_repeats: no_repeats(T;l),
vatype: ValueAllType
Definitions :
lt_int: i <z j,
le_int: i 
z j,
rev_implies: P 
Q,
bfalse: ff,
iff: P Q,
bnot: 
b,
band: p q,
ycomb: Y,
btrue: tt,
rsc4_addvote: rsc4_addvote(Cmd),
ifthenelse: if b then t else f fi ,
top: Top,
true: True,
false: False,
not: A,
lelt: i j < k,
le: A B,
cand: A c B,
so_lambda: 
x.t[x],
member: t T,
prop: 
,
rsc4_init: rsc4_init(),
rsc4_add_to_quorum: rsc4_add_to_quorum(Cmd),
select: l[i],
exists: x:A. B[x],
squash: T,
int_seg: {i..j},
length: ||as||,
and: P Q,
implies: P Q,
vatype: ValueAllType,
all: x:A. B[x],
sq_type: SQType(T),
guard: {T},
deq: EqDecider(T),
uiff: uiff(P;Q),
unit: Unit,
bool: 
,
rsc4_newvote: rsc4_newvote(Cmd),
or: P 
Q,
decidable: Dec(P),
uimplies: b supposing a,
so_apply: x[s],
sq_stable: SqStable(P),
uall: [x:A]. B[x],
rsc4_QuorumState: rsc4_QuorumState(Cmd),
it: 
,
subtype: S 
T
Lemmas :
select_cons_tl,
product_subtype_base,
lelt_wf,
event-ordering+_wf,
rsc4_QuorumState_wf,
single-bag_wf,
bag-member_wf,
no_repeats_nil,
bag-member-single,
int_seg_wf,
int_subtype_base,
subtype_base_sq,
assert-deq,
assert-deq-member,
not_functionality_wrt_iff,
and_functionality_wrt_iff,
assert_of_band,
iff_weakening_uiff,
l_member_wf,
id-deq_wf,
deq-member_wf,
bfalse_wf,
assert_of_bnot,
eqff_to_assert,
not_wf,
bnot_wf,
uiff_transitivity,
deq_wf,
int-deq_wf,
product-deq_wf,
assert_wf,
iff_transitivity,
no_repeats_cons,
eqtt_to_assert,
bool_wf,
rsc4_newvote_wf,
equal_wf,
sq_stable_and_left_false,
sq_stable__squash,
sq_stable__all,
sq_stable__equal,
all_wf,
decidable__equal_int,
sq_stable__no_repeats,
sq_stable__and,
decidable__equal_Id,
decidable__no_repeats,
valueall-type_wf,
sq_stable__valueall-type,
bag_wf,
rsc4_init_wf,
rsc4_add_to_quorum_wf,
select_wf,
rsc4_vote'base_wf,
classrel_wf,
es-locl_wf,
and_wf,
event-ordering+_inc,
es-E_wf,
exists_wf,
squash_wf,
length_wf,
no_repeats_wf,
Id_wf,
Message_wf,
Memory-class-invariant
\mforall{}es:EO'. \mforall{}e1:E. \mforall{}Cmd:ValueAllType. \mforall{}n,round:\mBbbZ{}. \mforall{}p:Cmd List \mtimes{} (Id List).
(p \mmember{} rsc4\_QuorumState(Cmd) <n, round>(e1)
{}\mRightarrow{} let cmds,locs = p
in no\_repeats(Id;locs)
\mwedge{} (||locs|| = ||cmds||)
\mwedge{} (\mforall{}i:\mBbbN{}||locs||
(\mdownarrow{}\mexists{}e:E. ((e <loc e1) \mwedge{} <<<n, round>, cmds[i]>, locs[i]> \mmember{} rsc4\_vote'base(Cmd)(e)))))
Date html generated:
2012_02_20-PM-04_58_51
Last ObjectModification:
2012_02_02-PM-03_38_48
Home
Index