From db79726d58a308d23acd6da7a33cf38392a48ec2 Mon Sep 17 00:00:00 2001 From: navid Date: Fri, 19 Sep 2008 00:09:13 +0000 Subject: [PATCH] *** empty log message *** --- Robust/Transactions/Notes/sysgurantees.dvi | Bin 27184 -> 20568 bytes Robust/Transactions/Notes/sysgurantees.tex | 68 +++++++++------------ 2 files changed, 28 insertions(+), 40 deletions(-) diff --git a/Robust/Transactions/Notes/sysgurantees.dvi b/Robust/Transactions/Notes/sysgurantees.dvi index 1eba1520f06bd2b699678040cb02059dc930be3c..1543b3d88d4336eca9419e9f23ebcea54fc0da37 100644 GIT binary patch delta 8741 zcma)C3vd*5nxCY5@{%_~f(GsqG$fD&5}t;a2@4TjNF>>C=(%fWrju!y=^na!^3Ywz zU5i>v$w>Rx*_QEC?tHGYDp90Sa4;0yF5F%zUUBR5$~}CYp1Znw)^6=`zwh5YlSyQ+ z&MK>5`v3Tzzwh^bf1Z6K@82KJ+dHpl`J!ca`Fy@StD*9_>$erJ{qpk5zNqZ-m3+C_ zSAyRQ0+H^4hD9g8Bljfp&wRh3E|sr-{$=@}ee;@f*O*GfqEj8R$=KQAn#*lTmu*wp zvG-twtlB-g7O~BcY#Xv^4_{WYCNECMSp|J38|za32Y-L6EtarBnE}>Jk=-y55$~xbUFJDM%FtLBg zs`vT&b;XqVqNMo#o!+{*drwMy|1L<%3`q$xQ?tA25N5bH+qz7*24sUNJq+Rx+THs$ zy{nlarbTU8uk$XDOgSl>xlL1PO-eWuH>8NnCWPgnYy@;AYHE7D2#p8d=Rl#5o%R8ThONtvxO)VvEnEBU5BnuC+?)$iiFbE@a$h1>a=^M0+ z$hM+tP%<8rS@Y)acsJlI6>;lddQ zM!E0;83kq?bz(}ma5^BVOjE;y%#aaH(107uU=a!8cO$k2ZMLT3vQi@{Jl5lRjp?%M zwE6`5#l$TQk4(IOU-nwdfA(LNAmXMrom!_wB8r*xuXu5zYM7F0k~b{>io>jKQn_3> zyc+>F#=?}>&Q%p$}x)7 zTLtGoZpM~-*fW#L;)nM+ijfIG&t92*N#XOElF1Y<;J$+uCQF+`59K{_%W)-P3BflV z_$RLg!3oh_Ln%F$@Oi0X!U_}RfQiV(|CO%UDq%M_db;gF*OZC<^LdWs8XnRg`9R^p zOhIf68m1g!n$FnZ55m zFJkReOXEdXmN@ROM!i+EV9h!nRbE&i3rs>=rfMcLqG81}B{-(mI}-sKfJ+W+Q_Pfb z;07tmQ%uqgf;*m@tdO_%D>FO(%m9(7=Ol{Nzk#(auCM~hw6t-RA+BR)@*w8q-Xj>L0}Ancgj2v>dc*(tZ+ zG6?~G-Ih%;!(P$qCaR7-{6z%$q;6n31LU$IX?cY|7)Kh%0ac=SxQp!#i(r4<3>mjW9h<4NaE+mdhRDmBJr(FXu%J ze_<<-ctIrq(Oq3&5G_h-y6nziL<^t?qqv4DF(h@yoUqA>-%6}k>B9%gi4*@xJ^}`k z5h)Pa)T-%4Jp;~aOIY2{YO8K+rA4Eec;dI*fKtW~`e%~4l8NsU;yHOZHHX*>22AHpIwJg>@)Xn$4fRdtqlOP813 zVVvM{?UZ=nd>e5^k9vdgq56YfiwA}~WX9v0Wk9cB_tA|ij@c?DaaJb!$+Vg3mtjbp z##=&5g`a0XySu53g{v1$6uK5llmLTCd}B{m&xy0Btr-drKbLi6^vUMd(E~9RM8rr5 zN1sMGNeCz-7WOzM>S_SRJVe~J))Gc`!N4w$4@rz-H7OiD00AXbv2hfWU&OAfY0Sjr zWp_3o9+)dAt$3&6JsOq>$VJx{?tu1B$3sef{OE4BYyPaV zjKLL76~1!hKH3VJa&Ug@T(LL-i)Nb<1zdZ>_Y6}3MIiFCp)0zV%~~+0%$Af0ksO3w zGzKyq4x zd4tdoTlzhu4Fx-M2JOd2C5D3!f1t}Q-cJJvQWSw0J#739oLX6Y7^Pg?k*&d8UyTcj_kx^ z$Dw<+b!-j;i(C82%|h#d9s?=>Orv2Av^G3VFa|E%EkQPPs9bc3s9}^#!#hX#ossW6 zGdGePRcvuBYvW{@_8>k?fJ#3@gab+0AZN`6x>~Lz&aEJ^JOJe{pSTjr#YRN)(-Mi%<{#ryq?To3M(?|K_4F{mlcM z8^{Bk^HaU@q;`{umq0$rAO@I2R8>A{0qbBNE~LtAy^CIU!THTg2CEl?I(8X`dy-Ykl z1DD0USsd7PS{?wMHhA-eg<%x5N4vQ~0=WC_jhkq`C|YJ;UNyvg*YxnydT&!PTSJtdMB<@2KHtzizW3HG zW;d={m|qujYb>{QQoOMnWC;vPyixM#ieZ3c644yh2_cAL{YtP!^Jd;;^ha!8eOi*5(lra zohVphiC3I=>c+J}RFZyhEi_GuKe#Sa(a_d_NO9UH(g}ee6 z@z@iqhA_0aYW0I+d^1hQ`%|L)Q9q_#Xr&oO<&uU@+93AATBe{*UB&}$Z`0_3W= z8WW|--6KAX+dg&BHK zNf*7}LBxhF#zfM3^t&>~%$#R&1%V}sLDDnCZthI3sI@+WQEu?k)hn&MvkjRM8Z?Cj z{BqB$Xf=-yR}ZD#LKP2E6+(d~JpbE>m0pRt(phh4ny{+QT22kGp0G3TdO%3sX>V8y z!~Pfu9)CU}?cglr_^{-Kc1|c0@tSwk$>fuJl~>P#vA9mt)ueE2ItQX-(_k96+o1Gy zUvqR0h3=nuL&Ou4A7mBxbUQ(fYA$8JX}dLy(mrD^Pwl_b1I8yzxq~Y2t#9ES2jOK2 zJ6B+cByFD`4PFrGi)RD&kVs@w8|_IYgsjeeGR z2Up<*<-fAIo)SAgZRB3{(Dm76GvkDk_UO$4Oq%%XRmZ0o5umTiF|v0kv6!T=ix2hr zER5=sCG47u4Sb9SC&;Xt0*6;DJ}*Eg!hhx%MvLJzv{m=T`NJ0-hZU5#*+&pMIw>4V z(IZ)JN;tF+&;@ixzvn?0YpB8d#H3p{^3>;&^~b_;>{! zwpc$P({lk{324L>9MdGzh88*Q&R*P_kozu&7fejSF8qQ`^7vs7$_4S-AO9wMH8Tw=Nl6^TpV2ev zI670!85W>BIdj2{Lwv_m_g}#M@SJD##L()w6B5dn+($e@bAcPG$*hU%N|7 zMvpWYD-dnow`mD)Na27^RI2)>tocyC>VN%x!t%-MbG8$DN1tPRww1LO-*ni? zyyIm-+B?32v+{9Ovp$z}E=?r%eB<-2+QB9(r3?HQ{}&q<`?nr!rSji}ZRPpz;lKX{ DGdI%w literal 27184 zcmd6Qdwdk--S4t9OTtw_5!6M8ZKw$)ZeYpp0=PE}fO)pEYS-}5{(&xX*KbI$w6 z%jbiJ-I?d|yMBL{=gEih0oUHt^SM)E_+z|r&86yo_uX2zecZUuWhNX z!;ABKV$JTq{v69$nY@)OIN40TxZ%)y_lo(3&wKCE?%3cxlVgMNaw6HDtDjU}=I%Yr zwoAr?54TxsH;rB8*@5L64?dE&3qiIuXl~2dRw^It88zgNmQ%x*vDkK}eo{}fo0vYl zY+FgMEy&p&IXiD>yn>Ti9#}ykT18!Rn@xizvun+FlFZvD4Y0Yew&KijJ z91RWjx1@;}Nzi;{$sG0dt~Limbj?xMMs&=BitTp07%}JLJ8*;;1G*2mZfO}Kk8c2J zz1Gf*;C8^oTJB^*lJe(rN-WklThn$X6@D$Gq-3_Pv~srRw0ESPq*F+DV^irgcG^N) z3JRDb-<>aDEnV0M6oWr13+m&+)wj7*j?wfC}?Xz?%J=aOw-oh3)R@%J6 zP8RaKM5Z-lM-Uluv@-8yTV3-_-||3GL8lx(@+c(Dl2n&b6TPb3Ez{_Nz2(r19ld*E$!Pz7XtK7Y*IaZJj7v~L4+xZ|53Z_$X z8s?a9zI+(wYjaw#;S@+Su`!D&a$Qc|CL+4#%cJskyOqIC3Qm&tqKhr|9MF*TSSDK# z0t3R^iZgjTw~CYr!Z_GD?<_l$v@yv){)nOd#MQ+-tPOoe!)7~3-*OgP4>xi3cd)L2 zsF3ms***-FTOgTmGJe81+;S7f5uh*j&ihgn9{8<}GE^GVd5~YPx3%2tSLnQ8W8Gqq zw5AqIyI^j!7g+?g4f)hEeixLgsdXll%=eGdpOw!nvF(*LwY|%sBvl{(t3vPsE8XQ; zUU%L#H~!MXf41+VHQ|J;J~g#40iS18&%*8%`iNjntykj+S=UU7m&)D>LgqbUh}8ng zD1akQHYbTz$dVl*gWz@G!K_fGT95RwBd~L@OzlkbAX`_wQ<$Sh*SPoWKC}DAz4N7T zl30|Cd*@joa>&r2f}wS;`F63n4gBfMPjHR#x{z$p5(V{Hj@{v-I?}SrsyW_Uc?+6Saoq)%-o>NK#epfF)I=SfeoD#@?)DtN{ zhT0Nd%EG$O8EBC`?WRFl`8{4i9el7|!e?Sx;zMadq_1%@l5zP?@+WO2v-l?Dy11Lg zoOe$DVy_GP6)bmPfHU+FDB@)`9|K=k+%2|Djz$?ru@etgHpSj55(e{V+_T$I)6D#M=A4c~Hdi}AZhyI5P~Y16 z*M9uRGuSos`z?F9lvS{5oQ!})6Fh!!f(H-1ywDbo&ts@3LFtq|!B5Qot$5f?%zj2a z?2DH}!z`t#m6cC8Tuz)2;|;UiQe`;%yJN3Rj`!sabwR7fpJNka1VrG zN3Vti;BN>u`I6}S=C^icwwB6FLmz?X`7nF=#QVI zjSd^l4(Bna=vLK^2Fwbiu=6-dH?RPV_rMRVLdkewy~7)VwS$Q-gs&T^=i!}=pBA7G zv`^w%fS;WLjKMI**4Rccjs-hE4jdE^K?Di>sbZpl5d*|bLAinb9=xbA13(zLYp=I~Hqo;%SOhV6;O)mq zn5NCxGy33PZ+$v85E?~)8Ihg5%_$b$A=?`W$&-k=m<%Qi8&KSakoo2j$7te1rd1cv zuYO#X+5oULeaLLq3`u_$M>39tnDdB43k8blL5-=yp)d$foPs2;)xi$j$^oz({sSz6 z%~Huce7&}BiZ{Sqk_I6}Y75{UM;of4;P76_Qb2{AE{qGaZXg#W_HRxH0aEfUA&#@J9|*$C46HZ2X6OQ)Ov-`w`0*D%6BF})v{U}mtwjoq=TtTWU%dv7@zm}IGwZ*d@K0Nw93 z5uShV>}8a5$h!h6R*gBWF`w^*f7OJzx`u;UBr1@0VF4z2(gaTlDbg**Ki}jx!F};4 zaliJKwldSw!c1(4;EzkjKi>lJ)KmI+UJY_Cc{`vS5sXxu*JcH)0%iU*gM#^3S{v$K1j2A5V>zjylBQJuSX5=bOC^USC7NIzO~6TRx|eg6{L_<%J98d*{nN z!l(P@OP`}Tg^tzm3JH3E8RX&ts=6r^LHx-C2snto6*A)WSYDY`mAt*JTz`mxLLAc5 z;*|k#pwW;eGD4kEVufq~g&YE)YlU5irX=$^EOmVu@*DJ6LAec94slvOXz@6J3VK=s$PGh; zj8*8&sUVdSwUL%;f(VPhbLU)Q9Fhsp^llICJ>2(Luct+27Rs};xm-4l@YgkF-Cqv? zG;8Db1xQhR`{pHfiGnCHn9X4GTz7Bn=*~iC0lwRfJ#!~nx(#1%0&tpjfA92AGo`u; z@3PECx^nTFQFk}Fu@^pS_Rer)ciyxw&Dp=a_%9}aHk2Z+6uBN6h(~Cg0~#*$7Okdi zXvm48JK{%=kmDvcl@d#5kZ8GyrPF&HKk@tpf|D!U#0MJ%rIjtgiU*xGxffJXpJ3ua zznBBjM6ita9awYitHEDN(!)YwU8DHx-k4fpw!_XrqSzxq9x7Q}y>4Mym^rpIQc0lK z-4!#FT??I|ji{9LD4ZXQCA3!OCEzHjYI5*OvH^1NO3QW;o_SWPWR5-YoX&i~HOJO1u~8~GCoBE||3@A%QwU~f z0Ro`l$VHB=V_PbPB(dbVrdArR$8wGIhlD%QA4tX1_y-w~RD^Rw<-w1?eH&R9WevQZ zoKQIuuyec0aPSJ1DVn(Ex_6s02tANHCDYP|K$S9*o#}$p0e8<9D5q>vKA+9Ol!(|% zF;JW1gR{ytB7RPl47c3^Io(WXFrexkxwSK;`@v9Ne$U}s=RG+@&t~Pjr#&8ftksRZ z@=H8`A8Gh$GuXB+9`)Tae66u|9f=uS7P6CRX~s}q02(58Q8EVEJvpi?K8lD5s`4);B+VLzxBh!`+qOsLri^#$HGSrkp!6(DTnC8?5LSv_sM% zgg`Bjq(Yzo2XQ=1zx^9tg!*M&?qu7cq)$y1z`{4KI)a20?u^hDL%5R1dk6?anAw#8MbAA2?f;n${e=%=2xG9 zU`c>PJkxAg)vLFc1x#WOfahSf1SKj#CGhx9UsTLWCfVGlCPq00$PJMHtU?yReMM-W+X*8k^9DPoi&1MwcQTB=*WzY_N10l_rBetem&1>rKKG(zWoSNVPLcP5OsC3WALOPikG%v45=0^Kvo}2ueeBA`;uApESFJ{QzXud1Q*SU zQmSiK{ee?3Na|=Cs!HEqZb6xX-Cbq*3QBNH0{{eGEF(8{=NNJ`k~fe1bCe$fLio6JJnm7 z|4poM%-Lm!S3q=DnYX^fFhc(0TfJjlV|uCYmmIPjGmr7AlDLSERYSf+uOWDjyzscr zf0Pkh!d`=79B-o-DX|Q!MU>LuK8gNPYSe~Mt1u`?Sc-o-e%eGg{^CZ- ztB}|s6V^^?Y!txSxa5xtFVuv;5~&Yp0cAxZ<0;FQb)~AR4W~zM`R2uYk-!8duh2(i zGSSWBnwP|AHc}VL#}cL`J+BMq(1Mi8@xs^>OurD1m(1xG(fWj85Cu=H4~z3Uktdpd zA&O+nWYIhJ+M2 z!4{h`)s+SsEDhzSog)D0{4BW@6ha|THh}cZDq6E_fe5u5pjV}@`pMZz?f%?lgeH8z zk#fzXT2b)jFfsamN)g3g{*rQeeZIuY__8NcMz;bjM1`)rDJ9c#!JK0w{u-NaCz*;| zLf)eav}pq>Qu&VzF%**uKH;p<;!b zZ!d$e2uG1^X(?DvhHwgij$9&s^o_AsgtAYGnoxZi9uWVakgziaK*vS+&Y0lp)T#D=y-#y4d*Ysdha-|A(S8%oMV479mzfs#-=g4 zs0Txqu3m@?OIRK@3SWg>Ho8XP(j~UXqKNda%yHcIHDCne*q;EHAG=WrIGLCVnUgCN z667Yjw^N$;?;YTY%pAzR2u)1ZUqNjV`%CjuyTo~0MQ4C-Hr%Ht^klOXdgE9L0J~hX z;l~|8HqYrU@^;|HKHBA*+2cDi98y6);Y_o~A-YC%EDR>`3w&aLgvsw*Mq@|=hen`m zj$XjNEjBI34YP88o>;+^;zpye9!#LS_!FF}0&}F49$D1EeU+$%Qqw`etdDVg;p?tE=zr zZ77*{{U+4;$Y+zY9d^n|jOe0wwvH!6{Mzxo4N-2t@*T!=uKB0AT_7W>88*RQWZxwu zcFof3(QsHotf#*zhBq!H-v4QCo?yA$fX!W8ki+hGVC}ehC>$3x9`Zt>;YiL!srGKL zC`tn7NpV9@1z`8}XTV=TT(DiY@|mn}9=C#Cl$}W=O)30Ll`}jmk)Y+YyXJ8YJ^&xk zEz7~3-d}*(B(vxVOeJ?huERI3-l>@|JRnLhSk*Ug!lNbQ>X%fHVMh9OC@cIOm+ye& zF)xZmXu=~r%gWfP5+pDWNjsMT39q`DaDut`MjFywe8YYaK)?f&Y% zEz`ftK;v1s4&;sBA4Z&$S~xf2%-i`9H~=a<&x1^@+xM z$A$wC%}El_2hvng?TqSG1i8hYs-OBuXuI|i?L;pnQ0iA~AcF65{ULS_XYY6UU2J)I z>9jidL7tWR11K6>kp%BK1qM#$pV&CVa^f@23aKwLMcGS8k?aS0BA-O#DW8&^sm*4|Fy5Z{P|iYFU!<=5aqj2YwQ%Szs%a_#URhdek|;W^jXwwptUo=iYR2-lc#LQgw2 zT>Q^L(V*xoIKH<(e=yQKm2el00+SCTBU~g^cqO~?a-|eTiWV*v7-jmD#`=`SJQSMJ z-J&>l{wJvZ_~z6#sOXqe-HL@-x$>;luJLIgQ*}jm;*|gBcdfJjw|bK5Ac#|n?ori0 zr$-|dbc83poT}J##DFsZLP-)|xQTqn}n85yLsjZ6g0 zKc@;Rpa|u-RHO^;53XG=N{k{ALXIflsAb<-A33OE)4NWjWy=*r-w5Wv{tMy>ksC`O z7vC>mgvx#Sx4&ta=o`Zypfbqt`}+N*0#P?~jx)7~M$JvHSfIGSCz7uL>8(jbCfB@vS@f~cn_u3CyfFYK5~m{7T7l68 zK10(0y-FEOu$r?<6-uHk2AL(_95)^hIVg;=Nns0*=Is*%br40!mU1jT+#VfnId{TY z;r^hsjYl$I#hc@GY6aoJ7v87w_|2SeLZT8W4>ADghg++0B}47$JC2SF7xh1&h=a2y zUK$1u5OBGTzHSRKBZI#*(t(nac|M3kS{V@yA~)nqVV;!ma1_A6qp?E+fjl@tkrTk8 zM0;po4GJCT0zS=BGUh#iQWqqIyr(hmeh@LJ(I;jfMRB+CM#AzDz^?`7)gNZovj3`h zUKD$4qeDfUR_U8{LPA!XR_PLXgXUonqLR@(+@U_q3il`M*xF=S7)IR+S9h&Ld6m@# zdGtW`?A4%r!=I_ty)tJG7oA_tfz#jH91SYpQ9f2q|dQr{{+4W6xm1YpD&Bw`e9r-Z`F3fAmG&^Y! z<*Z1enbsAV?Y?$(&~#=9hg-5h0G9J!!rZVd#=MuKNFStp^!{d1y^^ILkd4kH z;W2WKvIxXBfx2Jky(|-fY!yD-daUs+0OcD^fr;3$or4^c%x?VNuky za+uv&K+lXFr5!j{GVf1Kan1Xa6Z@oxsG9cj9oVR+qhaK|D)SLIakXw4%o2`2$;X%2 z)F4=qJd%4lQ)L_Jyg_7783^kEI>k+{`5oYaJ{^M4lmA~JjDQX?k_MSqtXWmf`f||e z*Y6)S%N>MLL~-GmJ?y6wn|3o#Df)L4o8AxsusA73UDKjA=lBB)znkf;a0f2AxJ-5& z1jCy|-_Wtt2(g3A%jwWEoOt_-GM83;{*55Wz~7(z{}dVQv+vLb_ucdX5u_HN)K9#9 zEVdU&kR5Q?%nL+5HEK{VPmzIt;=ls`39b7H{OQnWwD-rf4TME-WM+#1rUf0AlZ)c=NLv-1>C{uU zqg?A7$xGqj>4B()RXhae2OMuCFCpt-c{JkwJNnQ=ubTKsr#Yyd3{TA25NJ4=0dg=N z`ofWEEaYGk2w9-#3ni~pA$S!npb==STJoAa0&TwHbmkFWys`qBpH4pbN2I``s&;{I zkoKg0&<;jNIMzo{Nqim9%=9+Ttx;Dll9k2$%7zxk9wU zqu3jBxfg7B{SmAiSLY$OtY*;_^;4mmdL6@3|anlccuMLb%) zoEq^tG#0L$MD2D2Iq(Z!yjREmcYsaLcEtpl#AMwsN zc8#Hf0J}yD4gwE+faVlrL-KTVqvlnRJzzeWKds`Hf7H;#kz)pwivH-y_{z7Kx0hp%`0jX5 z#$zTMn8P=3SQIW*2F16(RMtB7LWC9JJE=kwC{Y=5lj@}rH|6A{?#8q46TM5uvwJ2- zAO~Yq&-|>PFw7k}rirPw-+B~-O?>%jg)dhWOVv$plx1^w9_M*peHpE-#;eGZldI*escy&> z#h^TK-+pAb_Ua4E+|S6^l9KGNzC_2t5Iq3d%jF29j2;~0-FhuU&oEX^KwLR*u*z;h z5Ui*b6MU$8>&J9J=DPI-nVS4Jh7gYr%`+*1q}2vP`INH6?a^V9m9SED zZU9qKIRq`XiBn%tJRvHa@~EIFf#YXi!^%a2jGDtWp8c!roxn0^5BsdbJ+^cetbHPT z!F(7r;bW9F6J-V(6?T+Z%!icq`Jo$n?MH4U%+rvbQ!}vw^ZFM!##GrAg8gt~vC1z~ z$!y9cm|c{JVCP+P%B9j>V=Dk{Rtkr_m+j=BrWVZ?UJd^U(6Q_#`nGlgjw@Flxs+n2 zntqU=8?@jdG)j?)pq+-!0RN0?+!M&BMENHym9ye~np$|TDi1{7l`=q6!vy&B&^Tag z#&f;AHP?7<8)Zq*&_t!r$|MO)+Fy^TpV%1SjK*`@IOT}ZDxN{Vz9;i-+;^sL?3zRR z=>QWInSp~=a))UtzJ3kX;m6mzA`IvLTtvf^-m&EU5_)n3N)&cXfp|D4j}C$sa>XEz z>N3L|(jFqd{o~j+_G2OsZ5kVHc#L;w-s&t$U2HO_q=@>!W^V#x@2Z#u{6 zSz0+UIAT`S!>>uP>t_&FWC(9dZ-@}&qHyQ%_AMn^9Yrqjm#NOmI8gjWU^N&}~}4r;ehIGXlans=!SKBToMw>s<7rh|xx@*sGCWk_gQQ z5;<|aHfn6RZ0xZ6lYL(RIN<81Yfk!K%$vT`j9j{^zqbNN^1u^@Enzy3IwqnsrKnLC zas)n7Oiibijqax%P*gdU*(eIHraTEFDP!9gCr|8i6#!Cb9T00U!8OgxX3G_5##~`Iwb!ym&@u z2Bl>NN#abh?!_>KY&oVU1>)47sy=-I4j-VpjPEG1L|2%Fep>65=jff}n1H{{`F`B{ z63GA?eQ|V+)KSNaEYlNY5T)i z{Q0=9z&!rT+o@n{-AIC-c4Oa}n|4j>h9oJ1R46YM2<3>df!Z|z3)@> zP^dpJXj0RJ3c;);e$oWEz2jo>LD&^=`Zz^U?4OQ>BzYlxHiWRhJSV^(>IlKbwJ8vk z&{g>4fg@%>9+F66)^)4%B6cc#)T6EpP6?^kBhvGIZW`tHUPNaWA3jc>%B{MwMACSi ztKOGWNfJgg;mPmO=|4HOoCd_$d>(GTqb_7|e-Jbu&3UNWKYXn4SXxi9Tq?Ih=DFy` z$x=VQ@d^@ODMp;K*?46|uQCB23T^}}3Zj;N3AoVaDhJn{SE6l<0#~ZgLe2B&kwvpT zK`p9;>YkMRF&cdS_zmIfLli-I27rfP8qyEpCgk;K0B78PA7*u-f!ZR}O=a?^0{9{B z7Ng657GD=${xhY&y9~w6UaomfY+=WmOJlZ`V?B;;I4nbQwTlGB^N_b&@?pGRir0_k5m!Zs>-EfQZ)^r9Du)f5t;P7h;XSNf@P_lcC^EnX zc@JsZM)Mk|M~B!lSzvn{e#m*a1cYL$0xF~7TEJLIQ1Lij*k=BA&^c%UCm&*5{U(-< zwz%C~FDc--lP-b-|Ju79`3z`vYrLn>DqI3V*w?5^ZwKP?EEz;oVv{52ifVV7L)?|V zx#jz~e-Y4*P`ztzxl?plbT~kXG(eJXo2hZ?;Ip^f*@r;1TSzGC?Gr0#fP(_8oRZGI zvE_J8fvU#EP#J(!Z*R|13unq{#j*UK)#y8^{=%d(rvwB5qe2OBs-_2*3E)6-=<>_8 z*!;d-nTW8*9lemaFAn(`+n%jhzyOMTl;&h97a%gcxk4B;qC5DFd-vHd>Z88##xFuK zLkj@{A}A^KD&mbTd~+YJ!0Bv}-XDw5E+VAdgq$}LzMVTMLZuEv8jFKpaYGdMYKjS% z7$RDRCQE1rOau+hLZ`-E(|7ayk_zD&6meDN@@;=cs zMUkDfPJg*5FXIw;7k2L`l$HJXr?+eL9B6e{0CAGUmJJ9hIL;GVi1Q-r*otukMjbh# zJ%e}z5JP7)V3&CO(ENl9@{J8=5~?g28|DfJIhhR`WR>$m!r?%Jc6~LfB1?ZyZAH57 zR1F_1?uLQ>R20E?{7IBXNa8{kg{oCO;P2QFrSxf$w;L^;uzn?R=Yv2l)dT*aJfBL` z>+`aWr8mRA1A;ZKQF=>Jl3*TYp%WhzAGcF=W~hz2YUwRv9nnm#OXN>r0bpGzbD&00 z-bw#}5~?DS;v&6t9HE#up&z89PMC(0*)frw7tN2;gN(aEZjh)E6THcRKvLXUMBo;* zK%T;`Jp7^=1X$*WHlrF4f9U755vdr0X*^Gq`BBbL-@(8m*Ouu<3~aTHY^YFG%o!pS zF%KYivu>T<@*+ zl;~4sfS!7RWkcwr{ zNZM5%ecnVM?G8QccPfOEt0NiqjhoksY!T}((=NpB$bMj@QL+U(H1OjrS4Bt*!{i*k#h&sK=sG^eki(e= zk6PG5=`NpC*gx$hH73v%=;Tx4Pl(&E3K0MkoJ|$$*f`fOsHUX(0a>4QJwKx#Em9P z>9`0Q$Y4T|PVgwkDWHpl$}(OPrz{IHLts8}2>If|?^*D~yo$!OAv*6)qQs_=FImL( zX!$JQ8JXwsXfjf@)uT@OGZt6vl|(XNcuFOb(~lhJ?LmM=oV_gtuu#w(9GD2@GxjeM~X`c_3? zWM!1jX&UC6bf&gsrno*sSy}ypcVdsF&Ub;3?D*^4s?jetYLyrY8oeoD2|%ky_~u9) zXeyZ_-{u^*YRToEL46+7lv_SDg0@{)P#VUgY;wYvUqXYo}T zu9=F{qFHdL&xQ`Kqqwu5R+}IL5>uaK9|t3+TtclJzIoc=+V|Bz_@YWdDTrX`l<><1~9r>?Y=`=x{m$5PQ%9i;jwQA%KqQX3R!=T5=ekVyaujH}@#BCj6$ zrsn?^6%BL#>l)63LEOa>DFSLKY%*Yg^#1nZz7-9^`#D+BFjrkKi5f|1^`>_TYvH;# z*q3lTNm#~j=7?vaFWjnC_wD;UTg{Rz*-W^PH8&iM0-~-L_wy2$GmaTcOC$jB%Jv7{hC%)L13F2nwjo zK6W%oV4swNq}ObbGR5d0+(qfiO;54_`o^ZG_{5nH>q7>9<2cH$9zCyT@#;0B?v6O-4)a!&DMXQL5pHMAAd1LK#+t$X#+Yb~ zl;=ow->SkYm;{ALfJbh=78^$+)c$k5Vd9+D4#~-EpWc~P~+Zi~}?m7R$^=%D5C=ieMD%xZGon73z zE|0}VfK}3zBKB*x5dVSeahiE6*DIokNX8F*wg8GJAwOj;H65nR!?)&E*xqP(GjY8l z8VSUTOO+iY8!IlLQ_jN2vl7-|Id+Dw0R8+q1S-NJJGpi^B@wq$?M*I2$HLs_rBoSsmpHQfU+#lTbRe+13%%L$8Vr) zA>|0ULar$fb)Qn=)%i?4q@lQ(PQl&>bFmx^x+<2lA)mIg()Dgm0YjD=WP` z3)-}yy+~X#0I-g>`ZIPAr_?W7@mAm_Je&#*r^hh@<9zxx5f~AK!sYuiyeD&+mowm3 zK!^Z^$wV>Ga$Mxd`2ahWstDAk%0P{Nr@{gJx!`a82WsLM*@#~^A;^SH(dOZwJE2!v zuktj^_)#p@7U;hWiGGFA03QoT#H#zhalhY7w)(vWum4}p)9-D={r*yj{(lWoe^-R{ f_d6-}^!uxm`u{yld;0rrNgu~z&fxgV`15}N6mG_H diff --git a/Robust/Transactions/Notes/sysgurantees.tex b/Robust/Transactions/Notes/sysgurantees.tex index e2329d4d..ae99b4e0 100644 --- a/Robust/Transactions/Notes/sysgurantees.tex +++ b/Robust/Transactions/Notes/sysgurantees.tex @@ -18,44 +18,47 @@ A Transaction consists of a sequence of operations. Thus, a transaction can be r \subsection{Defenitions} -Def 1- \emph{Set of Operations}: Operations are taken from the set \{readoffset(fildescriptor), getoffset(filedescriptor), writeoffset(filedescriptor), readdata(inode, offset, length), writedata(inode, offset, length), commit\}. We denote read operations as readoffset and readdata and write operations as writeoffset and writedata.\\ +\textbf{Def 1-} \emph{Set of Operations}: Operations are taken from the set \{readoffset(fildescriptor), getoffset(filedescriptor), writeoffset(filedescriptor), readdata(inode, offset, length), writedata(inode, offset, length), commit\}. We denote read operations as readoffset and readdata and write operations as writeoffset and writedata.\\ -Def 2- \emph{Operations Sharing Resources} 1- A readoffset operation and writeoffset operations are said to be sharing resources if they both operate on the same filedescriptor. 2- A readdata and writedata operations are said to be sharing resources if they both operate on the same inode AND the range of (offset, offset + length) within one overlaps with that of the other.\\ +\textbf{Def 2-} \emph{Operations Sharing Resources} 1- A readoffset operation and writeoffset operations are said to be sharing resources if they both operate on the same filedescriptor. 2- A readdata and writedata operations are said to be sharing resources if they both operate on the same inode AND the range of (offset, offset + length) within one overlaps with that of the other.\\ -Def 3- A read operation can only see the writes made by write operations sharing reources.\\ +\textbf{Def 3-} A read operation can only see the writes made by write operations sharing reources.\\ -Def 4- \emph{Commit Instant and Commit Operation}: A transaction commits when it invokes the "commit" operation. A transaction $T_i$ is said to "commit" at instant $t_i$, if and only if it reflects its "writes" mabe by write operations in the filesystem or equivalently makes it writes visible to the whole system for all members of $T$ accesing the data at instant $t_j$ such that $t_j > t_i$. After a transaction invokes commit operation, the transactin ends and no more operation by transaction is done. An operation $\in OP_{T_i}$ is said to commit if and only if $T_i$ commits. Commit instant are not splittable, hence it appears to other transactions that all writes are refleted in the file system together.\\ +\textbf{Def 4-} \emph{Commit Instant and Commit Operation}: A transaction commits when it invokes the "commit" operation. A transaction $T_i$ is said to "commit" at instant $t_i$, if and only if it reflects its "writes" mabe by write operations in the filesystem or equivalently makes it writes visible to the whole system for all members of $T$ accesing the data at instant $t_j$ such that $t_j > t_i$. After a transaction invokes commit operation, the transactin ends and no more operation by transaction is done. An operation $\in OP_{T_i}$ is said to commit if and only if $T_i$ commits. Commit instant are not splittable, hence it appears to other transactions that all writes are refleted in the file system together.\\ -Def 5- \emph{Precedence Relationship}: If $OP_{executed} = \{op_0, op_1, ..., op_n\}$ represnts the operations executed so far(from all transactions running), and the indices represnt the order of operations executed so far in an ascending manner, we define $op_i \rightarrow op_j$ (precedes) if and only if $ij$.\\ +\textbf{Rule 4} -\emph{Relocating the Position of an Operation Within the Sequence}: Given a sequence of operations $OP = \{op_1, ..., op_i, op_{i+1}, ..., op_j, op_{j+1}, ..., op_n\}$, $op_j$ can be put into the standing $ij$.\\ proof: We use induction to prove if assumptions above hold true $op_j$ can be relocated to $i = j-n$. Assume the same $OP$ as before. If $n = 1$ then since according to assumption the pair $(op_j, op_{j-1})$ is not subject to the conditions in Rule 3, these two can be easily exchanged. Now, lets assume the $op_j$ can be relocated to $j-n-1$, now we prove it for $n$. After relocation to $j-n-1$, $op_{i+1}$ immediately precedes $op_j$, as according to assumption and Rule 3 $op_j$ and $op_{i+1}$ can exchange positions. After this exchange, $op_j$ has been relocated by $n$ and to $i$ and $op_i$ now immediately precedes $op_j$.\\ -The same argument can be used for $i > j$.\\ - -%proof: If the sequence of operations $OP$ is a consistent one, exchanging the position of $a$ and $b$ does not violate this property as no difference in the bahvior of neither $op_i$ nor $op_{i+1}$ is made. If ($op_i, op_{i+1}) is changed to ($op_{i+1}, op_i) they would still both read the same data (if they are reads), since there is no other operation in the middle and Corrolary 2 says the read from $r_n$ reads the most commited write to $r-n$ and as no writes are reflected before the commit operation for that transaction is invoked, and none of these operations is a write, consequently exchanging their positions does not change the data read by them and hence the behavior.\\ -Rule 3- \emph{Committed transaction Should Precede the About to Commit Transaction}: $T_j$ "commits" at instant $t_j$ - $T_{commited}$ denoting the set of all commited transactions at $t_i$ such that $t_j > t_i$- only if a sequence preseving the behavior of the program can be found that in it all members of $T_{commited}$ precede $T_j$.\\ - -proof: $T_i$ denotes the last commited member of $T_{commited}$. Lets assume on the contrary $T_i$ does not precede $T_j$ and hence $T_j \rightarrow T_i$.\\ - -If there is not a pair of (read, write) or (write, read), sharing resource $r_n$ in the two transaction, then $T_i \rightarrow T_j$ according to Def 7 and Def 9.\\ - -If there are such operations, 1-At least an operation $a$ reads from $r_n$ in $OP_i$ sees the writes made by a write operation on $r_n$($b$) in $OP_j$, however since $T_j$ has commited after $T_i$ and writes are not reflected till commit instant, hence $a$ could not have read the writes made by $b$ and consequently $a$ does not precede $b$ contradicting the assumption $T_j \rightarrow T_i$ . OR 2- An operation $a$ in $T_i$ writes to resource $r_i$ and operation $b$ in $T_j$ reads resource $r_i$, according to Def 5 $a$ precedes $b$ and $b$ does not precede $a$, hence contradicting the assumption that $T_j \rightarrow T_i$.\\ - - -The same reasoning could be done for $T_i$ and $T_{i-1}$, $T_{i-1}$ the last commited transaction before $T_{i}$. Now according to rule 3, since $T_{i-1}$ precedes $T_i$ and $T_i$ precedes $T_{j}$, hence $T_{i-1}$ precedes $T_{j}$. Same reasoning is applied for all the members of $T_{commited}$. \\ - -%If an operation $op_{i_1}$ in $OP_i$, writes some data used by an operation $op_{j_i}$ in $OP_j$, then $op_{j_1}$ can not precede $op_{i_1}$ since then it could not have seen the changes by it, however def 3 says it does, this is in contrats to the assumption. On the other hand, if $op_{j_1}$ affects some data used by $op{i_1}$, then since $op{i_1}$ has not seen the change, $op{j_1}$ can not precede $op{i_1}$. If no operations in $OP_i$ affects another in $OP_j$, then the set of all opeartions in $OP_i$ both precede and succed those in $OP_j$, and hence the contraray to the assumption. In this case, the transaction are conceptually interchangable. In either case, $T_j$ either "succeds" or "succeds and precedes" $T_i$. Either way it succeds the other. \\ - +Now we prove the other side of the argument, that if $op_j$ can be relocated in $i$, $\forall op \in \{op_{i+1}, ..., op{j-1}\}, (op_j, op)$ is not a pair subject to the condition in Rule 3. Lets assume there is $op$ in $T_i$ such that $(op, op_{j})$ is a $({read r_n}, {commit})$ and the commit invlolves making a write in $T_j$ to $r_n$ durable and a precedessor writer that writes to $r_n$ does not exists for $op$ in $OP_{T_i}$ , now if $op_j$ is relocated to position $i$, $op_j$ would precede $op$ and hence $op$ would see the writes by the operation in $T_j$ (defenition of commit Def 4 \& Corrolary 2) and hence the behavior of $op$ would change as it does not read the same data as before (the data read before could not have been the same thing due to Corrolary 1). If the pair of $(op, op_j)$ is $({commit}, {read r_n})$ the same reasoning would do.\\ +The whole argument can be used to prove the Rule for $i > j$ as well.\\ +\textbf{Rule 5-}\emph{Operation in the Set of Execeuted Operations Belongin to Committed Transactions Should Be Able To Precede Those in The Transaction About to Commit}: $OP_{executed} = \{op_1,..., op_n\}$ represents the set of executed operations before instant $t_j$ and $T_{committed}$ represents the set of committed transactions committed successfully before $t_j$. If $T_j$ invokes ${commit}$ operation at instant $t_j$ - then $T_j$ commits at instant $t_j$ if and only if operations in $OP$ can be commuted in a way such that $\forall op_i \in OP_{T{committed}}$, $\forall op_j \in OP_{T_j}$, $op_i \rightarrow op_j$.\\ -Rule 3-\emph{Operation in the Committed Transactions Precede Those in The Transaction About to Commit}: $T_j$ "commits" at instant $t_j$ - $T_{commited}$ denoting the set of all commited transactions at $t_i$ such that $t_j > t_i$- only if $\forall op_i \in OP_{T_i}$, $\forall op_{all} \in$ the union of $OP_j$, such that $OP_j$ is the set of operations for every $T_j \in T_{commited}$, $op_{all}$ should precede $op_{i}$.\\ -proof: Follows immediately from Rul2 and Def 7.\\ +proof: If all those operations can be commuted tp precede those in $T_j$ we could have $OP_{executed} = \{op_1,...,OP{T_j}\}$. This by defenition of transaction means $T_j$ can commit (it is executed in its whole entierty).\\ -Rule 4- \emph{If All committed Transactions Precede A Transaction About to Commit, It Commits}: $T_i$ commits if at its commit instant, $\forall T_j \in T_ccommitted T_j \rightarrow T_i$. +Now we have to prove $T_j$ commits only if $\forall T_i \in T_{committed} T_i \rightarrow T_j$. Now we'll show that if all committed operations can not precede operation of $T_j$ the $T_j$ can not commit. $OP = \{op_{T_j}(1), ..., op{T_j}(m)} represent the operations in $T_j$ excluding the ${commit}$ in the order they have occured in $OP_{executed}$. Assume \{op_{T_j}(k),...op{T_j}(m)\} can be relocated in $OP_{executed}$ in the standing \{n-(m-k), ...,n-1) but op_{T_j}(k-1) can not. This means first of all op_{T_j}(k-1) is a ${read}$ operation reading $r_n$(each transaction has only one ${commit$} operation). Furthermore, this implies there is a ${commit}$ operation by some transactione $T_i$ between $op{T_j}(k-1)$ and commit operation by $T_j$ and $ \exists op in OP{T_i}$ such that writes $r_n$ and $\not \exists op_i \in OP{T_j}$ such that $op_i \rightarrow op_{T_i}(k-1)$. On the other hand since there is a ${commit}$ by $T_i$ in the middle, the commit by $T_J$ can not be commuted in a way so $OP$ precedes it without any operation belonging to other transaction in the middle (two ${commits}$ can not commute). Hence we can not have a sequence where all operations belonging to $T_j$ are located next to each other, this contradicts the defenition of transaction, hence the transaction can not commit. -proof: If $\forall T_j \in T_committed T_j \rightarrow T_i$, a total ordering can be established corresponding the precedence relationship and all writes made by committed transaction have been seen by reads in $T_i$, hence according to Def 8, a consistent sequence of transactions would be provided. \subsection{TransactionalFile Opeartions} TransactioalFiles can be either created inside or outside $T$. The TransactionalFile object ensures transactional access no matter where it is created and accessed. Meaning the first time $T_i$ \emph {uses} $tf_j$ the flow of the program should look like no other piece of code (i.e Transactional and non-transactional) outside $T_i$ will \emph {modify} $tf_j$ before $OP(endtransaction)_{T_i}$. Otherwise, $T_i$ has to abort. \\ -- 2.34.1