From d43bb6423992abad010f1fe814ef79212e1f8f8a Mon Sep 17 00:00:00 2001 From: navid Date: Thu, 18 Sep 2008 18:46:22 +0000 Subject: [PATCH] *** empty log message *** --- Robust/Transactions/Notes/sysgurantees.dvi | Bin 19624 -> 27184 bytes Robust/Transactions/Notes/sysgurantees.tex | 74 +++++++++++---------- 2 files changed, 40 insertions(+), 34 deletions(-) diff --git a/Robust/Transactions/Notes/sysgurantees.dvi b/Robust/Transactions/Notes/sysgurantees.dvi index 78947073abebe9f86c9b64c6c2d2bafad3566c7a..1eba1520f06bd2b699678040cb02059dc930be3c 100644 GIT binary patch delta 12549 zcmb7K3w#t;x!>%}k`N%2R|zGhgaS<@L=q^E1gI&9O(~B;TC8owVRw=p%+9Pk6GH06 zY1OvAx-y)099b!%^yQ=F;q|(r?Y6;cy|q_cZ@pFuB9<1dijQB_+KT`0oSE4Pp!NFu z*`_<^@tyDS|Nh^1&V!$=*!Sa#?bAmrY-?$mH~*8dSge9|Ou2Oby2plHCJ(=5)Am(I zRhCn;In`A4?FZ^DHN_Ouk%tdhX_XCjmy9fHudJKy$|bqjRFJ1#fnV<0U9tC;M_co( z*yPC5mNqvxH+eMBuAF(vu*ykYX_XcjWnjI27rPkUESocWa!Q6BJY1QtXp`>m#&3qM zGQ&$I`*LiPr*<1Tl_|Zwj5ap1o|;oE&CnSJ@?Y?eTyvi7s{XI#J*s7lFjcEzWUrc1 z&16o?T1Kw1$&G)ttv{z(>UqE7m`W<8SW1JY8{3&ZVuGFDbC=T`i}5+Zmz}GQrqm`k zvFt~Dl_n>#?Acyb@3GR2O)P0-GMY8mQ*3ss9v#2IIdh?^y7KQYO{uzJ;ncsMMw>*$ zH=#{`7y81Nba8w|PqExsUm!;R#f4x8FB&-_J`7@A5sR^HH8)o5VMl5vvl%rv+6C$9 zAIzKWNKZfgN51+0S|v`7Gpa{*DYb2FlE3KTJ$9gHsD$?UFn&P z8V>i&`^cZ*I_7|BsTpSEJofw17q`(DKHX$nG*jEutCFBJwm)t3s=lydk{dtsJveM3 ze&)O6vUdH1#q#YJ7nNjEH8s75dn`GWr&vrJXlL|5o1qW&*`nE(^wJL2*fH}myV>8M zquWw*uDo`+!Xm0H$ZMBHtw95XDd22nGaw#sIYc6dQ*}?(Q}9AKhi(K4N2s~d%oEX> z?FDJ(FS!oOa}j--$x?{ZW=B4FQ-|&uS%gOrnS-s4RQ*6{jmKWO;4*u}ldUi?BLh2F z$}%We0t>*zu6)tdi0v5uj=IN({#x{%vDq26Xv8w^;lA#;Gbn%u1Q|24y_#hyFb@v9 zpa%Y$RN)0dEGt>A4kc&0@}&D9g#mTs3i71Ap-K$hgn?igGM%uvN2}-5Q7Yk|rjz|V zcnA~L_SI$?03MD)dqjXPSG%3~*H2zPyAc1n{qmD*b3E!;lBo=UfPXns4O_?5Ug3ag zE$hVg{Q;pUcTef;_DXADxV3Qc?>+pux>Zf~Ve`B*eeMIrC8Ssmz5;6JK3#`-T09=#m;=kLj1@Z7=$28 zsX328KjN*X7i`PKwjNZk=$>LG;j|P-8AT5dpyrwgIs4%aq~DRq9ziYwz}U_(*2 z0(qpbqQ?=FetNUay&( zG(0&I!v=K13|j%5UQ#gvJ?o4&iZuW(&SVTJ^C7h zAg=VcU-2M-2Z*8M0gazY7r8bSY{j7jxvn7n?blFWFeT1x_F(k!ib zTfD$B5!k?nPfaCr1TYSBlmogEAikm+ApX?Ev$7Z~ZE~gMcMi5PL_2xx{#PF-XkXa& zgqF`cBhyCFUe)0u8{R;(*Q~yV-Qb_nqy%}ijy4sc*1$zn^d7QDMoFni{sZ6#+(f!( z`H3*H)M2;Z&q;dFyrar^b_woiDl(~14;FJ0`NPHfK(c6{uG_J|{YFT!cO$W%%s+5Lm9 zzOqX+k5A}We$T3-YuMVm9IWPN;mt7Bmlc+YH}S%I2Im)- zu+nBH@!BJNqo{<#udwHm8X~bZ{9DUm6;-DNG{9NpQ}sKNG+216BjtZE7z;!+vT6>v z$06|?PpaCzrYNGE$C>XR@aX|oYK^Q2Y@g|rt_DDVRctp{T?=TQr%2P+W1;YDM+htC?XsMq=;bj z6%3X);IRwp#}6Nw-YEPKyVkKilP1~MCI3hs!_p3xBYz15553A69(#mNUXXY0g_N$m z^S&Mc2*Aqa z+IA6HmC&4+ok>_hw9b*XO+MEf02sI5gn`I)G!S^h9gcp!nP(iKbARhiH3fz$v*^Tg zPvJ0bT>qV}CgHSj#NL6a4A!y~R14%ZoD^kLa$>$R9F`^OZe@*A+T)|X&6Jv28x>QL z(=J#3(03?cd|$$WBN0=1;@+ZwcOJeNhZs3u`U08w+L7R($z;yJfl{-}B?)v1+Ootl zz*-hVqY|6vu~8S-t|qpCWg|ol)bZQOdW{YbhSD1H%fqopTk_7>J9qE^#T;KXft#W< zxQA`Mc#7>v&)n^cVo(arLgI$+g--1z;{ORVr_^p$ z*TV9=Tu`D9P{y;Wo_x_vmz@;AirSbn%d!cC@3_*D)xueD)`5a_WEKA%^kgKtx2Q4U ziP=lWUn-sYE(r~!#VV{<0m>NNo(}~+d)Tvdf?bd+pEr2@D$K~$$qPgaIZLkmUtXZ0 z#EXbr*}Jc}i4AzXXaKK{Yz~i_+FDX*Vi9!!Rx<#*D%r?aSH>_cq9R0P^z9R<;0u^1 zfS*V~sf+#3oC^=Wcj}4?yAXe4*239N{Ea4*^SPjOuynwTPcP+G@*7zY753sI@dRts*6D8_gpjrDm`Tyd4nF3uIHtsAB)L0s|sO(0UM`1jDCZ zgGgGwJbpi@xlmd8(3Pr~Wn-EvzxNCZYhuq)?X!%EriCMKjFHXBa8&qHwk4lx_Lh@G zK|FHFIBG1q5yK1eqMJxSfs|>5Tmm~maMp){Xwi*)ZDbpp_ntiNrP0mNwGduxT3THy>w?no0cAL$%?7Ym>n(+69C!UsnX z6T@&{jph>a(&5(uf39ThUQm#%&r=Xkf>{V0MCk=%a3r9n$Pnqts-bgaI6DDe@lwk_ zOOLh%R#R;-hQ*a6HI>vb*S}ey`o%!q2Oew5=iTAEK3Z&;(-q zSA>WKh*)ZOP)id*4vU#O`vZ@)=JQ^u-Nh#=tl1hAN0AY+*b_Q9bhR^Hh5HKO=0szB8-nRGWyWkCKuhxU^lV+hT z0@hN>^w1hOtDFh;K;3bFH&#W^WGIj^BP6!0h0SEGp%-!Inep%SXrW3Tjll0k^O(F|vrOBOTfdt1 z3{xZ}K@1RpL*vPnjm!FUPCpTnfO2CdxIVbLAk<_Yn1!cW?7n9M#U=+rq6B~pngC~0 zL?Vj@8CyNB(heu{g0ukuMNonUnl=K7nMzwih{n(!epG+)zj^g|>zH?LP4c}N0pQRU zE>^sC%#}E?-UA~$(ybT3&g3lX3D~-*&djkZXN;TXyG3WWD;G{i3!OP39{dQ>t%pFdsE4`ra|rV zd~4NoTu&za=?atRm@k&Pg_eZt4EzQtWu>9V86T*X_&;C9#;O-)bu zIk_P!Pi$b*wFII%iFwfCw!0~R%j-TxYs%|B8FWhk(+GpGyXf(iDWza#sf4_`XXb`o9V(Cc!6l4W-BgYEq26)%)3y*B>pk)j2c~8Y(jxd;+-vAJthr`AH`DD{r8d6mWzz&$ExN<=Qa}M?&_(c zH32Px$py^_(YzU~=NDj$rq{94bH+CZ9QQ1uJXjx8n#FZ}z3`sD|E&Jf9zTye==j`W7-H|Fxr z?0Fv-!rFnZg%QRs`E4+insrEHd1p%1H)(9S&*u-_N>>fYbE1wC@s+rA2ciFsKciqN zS0VT>+&sy*U8kX0bXymS>RuJ~8{p6871t2rN(?oq;Nbz)jeA88SX7LJ#2#ndynGw7 z?KegbIrho7lia>?%U^^8y!%cc&;TWi*wRz5Ra{gLXkgeIK^5l3qMx3r3@ z?ySw*K1MgHoS(eh5%kbpY3B#g_mOtqLWRyE#Mb8%0}z#+NP_*6XL)f zlR0(6)LBu5d0K!|{G`(1yZK!l8arUE1O#|KaL*9oV78|(DI*wNRH1)sfNb>w`ha9T zs%|5bpyVN%0!*-iElg@Bpi7F2m=K`gcO%{rHkRo6s?5j(+6EOdq(olUQmGJa=$GRt zOsA_28>Gp>WrnU%@T7v&RilYZ%*Z&t<(PYtMG?qRK(6ZFjr$88 zG`QFH{HG5M{Dv1Eh4>SlO)t{13XA}^bEOwLIlC@MFI-J7NbDDOeHj!3%}^3mLtFXP z;w*+b;-U{eiq?$iIUq9d>PAh`<>J7{x+tzhzeT(?Nco*a+tB?(Vs$tE+`G!B7pEG( z>ui$?j77=_jE)leGut}!6nd?1-U?(q&k{uZc}0!ltUM7rbHWV|c4c`>kaU2JRq|oV zW0U_1oeQKb$Z{X85~MEjYp(7g-9johBFl^%zKGj|oE=5PxfyG+{a2hjP(iufD!u+` z!oSz^<(j?~@{Im$`D_S>jar}^zahz}6$!VeJ|y)SM3oDy!YQy#SdU>i$mYtUR@z3% z;7BWvm1|gN^Razhq5&-`Kk8lpQE3>ZO21Fe9hV*rtvu%Uv^Wfp%s~QbQ2S6-j|w(e8Zf(8}p?`C{GV*XEA= zY4C%yUUnc_I6b!Cf*=1YdW>2M)k(mlF>>?vEmd5fqp!Tms*<657IisATX^fLPR zn?*{q7>axiCg$4o35us@I9X10m_nZGfA?r>n$91L-=y1#?J`*CIa=7*qrN51(%eo|^oIEi1JDWbiEJ{3-j z3t0^BL^cAP@a0}&%Rq=pk@gUwES{7r)~ zx59j>q&pSn$-x*awqT2nH+8bH-S2^uWArcJ6AT{V(aY6_6VSZJZ6$xLlE0|LwGQ6< ztU8L0G3vR%1h`Ya`D55b`uJ9C55Lm%!X~c#$+e-ZezAM+(V~{gs3{GNXFNb9 z-o&4lm06e{Nlny%3oT0bb7hPAyHkiu&;Nl`UXY&uY~!5USI-#kxk<&3TE|p2LO8zd#IVZkXyM`d*sL zj!xe?Bk}HM0?xHLU#RMQrRYC%Gx5Cm#4)^dl1?0Dzin=^?Hh~ynGNS-)TTXg6fbD# z8X1H*j1GG0jf;KhbW5bi%c)=F8BpbQ)j@{{3RlWcgkZzUUw^f<6t6$_mS14dyQJAR zuizZ%^c;e&a;^mTHbKL~R7vp?Kb_%*30vOcu0nOf6f7(j7LI1B6f1-1#H92(c}3GxAHq4Zk~f|W;Vf&%^Ajiw)~ERzicYS+40V{ z_~MO}-Pi+fFUs^-oGEj@b8tq>?ZfGws)M^$#w#kd>i9AI?;n0_Muq?Y delta 5060 zcmZu#e{dA_6~DXPOSpva!;$bSBqaU-BnjpR6au0#l!6)(0Rg4jZtnJSOYe4%-92JZ zdd~Q3s&Zxh%FW8Dz=#NS{DHyh3e^i~siV?C@sCceFlxoZ;MCD}re&=3^S*nVT-q`r zx!c=)?|t9C%C=8WysXN8F;8XFtyS-uNqyV>2PSJ#NUzg-)Xv+z)%!FC^fJ+DPsQrCKQDPa%% zrZnRZiTAJ5qLz67ZS2-iWtv`)b1iAhx@0Pv%J2lPWbuK9zj~upYQDHqrE9o(-B{f) zGkdpNjXqykGUS|a@F#scU#*ob;ox0;OiRThwjr^8I+2}U%g-{XWUSJ03mqIfEJtKx z`1+*<%bdo{UiM(<^P* zta5^=2X$GBL?lz1t*F{Ac3;_~G~=Ip*X)Q~UkFAkH)In<8=M-K)m}3;XQ7b1TGe1qXZC7KPEy@L32!LpY%HQvvZsI8bbn>oH}vE75G``vunqjCY` z1f_!Ev2oexH%vK^6*lkGbW7O$1nVC^qfiMWhxc0)L+Odj6eCr-FQ&x-DgF?PYC1un zU@Rdg;FUL}Zsf!XUuw~;IN@x5trg5(=SX2B4EZA~Hr06Kq=36=duIe>#%$d3wPU2h zEQU~}(I3?{<(FE*(ODxIDNPLm3?(z}YFE9ZHWVV_{g)Nae>l`^3HKi2oy`IhXH|`T zq}EG*PB?!GXLHj}Ib_`vr=+`HblfWjaP~r-Thae5jHClGyB`7ca>DLk7|FO|ni8@F ztnN7%lhv@y6q89wjz&p0kVTu505f$-HKZ^R1g_$glt`O5fWf4+?o~*aD`apQ;Zot8 z!B8_+$iJ!e%1Ea^3Wwr?i}M@U@l~27Y8TeXxl2h0`%w zB!icN?S_#`;En|sM|wSNmF7-ShS2UQ6`4@b8^GyE&_$iYAA9GeK{sJ?BxB7@H#>?N zQNofb8@b@;zebSR;ODQQi-`@r8|@-{jaK>2_u8%C=XKPZGeA<`*jB|`>zwNferf2z44-W2tr&O~A9#eH!gS*X_H7+h zGgk0G_fW6LVGc;l680Wj(172A$Gi0`A%}&T%s{UAlM~K9x0=au-c?3SN!sXt8&{YV zX;@FxZg(Yd6z1Mw`O;^n5bJ&Xs0%SNo9`hPKvp4KDJv|Sr=#LIVOe8wSqNV&FX7Oj zZS&pLJ%V975UiL$%1T zGsgz2;wk`|jQ4}AY^uDC#IX5r_%L@u0mZ$#MQl@}CxAJwIot-u#e&OxS|6tFlFq+5 zgvDIo+$7G=R^VJ^UIKZE&m8NbKJHTtqKeLQxdbDZJnW>T=!Ol|0RzQJ z!!@1Hwgxv21kpjlfW-Rkfksjkyhs4E75IKV@qa3ADoIe3Cr%6vv_~F^`}0NF2w&^WcBi&Cf+Zs> z99YffOCCXKXE20t%oynrQmVl~(;3#k@dWC@zCbN^%f)!ro(Popc zU}vUHDzk!<>w2J9`Wfr4yF4`R4_^_9Y;J|8D%LuEYI=SBQJOb)%w=Ma2Qi95+Zw1- z3pR- zjCGBnPwZAc#}F)#k%UHqJS7A`kU)>cHJblkZ_rpVX|{>6XNo2PCT{7K_q&wAyizEc zTbu=YP*i+SX zM2@pjBE}M)s$oB$ao;k$sOICm2nfMYi`!*5Q7#y2F2eR0wSsp#z(A%rm7{nkfQ;4802kIM_yFr5Vjb0ZPyblG+O~&Ay+p zI54i2Rc)NPbfuaVpM8kKSbX-uW)5S@Bf6ik>vfJRpIoZpUL}-zm^pnF$gP_11B=QR*(+fbf1 zvVoHoG`dHYHy5ITix((;&;evBE}^&4iJ%4;idlh^n!y)z%vc)k zc422J#4Tk--54vm#h4W;)- zn;~mH`Q-R*NmAFEiWTF02jAaV`;Iq$9JhSGTpnkgGR$K5!I)QjSNUeF+WB3_*SN6i zh8VZQ_z#il-R5rL*ejt}h#s_Pn^jVKk1GP=k+_D2>oc@@@5b1XfK zn=`jpR)+3;gT5+oSL)TNxNHSeUo^A28}GiVq_NCP4lRg>A9e~0vr(55SKSMFBd*%U z-o9}Xz5qG=kkjC%a@0~X=iEid)f?{DLl}KD`4D;mf^KmDqJZ{v5gi!0fc6Y#%*Z&g zf*S_&6l%(b&PM|)4jk6bf&RMXSTaC z0<8UzOq_M#219htK-IEjkgcy@>|ewlTQWr?Y_LerR*}A*7^t}Ey?}o&yQcF9exK|7 z-N4JM9tf3Zc31m++aLFx>1bgamt5<=3{Ot?J8aR0jqYPRH{2X3Eu?#3$;QU9?2os! zO=)xX1P;7^di$P#r&{Xv1mgVV>n(K*BZ@!A0 t_i$ . 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{No See In Future}: Assume $T_i$ is an uncomiited transaction and $T_{commited}$ indicates the set of commited transaction. A read operation $b \in OP_{T_i}$ MAY ONLY see the writes(changes) made by write operation $b$ that shares resources with $b$ AND also is subject to one of the following conditions:\\ +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.\\ -\hspace{7mm} 1- $a \in OP_{T_j}$ ($j \neq i$) such that $T_j \in T_{commited}$ \\ +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$.\\ -Rule 1- if $T_i \rightarrow T_k$ and $T_k \rightarrow T_j$ then $T_i \rightarrow T_j$ \\ +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$.\\ -proof: Since Def 9 ensures all operations in $OP_{T_i}$ precede those in $OP_{T_j}$. \\ +The same argument can be used for $i > j$.\\ -Rule 2- \emph{Committed transaction Should Precede the About to Commit Transaction}: $T_j$ "commits" at instant $t_j$ - $T_{commited}$ denotes the set of all commited transactions at $t_i$ such that $t_j > t_i$- only if all members of $T_{commited}$ precede $T_j$ (hence they should succed)\\ +%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$.\\ @@ -105,7 +111,7 @@ The same reasoning could be done for $T_i$ and $T_{i-1}$, $T_{i-1}$ the last com 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: Follows immediately from Rul2 and Def 7.\\ 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$. -- 2.34.1