| COM | sci_inv9_1 | ---- Putting together Lemma 9 ---------------------------- |
| THM | lemma9 | n: . inv{}(sci_program{}(n); s.inv9abc(n;s)) |
| THM | lemma9a1_ | n: . inv{}(sci_program{}(n); s.inv9a1_(s)) |
| THM | lemma9c2 | n: . inv{}(sci_program{}(n); s.inv9c2(s)) |
| THM | lemma9a3_ | n: . inv{}(sci_program{}(n); s.inv9a3_(s)) |
| THM | lemma9a4_ | n: . inv{}(sci_program{}(n); s.inv9a4_(s)) |
| THM | lemma9c5 | n: . inv{}(sci_program{}(n); s.inv9c5(s)) |
| THM | lemma9b1_ | n: . inv{}(sci_program{}(n); s.( p:P. inv9b1_(n;s;p))) |
| THM | lemma9b2 | n: . inv{}(sci_program{}(n); s.( p:P. inv9b2(n;s;p))) |
| THM | lemma9b3 | n: . inv{}(sci_program{}(n); s.( p:P. inv9b3(n;s;p))) |
| THM | lemma9b4_ | n: . inv{}(sci_program{}(n); s.( p:P. inv9b4_(n;s;p))) |
| THM | lemma9b5 | n: . inv{}(sci_program{}(n); s.( p:P. inv9b5(n;s;p))) |
| THM | lemma9b6 | n: . inv{}(sci_program{}(n); s.( p:P. inv9b6(n;s;p))) |
| THM | lemma9b7 | n: . inv{}(sci_program{}(n); s.( p:P. inv9b7(n;s;p))) |
| THM | lemma9b8 | n: . inv{}(sci_program{}(n); s.( p:P. inv9b8(n;s;p))) |
| COM | sci_inv9_2 | ---- Old alternate versions still used ------------------- |
| THM | lemma9a1 | n: . inv{}(sci_program{}(n); s.inv9a1(n;s)) |
| THM | lemma9a2_ | n: . inv{}(sci_program{}(n); s.inv9a2_(s)) |
| THM | lemma9a2 | n: . inv{}(sci_program{}(n); s.inv9a2(n;s)) |
| THM | lemma9a3 | n: . inv{}(sci_program{}(n); s.inv9a3(n;s)) |
| THM | lemma9a4 | n: . inv{}(sci_program{}(n); s.inv9a4(n;s)) |
| THM | lemma9a5_ | n: . inv{}(sci_program{}(n); s.inv9a5_(s)) |
| THM | lemma9a5 | n: . inv{}(sci_program{}(n); s.inv9a5(n;s)) |
| THM | lemma9b1 | n: . inv{}(sci_program{}(n); s.( p:P. inv9b1(n;s;p))) |
| THM | lemma9b4 | n: . inv{}(sci_program{}(n); s.( p:P. inv9b4(n;s;p))) |
| COM | sci_inv9_3 | ---- Some immediate consequences ------------------------- |
| THM | inv9a_single_query | n:
inv{}(sci_program{}(n);
s.( p,q,r,Q1,Q2: . args1,args2: List.
query(Q1)
 query(Q2)
 (Q1 = Q2)
 Q1(p::args1) buf[q]_
 (Q2(p::args2) buf[r]_))) |
| THM | inv9a5_single_response | n:
inv{}(sci_program{}(n);
s.( p,R1,R2: . args1,args2: List.
response(R1)
 response(R2)
 (R1 = R2)
 R1(args1) buf[p]_
 (R2(args2) buf[p]_))) |
| THM | one_outstanding_mesg | n:
inv{}(sci_program{}(n);
s.( p:P. Q1,Q2: .
outstanding_mesg(n;s;Q1;p)
 (Q1 = Q2)
 outstanding_mesg(n;s;Q2;p))) |
| COM | sci_inv9_4 | ---- Converse of 9b Lemmas ------------------------------- |
| DISP | inv9b2_converse_df | inv9b2_converse(<n:n:*><s:s:*><p:p:*>)
== inv9b2_converse(<n><s><p>) |
| ABS | inv9b2_converse | inv9b2_converse(n;s;p) ==
outstanding_mesg(n;s;read_cache_freshQ;p)
outstanding_mesg(n;s;read_cache_goneQ;p)
 status-p_ = Pending |
| THM | inv9b2_converse_wf | n: . s:state. p:PId. inv9b2_converse(n;s;p)   |
| DISP | inv9b3_converse_df | inv9b3_converse(<n:n:*><s:s:*><p:p:*>)
== inv9b3_converse(<n><s><p>) |
| ABS | inv9b3_converse | inv9b3_converse(n;s;p) ==
outstanding_mesg(n;s;prependQ;p)  status-p_ = Inqueue |
| THM | inv9b3_converse_wf | n: . s:state. p:PId. inv9b3_converse(n;s;p)   |
| DISP | inv9b4_converse_df | inv9b4_converse(<n:n:*><s:s:*><p:p:*>)
== inv9b4_converse(<n><s><p>) |
| ABS | inv9b4_converse | inv9b4_converse(n;s;p) ==
outstanding_mesg(n;s;delrightQ;p)  status-p_ = Delright |
| THM | inv9b4_converse_wf | n: . s:state. p:PId. inv9b4_converse(n;s;p)   |
| DISP | inv9b5_converse_df | inv9b5_converse(<n:n:*><s:s:*><p:p:*>)
== inv9b5_converse(<n><s><p>) |
| ABS | inv9b5_converse | inv9b5_converse(n;s;p) ==
outstanding_mesg(n;s;delleftQ;p)  status-p_ = Delleft |
| THM | inv9b5_converse_wf | n: . s:state. p:PId. inv9b5_converse(n;s;p)   |
| DISP | inv9b6_converse_df | inv9b6_converse(<n:n:*><s:s:*><p:p:*>)
== inv9b6_converse(<n><s><p>) |
| ABS | inv9b6_converse | inv9b6_converse(n;s;p) ==
outstanding_mesg(n;s;delrightQ;p)  status-p_ = Delright |
| THM | inv9b6_converse_wf | n: . s:state. p:PId. inv9b6_converse(n;s;p)   |
| DISP | inv9b7_converse_df | inv9b7_converse(<n:n:*><s:s:*><p:p:*>)
== inv9b7_converse(<n><s><p>) |
| ABS | inv9b7_converse | inv9b7_converse(n;s;p) ==
outstanding_mesg(n;s;purgeQ;p)  status-p_ = Purging |
| THM | inv9b7_converse_wf | n: . s:state. p:PId. inv9b7_converse(n;s;p)   |
| DISP | inv9b8_converse_df | inv9b8_converse(<n:n:*><s:s:*><p:p:*>)
== inv9b8_converse(<n><s><p>) |
| ABS | inv9b8_converse | inv9b8_converse(n;s;p) ==
outstanding_mesg(n;s;modifydataQ;p)  status-p_ = Ftod |
| THM | inv9b8_converse_wf | n: . s:state. p:PId. inv9b8_converse(n;s;p)   |
| THM | lemma9b2_converse_ | n: . inv{}(sci_program{}(n); s.( p:P. inv9b2_converse(n;s;p))) |
| THM | lemma9b2_converse | n: . s:state. p:P.
inv{}(sci_program{}(n); s.inv9b2_converse(n;s;p)) |
| THM | lemma9b3_converse | n: . inv{}(sci_program{}(n); s.( p:P. inv9b3_converse(n;s;p))) |
| THM | lemma9b5_converse | n: . inv{}(sci_program{}(n); s.( p:P. inv9b5_converse(n;s;p))) |
| THM | lemma9b6_converse | n: . inv{}(sci_program{}(n); s.( p:P. inv9b6_converse(n;s;p))) |
| THM | lemma9b7_converse | n: . inv{}(sci_program{}(n); s.( p:P. inv9b7_converse(n;s;p))) |
| THM | lemma9b8_converse | n: . inv{}(sci_program{}(n); s.( p:P. inv9b8_converse(n;s;p))) |
| THM | lemma9b4_converse | n: . inv{}(sci_program{}(n); s.( p:P. inv9b4_converse(n;s;p))) |
| COM | sci_inv9_5 | ---- Some consequences introduced by Amy ----------------- |
| THM | inv9a_single_non_rw_query | n:
inv{}(sci_program{}(n);
s.( p,q,msgQ: . args: List.
query(msgQ)
 (msgQ = read_cache_freshQ)
 (msgQ = read_cache_goneQ)
 list_el(mesg;msgQ(p::args);buf[q]_)
 list_el(mesg;read_cache_freshQ(p::[]);buf[m]_)
list_el(mesg;read_cache_goneQ(p::[]);buf[m]_))) |
| THM | inv9b4_non_rw_query | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Inlist
 list_el(mesg;read_cache_freshQ(p::[]);buf[m]_)
list_el(mesg;read_cache_goneQ(p::[]);buf[m]_))) |
| THM | inv9b4_no_delleftr | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Inlist
 ( qq:
list_el(mesg;delleftR(qq::ok{}::[]);buf[p]_)))) |
| THM | inv9a5_next_mesg_response | n:
inv{}(sci_program{}(n);
s.( p:P
response(next_mesg(p;s.h).type)
 (next_mesg(p;s.h).type = delleftR)
 ( qq:
list_el(mesg;delleftR(qq::ok{}::[]);buf[p]_)))) |
| THM | inv9a4_next_mesg_response | n:
inv{}(sci_program{}(n);
s.( p:P
response(next_mesg(p;s.h).type)
 list_el(mesg;read_cache_freshQ(p::[]);buf[m]_)
list_el(mesg;read_cache_goneQ(p::[]);buf[m]_))) |
| THM | inbuf_status_rc_freshq | n:
inv{}(sci_program{}(n);
s.( p:P+m. q:P. args: List.
read_cache_freshQ(q::args) buf[p]_
 status-q_ = Pending)) |
| THM | inbuf_status_rc_goneq | n:
inv{}(sci_program{}(n);
s.( p:P+m. q:P. args: List.
read_cache_goneQ(q::args) buf[p]_
 status-q_ = Pending)) |
| THM | inbuf_status_prependq | n:
inv{}(sci_program{}(n);
s.( p,q:P. args: List.
prependQ(q::args) buf[p]_  status-q_ = Inqueue)) |
| THM | inbuf_status_delleftq | n:
inv{}(sci_program{}(n);
s.( p:P+m. q:P. args: List.
delleftQ(q::args) buf[p]_  status-q_ = Delleft)) |
| THM | inbuf_status_delrightq | n:
inv{}(sci_program{}(n);
s.( p,q:P. args: List.
delrightQ(q::args) buf[p]_  status-q_ = Delright)) |
| THM | inbuf_status_purgeq | n:
inv{}(sci_program{}(n);
s.( p,q:P. args: List.
purgeQ(q::args) buf[p]_  status-q_ = Purging)) |
| THM | inbuf_status_mdataq | n:
inv{}(sci_program{}(n);
s.( p:P+m. q:P. args: List.
modifydataQ(q::args) buf[p]_  status-q_ = Ftod)) |
| THM | inbuf_status_pending_R | n:
inv{}(sci_program{}(n);
s.( p:P. args: List.
read_cache_freshR(args) buf[p]_
read_cache_goneR(args) buf[p]_
 status-p_ = Pending)) |
| THM | inbuf_status_inqueue_R | n:
inv{}(sci_program{}(n);
s.( p:P. args: List.
prependR(args) buf[p]_  status-p_ = Inqueue)) |
| THM | inbuf_status_delleft_R | n:
inv{}(sci_program{}(n);
s.( p:P. args: List.
delleftR(args) buf[p]_  status-p_ = Delleft)) |
| THM | inbuf_status_delright_R | n:
inv{}(sci_program{}(n);
s.( p:P. args: List.
delrightR(args) buf[p]_  status-p_ = Delright)) |
| THM | inbuf_status_purging_R | n:
inv{}(sci_program{}(n);
s.( p:P. args: List.
purgeR(args) buf[p]_  status-p_ = Purging)) |
| THM | inbuf_status_ftod_R | n:
inv{}(sci_program{}(n);
s.( p:P. args: List.
modifydataR(args) buf[p]_  status-p_ = Ftod)) |
| THM | next_mesg_status_rc_freshr | n:
inv{}(sci_program{}(n);
s.( p:P
next_mesg(p;s.h).type = read_cache_freshR
 status-p_ = Pending)) |
| THM | next_mesg_status_rc_goner | n:
inv{}(sci_program{}(n);
s.( p:P
next_mesg(p;s.h).type = read_cache_goneR
 status-p_ = Pending)) |
| THM | next_mesg_status_prependr | n:
inv{}(sci_program{}(n);
s.( p:P
next_mesg(p;s.h).type = prependR  status-p_ = Inqueue)) |
| THM | next_mesg_status_delleftr | n:
inv{}(sci_program{}(n);
s.( p:P
next_mesg(p;s.h).type = delleftR  status-p_ = Delleft)) |
| THM | next_mesg_status_delrightr | n:
inv{}(sci_program{}(n);
s.( p:P
next_mesg(p;s.h).type = delrightR
 status-p_ = Delright)) |
| THM | next_mesg_status_purger | n:
inv{}(sci_program{}(n);
s.( p:P
next_mesg(p;s.h).type = purgeR  status-p_ = Purging)) |
| THM | next_mesg_status_mdatar | n:
inv{}(sci_program{}(n);
s.( p:P
next_mesg(p;s.h).type = modifydataR  status-p_ = Ftod)) |
| THM | off_no_rw_query | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Off
 list_el(mesg;read_cache_freshQ(p::[]);buf[m]_)
list_el(mesg;read_cache_goneQ(p::[]);buf[m]_))) |
| THM | inqueue_no_rw_query | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Inqueue
 list_el(mesg;read_cache_freshQ(p::[]);buf[m]_)
list_el(mesg;read_cache_goneQ(p::[]);buf[m]_))) |
| THM | inlist_no_rw_query | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Inlist
 list_el(mesg;read_cache_freshQ(p::[]);buf[m]_)
list_el(mesg;read_cache_goneQ(p::[]);buf[m]_))) |
| THM | delleft_no_rw_query | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Delleft
 list_el(mesg;read_cache_freshQ(p::[]);buf[m]_)
list_el(mesg;read_cache_goneQ(p::[]);buf[m]_))) |
| THM | delright_no_rw_query | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Delright
 list_el(mesg;read_cache_freshQ(p::[]);buf[m]_)
list_el(mesg;read_cache_goneQ(p::[]);buf[m]_))) |
| THM | purging_no_rw_query | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Purging
 list_el(mesg;read_cache_freshQ(p::[]);buf[m]_)
list_el(mesg;read_cache_goneQ(p::[]);buf[m]_))) |
| THM | ftod_no_rw_query | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Ftod
 list_el(mesg;read_cache_freshQ(p::[]);buf[m]_)
list_el(mesg;read_cache_goneQ(p::[]);buf[m]_))) |
| THM | off_no_delleftr | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Off
 ( qq:
list_el(mesg;delleftR(qq::ok{}::[]);buf[p]_)))) |
| THM | pending_no_delleftr | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Pending
 ( qq:
list_el(mesg;delleftR(qq::ok{}::[]);buf[p]_)))) |
| THM | inqueue_no_delleftr | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Inqueue
 ( qq:
list_el(mesg;delleftR(qq::ok{}::[]);buf[p]_)))) |
| THM | inlist_no_delleftr | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Inlist
 ( qq:
list_el(mesg;delleftR(qq::ok{}::[]);buf[p]_)))) |
| THM | delright_no_delleftr | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Delright
 ( qq:
list_el(mesg;delleftR(qq::ok{}::[]);buf[p]_)))) |
| THM | purging_no_delleftr | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Purging
 ( qq:
list_el(mesg;delleftR(qq::ok{}::[]);buf[p]_)))) |
| THM | ftod_no_delleftr | n:
inv{}(sci_program{}(n);
s.( p:P
status-p_ = Ftod
 ( qq:
list_el(mesg;delleftR(qq::ok{}::[]);buf[p]_)))) |
| THM | idle_status | n:
inv{}(sci_program{}(n);
s.( p:P. idle(s;p)  status-p_ = Off status-p_ = Pending)) |
| THM | visiting_status | n:
inv{}(sci_program{}(n);
s.( p:P
visiting(s;p)
 status-p_ = Inlist
status-p_ = Delleft
status-p_ = Delright
status-p_ = Ftod
status-p_ = Purging)) |
| THM | next_mesg_only_query | n:
inv{}(sci_program{}(n);
s.( p,q,msgQ: . args,args': List.
query(msgQ)
 next_mesg(p;s.h) = msgQ(q::args)
 list_el(mesg;msgQ(q::args');but_last_el(buf[p]_)))) |
| COM | sci_inv9_6 | ---- Some consequences introduced by Frank --------------- |
| ABS | inv9a_f1 | inv9a_f1{}(n; s) ==
p,q,r:P+m. mesgQ,mesgQ': . arg,arg': List.
query(mesgQ)
 query(mesgQ')
 (mesgQ = mesgQ')
 list_el(mesg;mesgQ(p::arg);buf[q]_)
 list_el(mesg;mesgQ'(p::arg');buf[r]_) |
| THM | inv9a_f1_wf | n: . s:state. inv9a_f1{}(n; s)   |
| THM | lemma9a_f1 | n: . inv{}(sci_program{}(n); s.inv9a_f1{}(n; s)) |
| ABS | inv9a_f2 | inv9a_f2{}(n; s) ==
p:P+m. mesgR,mesgR': . arg,arg': List.
response(mesgR)
 response(mesgR')
 (mesgR = mesgR')
 list_el(mesg;mesgR(arg);buf[p]_)
 list_el(mesg;mesgR'(arg');buf[p]_) |
| THM | inv9a_f2_wf | n: . s:state. inv9a_f2{}(n; s)   |
| THM | lemma9a_f2 | n: . inv{}(sci_program{}(n); s.inv9a_f2{}(n; s)) |