ࡱ> C@ABn"5 2RXPNG  IHDR]X7ksBITDbcPLTEJJJccc{{{ZB9{ZJsRB{sZ{cεsZ罔kR)!ƽνskZ{cƭkcJƽsksskޥΌ{BB999111)ZZJRRBJJ9ΌƌZkkRccޔ{ks{{s{0@ tRNS\\bKGD IDATxiHׇDcdGhhY@cbsNg_L:Uο;Յ~_~_C' B-`&25o+fe\m9HλfІ@5Ǒat#u" f l309cfFNn믇btLvG2֒D'] S%ڃbȆR1잶,O%2wSxU{TTšDyxo. Je>Dxxeѫ}>z$\ j?ػ4T&66G7nN:'4~m-ҶaqyKge`LM3ZVǫ96:g2<wƵ_=WmFz\lC} D~ݍz'`~ }wdr sh8\6ۿT&iqURQd1 %Ƀe=ߦܯ NFp88vM{]>cﱁE_,~ l'lM^WH6D. m{B?L/CLO ëC;£VAGz0-߸혶TL5nmX'eF^2ǖ#}ʚd`$:+z 7Ia-'t6t~qL^|6d/5۲OMc泟LNaGUp#F.:ޏxwLjweCItxL##,˯\Q)JW>z` l'z(Grn\ G0,KX5ďjS"pNOx :=k(TnFU#̭yk/-a6(5R?X XRkCcI#ݞktZ1_]]dN¦A;]FAMmܼ1g>;E':H'<&.}tye齛t`C[:DIrh^0P@z=njjZۦڑ zz?*{ 8L{dӆ@ ^†Ƀ30t؅yq6}NAa q} c:ڑ =+hg`GvUtt41 *L0j贱,wʤzo`Z5qG-nKhﯨc iSрz:=;zuN[%=O<ˆ-j[trݸ n:ƺmŧ<8<>=TX.yѥmXb548֛ߏF< FaS îFSd.fwrNJMK[S{H\!((EV9m#E/FCAܳv3DMllp=Y͊q9κEK]ĸ\n$X˼. pFQdOM@@p'zEt vsNdV|:Z >sGQM/d'>Ϲb4++[L 3 q\{&]aqK:ai貌&d2DW<1ILNLԛyj9Lj >J|b=ZHFB[,CLA7Lգy04l04&@, ,9- u 1,=ZwglSw}Z?lbuϛS`^.h9j0,afLЌ : 4+oWEnؙ+g'D/:qƾ 6xi`9kj&kX9Иjj&9];C94-caqE\ȫ%֦)(7``I!*"ؾ6(~W7*s E:*0}k߳ouxԘ{fC @nYtNXW'(*ÍhCճ`H1_f,nN{lx^e:QmOuW@S]Q= js=|Q(lA{\͂ʓJz&Rh=@=`z0Eo+4vާ*pUR{y|cr COca`L0M5}"Wek`2x4բIe|$s,$;xiLQ0A:m*5: ;hQ_\Ҁ4*?_f€8 #ا pN93Ӕ&)ׇŋqtiV631PkH[đ:D=}KODaq}#HA,ߍn,ۼB]TI"Br%ɴ slR|]ЊL~B$.έJWjU$U9Y t#[\s"K?.f:-n\YMyp]Fʄf=8MوQFt͇ԟ%KU]Ӣu>a*҆ԝGXzl4բ# PU >mb:'W[~_ Vz~ "6*syaqѐmVD9*wm+Q͈UЧ9j0Y޸]-55|_;(4 ᴞS;E@{ZjbQT:6MT|lCĪ'T-W'+b% wt0\Uh/)f/ yfE7,V/sPkH(1Ao_t+% /"R=F*' P.DL.t%臞"' fN>Tv" mn¶0xNU_)`.rVUҡ82DXljv2f&] ?M=I`_T7m*g@"GcA`r>Q8=Ԭ-9yMTAbXn" *{vqft,B D t!끕yc`᭼un^K.UF+#R—x>6{w7re j*h/Jm~Y2#}SI mQj [l1zʅ`V!:>"[=WV2P7*߱7ӲINkajk& c@<nE `|fka]dj<:CGr7U(ŖQ`hoUmUȶ[k*}@h,kř#B1Gұͩ 1?_G0ɍKE&@A=Ibw }Zf":ՇTNϦj4g]4k[.`Uғ9UTb;Fn{F `l{}{CuJ&!̴ \ ~_YT DLjdj}{Wbl@=-1,7޲Jݪ-sRPlwQ0y Pj^࿱(3yzrpV%IPѕS~"Ӑ2&yz+ƍa.ˈQpEvo|T7"hSpvpcdA#MS?xQpKRtX ?FL[*F?|tzޡ[]b* ߡs[;NxdE2LJ"wZ'd\Hm^~۪mbR~p^F]>,h[S\9Z87Q<;;0:\tQ ђ{=9V˺Κ,Y"bqKth.ZU_Ц,Ofk*ogNi}utF|DeN[Rtꦯ:cIuv$l]ʐOh AuUf9S^\TdMr74quUp]ϲC^@D!]{ѡwz_GG1nƚ*N㍱qh`jZ!,<ڪ.k q]zsK+X}r}]t'.AGh}QTl&.䗵NR=v|M!*aNC֧r/:NnmQ"*pZEG9PR~4@mBTsM̆DS9\lUԀTQlKR y0ixbg¨rUőW3M>5TbNڴYh5GЛ3x{0L>2SS8I djf@m0o[P:woU 6524?OmC_7 |d4UUQͨR<@'= Ƶtz,ҍ#M&~wuJnיo4=.^&i7}7 L'F6e XQb *oއb{Rl Jܾ9]KzޡwߍI-܃QUb9T6[la AI1N/^,Ӝ`E;MB`LDl<f992㱃I.6<ȖGA9ZQ8a]O!)`z%2f)r @2*r|g !Ip4ӅϥKt5m ַNly-UȤ-*>/{rN=~ng3)K P?IỉZlf'UNN˕Á{xpvyRj&@&l ~"+܃@MogC;G7D=tZGa#DZ)e&Uz2t64mU68#7TQt^!I0# `BB"o{BU0 tx%~6ak0Fs_09\ZUh1 ˕P.C=w*qIüf/%8F15v*g{v )y Oз='09ظ 2!lG;嗁$&>Y*&'{jrf ](_YYJ[eo(Cr`?dbsXe >c{5er}6p=>)^IDAT[э2{}c!8prtvfHm9 ?B3Rn>C04;qLUӐuo(f Z773yeRv{wc̛R8]7ӊx.ڝqM՞kpz\oyqSB~ҝ&;C?&C;C<n#IENDB`nka <rky& V CDдk|WP0se&d*'> '[@xVK@'R=oj@iCx[-i˩x ОQ!#W'?ԃ?TDe jf?)@“]Б[jUT"mW̟@%wЯsOjMشt@w,UW]z.(5v/1z &">'vB]P!u4~@t̅'8:ݚe<{*f*x2=IEIE˒v+Gs2bW +u^gW_^ q#?ZһVA!sҒ.  Z j> >R+Wzh,!Y$J#igy:PhUɮ;Lӕ =\8_\U-/b-XTp^Z ;zbw+cԉbX{hx`/Tjk UJ\ZZV*t8q1)K͇27B o&E>LZ&[T5UwX<"T ̯M,lz5P@ ]W)󳣭gڢF,(W8"1dTbʦ/mz]amWG׫+f&gj.^zޭ0ΗCSS3k׮y͚5,i .v(.+!7eV}GgP-VU05v,~e:]]Th+bQ6 ﲐ8<<84rXSWkլACmظӰipڮ?OEŬ,!~RUOza<)hGvy6|#C#^ff+m|rҌܛ/Do$Hݾ}{Ϟ=`t0Ifzi=4S5'e+ŋ((`"B/_ UU|wg~v?Ilbe @(< աobZPC,[ϣ!u6 ط};S@ MU/<,d 6i#]v /=OWōCTb3ot7n0B`#|g~ʕO?g1"s:u*@(0#޽#݊ZKe8aI4(9exSc)isE`2iFS Uە%FeYWpL*i ]C@va۷OEEV#yH/GPTAsl_vƍ3v6:@0|7/CdL&@CGM!0&t[l8."U@ q-g.k-aQC.t$l ;4г 127&y]l.%U>R/wb,4A^Ҹa Za~1kxr9:dW 3/TO+haMp4`UWיs aypCY?ԭ#%,^ + :tHg<Xfz67Qa/M4D ?!|斂ql֘6Pӯ߽˯aL]30 7 |ŏte|Q'ẄX0G'sd8-yY~I$MzzAr1PR]24l%MM/;i*K QC4Mc*G̼_jUu'W!QJ1)wZ +!C& Ȧ xݗ/^Y3fu(u,mwhLꢙ҅EeD23UD1\ ZJB *woDse^XE4}0YV*_2WG\6׷WW !qRFփ~>f &w߽t\SlyaH'Oة=AKwJ.mL^W1FItlwxo{UdԼC^j@bTXr<:7Vy)#-_v3裏xmڅ_x v̜}i0=~)7r@y9 2G(VX-ɔϙb t6x|q3GӥlB7 A$0âna xŷJ3dUK|g)-ˢ js/\Caf%fjPuv֏+L `$AT^ [TZCbЗYB$4G3웖6]},x0 )|Nb,ffȑZzEH[u?渡؇ۄb`|믿=ty';3cG]D+ّ/ၼ'/YT.BןO>oE$</&ލ/RT5dݱ- (P%kU @ށN fE+ePz\lR %*0=-80 }*$S "\ ]b+Wخ^lOtf*iReʖ49BLC~UmῚ`(ﶶ6댡H{Fv }EpY^2dH tC(R#$sx" 7lΌ~ 0Y3" cslݜw%[mC*'zf0NSCmڏg29x&2*r]:ˤY_ &0wh" Jv'Y٩ zeS+мE3SӟMQNkLBc1;2_W^e١}~5j^Wms4eƜ +sř^&LlaN"I%C`a :WyظsbO`ZjO1lZ*`&{ɴ{m@3GLeI>Є掎AO& y `>[? x:3cisLG1ՀM}If5TWC(y i@ QNWy1YG+a_y"بt}DWj!ftT_BϒiXڪK`%z@h0Ç9sց,WQR烔5yi<`¾ىV_~;F3J֡f֖|"Zֳ /Wl4B^ 0V+ZZw twuv  @ÂXHET'X~ *g ɐ/G9 RyU aB\ 3vHhr`0A]&5Ӱ{U1f/ V3 #0΃Q`UHFd~(b %1`3 ḧ?fwT/O$bMG$؃`E1E5 GReHeCU0V{t0XQBjcytȏ\`Ml[j%D>X,/vU^mDYS&)B[hdI- PM8e4DTuyn@|.hEL$vK)#)d1&'T<!Y ߺ$['k=]קo.?hQ@e9=^ =[v@y=_RVhsg7F]4_%5:}iuXv6q a"WKb;Oo'oNǺʌV-“s &1]H,I? 2sX cUq.~E})U"DD8D&ųPQ_kAڞ%1x 5VsM]):@`,=&e P0{Ÿ,ܽviu*RV6X|W,W=Qm-Kl.3+ }VΚv$eJ`05U\m}CI//Y n*',h[T8{!MI&Z[z{dn&jVIʪgB xD_b0at˩ٸ>FgDHT1xJljO6HA۲0Ѽ6/ Y|&tD%.O ׯώ2TUET¤Tb<դeJg$Д0}` ]M۸bhY90F@M9ط6Xl`X^̜L ~= 'ea#̛Ԥ6i Լ۶-}l SP'/N'ڸs]c*=Ůc!+\ SDObLkZ[QF~鬒Qu 'zSKi+E񐌅0xVr$TF2f26xp|U,b"f-/h={Q?z~#I_!I L# _f&zMVB0hLx7ľNɉ=Ud?T@ЙIf޻T]ztc-.5 w'"@ܸq.lSWokX QM85pJWD gϞ%Cxh [: ͰDUtPQ>YMYH9z8Y$ M3wa0+A;0Յ45jKFظMeTJ2аy;ݪkpM}qho6fx#xdJ@XVh{67e%@/-xۃoV!rބhd~mafŸe=!SUhRԃGGޔJ[̪fdܚuwUpIhHNoMsjg5e!y)+a_Bdž1qI=!-Ļ<j\Te_J94Q1;[Ӑ`XA| )u\0FBABDՑ׮Z%*,,̋bBU-jWW{l=zv'}#-#eDִdDb݅܃=2jnno=ܴyg= x% =x]&Td糔~ne]K.gr_$q,PRaֶ0go a<jie ر[l/^ e1y#ݶm;==0fn_υ7޽s~t<]˪m0=O~[[B(`LďvGXI³XWN-e%,P 6l_#M'#0cɓ'YåOx"`<|xn~{ulLa=\f|6CG%kƦٹlT m-5 Z*TUo )fw"J~ΰ>ovv>R ELb tlF <5F]lvNw6 ͥeWؘk_%K/6fXh.47˸mL 1Վ L7o2OR:: ΦzRv_tH-=Qut xSJIL4 Ge d/kBJV%Z²Ch'@JY-+ÊlK` * 3jbQlf VxRхhDRVƐӵ+:[ϫiŴ6E {LXuEs=M!*.iUAwR}V5mM3n UZa#nVZdJ-g71F5Yzcx%c84\p {EH䩻P'GՃ}@fJv޺":t%#͋`44 $nl J]3]Y.ؔ]yh M8bSlF׽:/SFPcYnF %Z\cyZ^yO/CLXUxXR:*fՑ>(J g>V'>\` ?ިa1.X%u29Dx+bvهb_Ly}z\4eG/^Pk c%^!FI/hgΜѲzVkEhsŕL|66Y Vd6w5-A~ BEXnR6x>Wm͛5B=7~KhnH#X2g>YBFg 4w704ƛ ;LXXչ}}},{ ;Yy2вQxn=ǪܲNdUilhy|_e8Ua`93 ¬]W xPP*_ ki|hcڳQ1+䞆,NEre鰱;>~0;D#1iTlnn=8xSt#,0|+S~x}E3<5.\?|wU^T|֩NtmBqtSrqW.ʮfU-dG'~h7;O'NNy),MV{;wFcu*=,@Ҧ EӀLwcbg1T@ӃVX{$-a)P2ERQ[_M-- t45fU#81LLAU{f$ [\ v1MSZ|:=tUj.Cx[W:46P=lx3py/,7XC*t(dU6,̇i*Yd'SyjoQ;s #6҇+YgxLHZ* J'nScscS tRs s3@XP]Ww O?k]ټ0zRR*Ru͒cEQ|kB ů&Jl݊Q fu9jY*S5jX]ho*ˌ 0c ,z[@ss455  #ӻC`e%Z h@2+W8qŋ?:t*k_m%8$+ Z`ޭeK߳/{&&Px †h5ǂJCV$>331;2BWZ]U`ۆGb`y[yEevvzpkꞕخp-4mffC(0fb'qguJ^ddd M@ӳM@s0 7]M =£kC0ڥ'+o7;;v  hr6=euynX0K/_+F-(Ĩl@ᇨS#/OU*Yy[n`7F0%!kp&2tlӠXYyfн3)Fs}6s !XI!eeƣc:lu!Xʡ(U8M)`9roe0Mv+q9v)|R1㔖ŵǠrxKA&eyZj]}Щc?1W-em@b1g!~}I8k!Ћ.9~ZvTE O)dB]C7بG4c53l2B |r15X b*%KcD1N+@e \:c/=WePCPW'Ør yo޳FX]Kb*G6q@EsȦ=LUc-F\W'/>LyhoǤKX&r[UW4cx <`'HN+f gͪIwdX?2oS!4a#!'H>gc^=Mi"Ϟ=Cӑ?<}tL\ՠx&:^~^U"sH?.Fi}X^EX #ՕxFm\r|<8ocM<.B{ЊAMcܚnhAW0ļAvmd]sC`B!9/~޺SNݽ~9D r*܌'%٬cώ ~!IS,y_ON5YLJZ}sgΜuIFj%H:1S!6/\^D-.,eWLA4xbIG O7lXuCw:ݔQŬ&L,ld[<#f bPKDwB> -Z@=4:G|Wx!MQ1J.)l9%$oܘ<S<}I!+(gӣ*_TLQ36)\U~Vzʾ5T{~tu޵4O#ByVxʯ$P RH+)|Qr@p1W-CLx ,a,d8!X&Eo> mެ)nJ urWW[5Mi@hꕼgPL]Qkޘr=zKv&褃\c:3 *q+KSZ hƀ<jAS+mטf#6OOE 3_*^Z״؊2W;x]x$=jsc2F4 XR,*o7n\u :uJe| Uk9w- on`V+o&sY5!!)I D}9x~24tSwE_I5 xbxMԑO$y,}'ig峉ʅTRzZU[_ M?d xA!yoGFfguH',ra|9Mh%XbvP8[ ~ A8,/z{{Ubj1֑_0ZΦق/MY aˮtO?&t(ip6M\kh54Jw V.u-sOd!eպU7+!_vzB)b=*Eu,ڡxJb 8 \LLPx1|UGWM]å{\zwswtfn:z.s $Gl-<ʑEss3W6ox!LL{Ӵ_(/V/f6إ۷NoX3>9-_+-JTS]U[]un۹gO<}?lrѣʶm}s3J{ʚ⚞յ5k׭~|Z>_f%V47 7j ƃ4`4b W!!e! :-k^qm 3ͽ5P_Ir?~v%)߽!u5F7;7?X¹mUK 󭯫һiR-nbtf^{;~ZdžCpV Utqn1WudH8;w]Q mWfuwwGbMoB<\Pb fj0EɡЪv^Q` ̼rѫ2xY-(%I71'ay<yY)"3[8(n }>90Df&y4uu3RYz*z`,śMw}j|\?0 ЍLc Y$d'qEӧU*!7(%hd{.Ħ[Xg۟GqbJvLΪZL/w}V>r:oAC#nbq?N,Xd\q+XPI `sP_օ ^o2wB**-hdCD(6 v%6wXF£؄8K&kNJ2ׯٳG}LI}f#>o>ovrʸ9Xw ` ޾uˬhtl&Wr3AZeNvʹubÚd^O:>0j$Cczrw13S֑ zTCݗ={z.>3nhjG}Kҁrm("y^P4i?.m慆 C憖'MO{Xp7PiH4.PY0x/KT5FD5@׃s@= = z)r?.e+Vbg P/GOvDg%K+d4# H?BP'7m˼!QӼvqd($仾\S'KC:mE45^Q59x|zLMGדqGchbtQ:[J2LbgM^,DHD3TbsIZ:fGd)A&L7ӯ a2ݕm}yC,")L+LX9h G~C%FF'\{ *jyWW͚u/^*K(L]p31S *|Ցk=XD}) 9 \C(?~JR_ziImljM6a;)Y<{Zڬ\%:PM ׭$W6F ۝nƗ6t]CLYt2Ϭ!mFe7^*3J.\"k`V|s T(4^*61i^34ofxú 9{,OnjsQD[E:so]7qBV5[RyscԘM֑CNΝ|VBؽCiRBߔfYG  ro S' )fR SENTj?i(CkPtj), rola para trs ao evento 'e' tais que RCVDi?j (e) = SENTj?i(e) , repita 3,4,e 5 N vez (N o nmero dos processos)  0lF3fP/0 FfPj0 FfP30 FfP0lFfP ,5  PROTOCOLOS R  Asynchronous Recovery" 3fd 2.2 SYNCHRONOUS CHECKPOINTR tentative checkpoint : Checkpoint temporario Um candidato para ckpt permanente permanent checkpoint : Um ckpt local a um processo Uma parte de um ckpt global consistente 0lF3fd90lFfd0lF3fdE0lFfd0lFfd0lF3fd9E   2.2.2 SYNCHRONOUS CKPT ALGORITHM!" 3fd! ! \Cada mensagem etiquetada pela ordem da emisso Labeling Scheme last_label_rcvdX[Y] : o ultimo mensagem que X recebeu de Y depois X fazer o ultimo ckpt (tentative ou permanente). Se no existe, contem o mais pequeno label first_label_sentX[Y] : primeira msg que X envia a Y depois do ultimo ckpt (tentative o permanente). Se no existe, contem o mais pequeno label ckpt_cohortX : conjunto de todos os processos que deverem fazer ckpts quando X faz o checkpoint. roll_cohortX : conjunto de todos os processos que deverem fazer  rollback para o ultimo ckpt quando X faz um  rollback Y reiniciar a partir do ckpt permanente apenas se last_label_rcvdY[X] > last_label_sentX[Y]20lF3fZ0lF3fZ0lF3fZ_0lF3fd2  y  Q  aD    2.2.2 SYNCHRONOUS CKPT ALGORITHM!" 3fd! !Algorithm an initiating process takes a tentative checkpoint it requests p " ckpt_cohort to take tentative checkpoints ( this message includes last_label_rcvd[reciever] of sender ) if the processes that receive the request need to take a checkpoint, they do the same as 1.2.; otherwise, return OK messages. they wait for receiving OK from all of p " ckpt_cohort if the initiator learns all the processes have succeeded, it decides all tentative checkpoints should be made permanent; otherwise, should be discarded. it informs p " ckpt_cohort of the decision The processes that receive the decision act accordingly  0lF3fP\0 ZP0lF3fP ? 7\#   I g 2.2.2 SYNCHRONOUS CKPT ALGORITHM!J! !3. IMPLEMENTACAOJ Soluo a implementar :  Asynchronous checkpoint com varios processos (mas sem comunicao entre eles)*JPJP h 4. CONCLUSAO " f3d  Os erros podem ser corrigidos com metodos de recuperao Os ckpts sincronisados so mais performente (limitam a quantidade de ckpts) mas so mas difceis e custam mais (comunicao e sincronisao) Os ckpt assincronos so menos eficazes (domino effect) $0nA̙d /h !"#$% & ' ( ) *+,-./01P ` ̙33` ` ff3333f` 333MMM` f` f` 3h?" d"@,"d$?" d@ %  %" @% ` v?" dd   " @ `@r?" d@d   @@``PR 1d 1d@1d`1d`r d   @@ ``pL1d1d0d0d0dL1d1d0d0d0d  4(  X"  0G ?JXB  0D˽4B| ?`d  < A ?  d  <ffA ?d L  c $ ?/'L  c $ ?'  H  W  `,Cliquez pour diter le format du texte-titre- -  B  W  :Cliquez pour diter le format du plan de texte Second niveau de plan Troisime niveau de plan Quatrime niveau de plan Cinquime niveau de plan Sixime niveau de plan Septime niveau de plan Huitime niveau de plan Neuvime niveau de plan/x H   0mXo޽h ? ̙33 Default DesignV ` ̙33` ` ff3333f` 333MMM` f` f` 3h?" d"@,"d$?" d@ %  %" @% ` v?" dd   " @ `@r?" d@d   @@``PR 1d 1d@1d`1d`r d   @@ ``pL1d1d0d0d0dL1d1d0d0d0d x (  ^"  6GA ?MiL"  c $G ?  ^"  6GKA ?* xJ L"  c $G ?d L  c $ ?[ L  c $ ?   HV @6:  `,Cliquez pour diter le format du texte-titre- -  BxY  W  :Cliquez pour diter le format du plan de texte Second niveau de plan Troisime niveau de plan Quatrime niveau de plan Cinquime niveau de plan Sixime niveau de plan Septime niveau de plan Huitime niveau de plan Neuvime niveau de plan/x H   0mXo޽h ? ̙33d` ̙33` ` ff3333f` 333MMM` f` f` 3h?" d=,d$?" d33= -  %" @% ` v?" dd   " @ `@r?" d@d   @@``PN1d 1d@1d`1d`r d   @@ ``pd!9d 1d 0d 0d 0dd!9d 1d 0d 0d 0d ^V (     H  W  `,Cliquez pour diter le format du texte-titre- -  B  W  :Cliquez pour diter le format du plan de texte Second niveau de plan Troisime niveau de plan Quatrime niveau de plan Cinquime niveau de plan Sixime niveau de plan Septime niveau de plan Huitime niveau de plan Neuvime niveau de plan/x B  s *޽h ? ̙330 @ B(  ^"  6G$ ?R"  s *G ?R"  s *G ?R"  s *G ?R"  s *G ?R"  s *G ?R"  s *G ?R"  s *G ?R"   s *G ?R"   s *G ?   Ht    ,    B\  '  , <   c $޽h ? ̙33F   0 % h` (  L  c $ ?/IrL  c $ ?0 I5   Z( ? ]   nZ5Pk ( C ^y   Zl6 ?7N  jV4Oj ' B ]x<  c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++F   % h`P(  L  c $ ?/IrL  c $ ?0 I5   Z@v ? ]   nZ5Pk ( C ^y   Z ?C  jV4Oj ' B ]x<  c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++F   % h`(  L  c $ ?/IrL  c $ ?0 I5    Z ?  ]   nZ5Pk ( C ^y    Z ? C  jV4Oj ' B ]x<  c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++F   % h` (   L  c $ ?/IrL  c $ ?0 I5    Zٺ ?  ]   nZ5Pk ( C ^y    Z ? C  jV4Oj ' B ]x<  c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++F   % h`$(  $L $ c $ ?/IrL $ c $ ?0 I5  $  ZF ?  ]  F nZ5Pk ( C ^y  $  ZF ? C F jV4Oj ' B ]x< $ c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++F   % h`((  (L ( c $ ?/IrL ( c $ ?0 I5  (  Z`5F ?  ]  F nZ5Pk ( C ^y  (  Z>F ? C6 F jV4Oj ' B ]x< ( c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++#  % !!0++,0!(  , ,  ZfF_ж_ж ? =  F nZ5Pk ( C ^yLB , c $D81?_`LB , c $D81?  LB , c $D81?  RB , s *D$?V2  , <lF_ж_ж ?U X0d Z5Pk ( C ^y , <zF_ж_ж ?   Y0d Z5Pk ( C ^y , <F_ж_ж ?B Z0d Z5Pk ( C ^y  , <F_ж_ж ?8d [0d Z5Pk ( C ^y  , <ؓF_ж_ж ?n 8d  [0d Z5Pk ( C ^y  , <tF_ж_ж ?# 3b [0d Z5Pk ( C ^y(  , <F_ж_ж ? x1*0d  Z5Pk ( C ^y(  , <ȻF_ж_ж ?3  y1*0d  Z5Pk ( C ^y( , <F_ж_ж ?; 3Q  z1*0d  Z5Pk ( C ^yRB , s *D$? ! RB , s *D$?Vx  RB , s *D$?   , <DF_ж_ж ?   [0d Z5Pk ( C ^y , <LF_ж_ж ?n 5 a  [0d Z5Pk ( C ^y , <xF_ж_ж ?# My b [0d Z5Pk ( C ^y , <8F_ж_ж ?I [0d Z5Pk ( C ^yRB , s *D$?V( ( , <$G_ж_ж ?y  x2*0d  Z5Pk ( C ^y( , < G_ж_ж ?I x3*0d  Z5Pk ( C ^y( , <LG_ж_ж ? .  y2*0d  Z5Pk ( C ^y( , <G_ж_ж ?;  Q  z2*0d  Z5Pk ( C ^yXB , 0D3?_`XB , 0D3?  XB , 0D3?  Xr , 0$?M  XB , 0D3?   ^b  , 6G0*Hc?  # !, <%G_ж_ж ?    Roll back 0d  Z5Pk ( C ^yP ", H0G_ж_ж&$?'+ "Y ainda no enviou, mas X recebeu.&#003d#3 #Z5Pk ( C ^y2 #, <d;G_ж_ж ? :  : Orphan message&00d Z5Pk ( C ^yXB $, 0D3?_A `Xr %, 0$? XB &, 0D3? j XB ', 0D3?  XB (, 0D3?  XB ), 0D3?_`1 *, <OG_ж_ж ?d6 : Domino Effect&00d Z5Pk ( C ^y< +, c $޽h ? ,, , ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++!  % P((03(  0 0  Z|rG_ж_ж ? U=  G nZ5Pk ( C ^yLB 0 c $D81?_`LB 0 c $D81?  LB 0 c $D81?  RB 0 s *D$?V2  0 <G_ж_ж ?_U X0d Z5Pk ( C ^y 0 <G_ж_ж ? _  Y0d Z5Pk ( C ^y 0 <(G_ж_ж ?B_ Z0d Z5Pk ( C ^y  0 <G_ж_ж ?8d [0d Z5Pk ( C ^y  0 <G_ж_ж ?n 8d  [0d Z5Pk ( C ^y  0 <̳G_ж_ж ?# 3b [0d Z5Pk ( C ^y(  0 <PG_ж_ж ? x1*0d  Z5Pk ( C ^y(  0 < G_ж_ж ?3  y1*0d  Z5Pk ( C ^y( 0 <G_ж_ж ?; 3Q  z1*0d  Z5Pk ( C ^yRB 0 s *D$? ! RB 0 s *D$?Vx  RB 0 s *D$?   0 <G_ж_ж ?   [0d Z5Pk ( C ^y 0 <TG_ж_ж ?n 5 a  [0d Z5Pk ( C ^y 0 <\G_ж_ж ?# My b [0d Z5Pk ( C ^yRB 0 s *D$?_g  ( 0 <I_ж_ж ?y  x2*0d  Z5Pk ( C ^y( 0 <H I_ж_ж ? .  y2*0d  Z5Pk ( C ^y( 0 <I_ж_ж ?;  Q  z2*0d  Z5Pk ( C ^yXB 0 0D3?  XB 0 0D3?   XB 0 0D3?_`XB 0 0D3? j XB 0 0D3?  XB 0 0D3?  XB 0 0D3?_`  0 <`I_ж_ж ?I [0d Z5Pk ( C ^y( !0 <h0I_ж_ж ?I x3*0d  Z5Pk ( C ^yXB "0 0D3?  Xr #0 0$?M  ^b $0 6G0*Hc?  # %0 <4I_ж_ж ?    Roll back 0d  Z5Pk ( C ^yN &0 H<@I_ж_ж&$?'#^  X enviou, mas Y no pode recever&!003d!3 !Z5Pk ( C ^y0 '0 <4KI_ж_ж ?0 o  : Lost message&00d Z5Pk ( C ^y< (0 c $޽h ? $0 ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++  % p 4f(  4 4  ZkI_ж_ж ?  `}  I nZ5Pk ( C ^y 4  Z${I_ж_ж ?  `h I dP 4t4 t 4tc~RB 4 s *Do?p ppq RB 4 s *Do?ppRB 4 s *Do?v RB 4 s *Do?P p LB 4 c $Do? `0 LB 4@ c $Do? Z0 <  4 c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++   % 4,8(  8 8  ZI_ж_ж ? w=  I nZ5Pk ( C ^yL 8 c $ ?0 o X2 8 0f3$?i %2 8 NI_ȯ_ȯf3$? 1R Z5Pk ( C ^yX2 8 0f3$?N%2 8 NܰI_ȯ_ȯf3$?   2R Z5Pk ( C ^y%2 8 NI_ȯ_ȯf3$?K  5R Z5Pk ( C ^yLB 8 c $D$?FB  8 S D$? i LB  8 c $D$?+LB  8 c $D$?h   8 <\I_ȯ_ȯ ? 3R Z5Pk ( C ^y  8 <dI_ȯ_ȯ ?sV 4R Z5Pk ( C ^y 8 <I_ȯ_ȯ ?Q G  TR Z5Pk ( C ^y 8 <PI_ȯ_ȯ ?   1R Z5Pk ( C ^y 8 <I_ȯ_ȯ ?r h F1R Z5Pk ( C ^y 8 <I_ȯ_ȯ ?3  Req F1R Z5Pk ( C ^y 8 <J_ȯ_ȯ ?jd   Req F2R Z5Pk ( C ^y 8 <J_ȯ_ȯ ?   F2R Z5Pk ( C ^y 8 <J_ȯ_ȯ ?nM  0rEspecificao do estado de restaurao Representa o comportamento do sistema O circlo representa uma condio Um duplo circlo representa um  recovery point uma barra representa um evento os arcos de entrada indicam as circunstncias necessrias para gerar um evento Os arcos de saida representam as condies depois do evento O grafo capta toda a execuo do sistema Este modelo facilita a compreeno do  recovering a consistent state .'RRR Z5Pk ( C ^y#2 8 N.J_ȯ_ȯf3$?76  3R Z5Pk ( C ^y< 8 c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++   % <^(  < <  ZLJ_ж_ж ?   J lX 5Pk ( C ^y <  Z,YJ ?  ]  J nZ5Pk ( C ^y< < c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++   % @\(  @  @  ZwJ_ж_ж ?   J jV4Oj ' B ]x @  ZJ ?  ]  J nZ5Pk ( C ^y< @ c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++   % D\(  D  D  ZxJ_ж_ж ?   J jV4Oj ' B ]x D  Z ?  ]  J nZ5Pk ( C ^y< D c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++   % Hb(  H H  ZİJ_ж_ж ? 7]R J p\5Pk ( C ^y H  Z ?  ]  J nZ5Pk ( C ^y< H c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++  % 0Lb(  L L  ZJ_ж_ж ? , J p\1Lg  $?Zu_ L  ZP_ж_ж ? =  J nZ5Pk ( C ^y< L c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++@  % 9>1>PJJP=(  P P  ZxK_ж_ж ? U=  J nZ5Pk ( C ^yLB P c $D$?sMLB P c $D$?; v< LB P c $D$? v  P <d_ж_ж ?\ X0d Z5Pk ( C ^y P <4K_ж_ж ?M 7f5  Y0d Z5Pk ( C ^y P <`K_ж_ж ?< 7f$ Z0d Z5Pk ( C ^yRB P s *D$?%< RB  P s *D$?; P RB  P s *D$?{D RB  P s *D$?3 tU RB  P s *D$?U D RB  P s *D$? 2 < RB P s *D$?3 D RB P s *D$?; 3 b  P </K_ж_ж ? Ex00d Z5Pk ( C ^y P <9K_ж_ж ?R Ex10d Z5Pk ( C ^y P <CK_ж_ж ?  Ex20d Z5Pk ( C ^y P <HK_ж_ж ? d  Ex30d Z5Pk ( C ^y P <RK_ж_ж ? Ey00d Z5Pk ( C ^y P <tdK_ж_ж ?%~ Ey10d Z5Pk ( C ^y P <|nK_ж_ж ? Ey20d Z5Pk ( C ^y P <rK_ж_ж ?P^ %  Ey30d Z5Pk ( C ^y P <h}K_ж_ж ?   Ez00d Z5Pk ( C ^y P <K_ж_ж ? {  Ez10d Z5Pk ( C ^y P < K_ж_ж ? a  Ez20d Z5Pk ( C ^y P <8K_ж_ж ?!$B [0d Z5Pk ( C ^y P <K_ж_ж ?  [0d Z5Pk ( C ^y P <K_ж_ж ?N !$  [0d Z5Pk ( C ^y P <K_ж_ж ?TP) x10d Z5Pk ( C ^y P <K_ж_ж ?  y10d Z5Pk ( C ^y  P <K_ж_ж ?Z %/ z10d Z5Pk ( C ^yXr !P 0$?ra :  XB "P 0D$? D XB #P 0D$?; XB $P 0D$? < XB %P 0D$?  XB &P 0D$?3 m XB 'P 0D$?m XB (P 0D{?s XB )P 0D{?; s < XB *P 0D{? s XB +P 0D{?; t < % ,P <@K_ж_ж ?  (Y,2)$00d Z5Pk ( C ^y% -P <K_ж_ж ?  (Y,1)$00d Z5Pk ( C ^yXB .P 0D$?d < D XB /P 0D$?; d g % 0P <K_ж_ж ? n (X,2)$00d Z5Pk ( C ^y% 1P <pL_ж_ж ?;    (X,0)$00d Z5Pk ( C ^y% 2P <@L_ж_ж ? (Z,0)$00d Z5Pk ( C ^y% 3P <HL_ж_ж ?H q  (Z,1)$00d Z5Pk ( C ^yN 4P B(L_ж_ж$?" 3 <= 2F00d Z5Pk ( C ^yv 5P <@,L_ж_ж ?{ DRCVDi!j (CkPti) <= SENTj!i(CkPtj) 6# lFf!'3# #Z :Up  - H c~ ;X 6P 0$?KXB 7P 0D{?t N 8P B|:L_ж_ж$?" 2 <= 2F00d Z5Pk ( C ^y 9P <pKL_ж_ж ?Js X:Y0d Z5Pk ( C ^y :P <VL_ж_ж ?{s X:Z0d Z5Pk ( C ^yN ;P BaL_ж_ж$?$* 0 <= 0F00d Z5Pk ( C ^yN P B}L_ж_ж$?$*/  1 <= 1F00d Z5Pk ( C ^y ?P <L_ж_ж ?EO- Y:Z0d Z5Pk ( C ^yN @P BL_ж_ж$?T "  0 <= 0F00d Z5Pk ( C ^y AP <L_ж_ж ? J  Z:X0d Z5Pk ( C ^yN BP B\L_ж_ж$?T   2 <= 1F00d Z5Pk ( C ^y CP <PL_ж_ж ? (  Z:Y0d Z5Pk ( C ^yX DP 0$?. |\ XB EP 0D{? sP N FP BL_ж_ж$?T   1 <= 1F00d Z5Pk ( C ^y GP @ABCG E4F3f{? $w@lqT 7 G @    7 XB HP 0D{?s XB IP 0D{? sa < JP c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++  % pTb(  T T  ZL_ж_ж ? H \  L nZ5Pk ( C ^y T  ZK_ж_ж ? 7&c L p\5Pk ( C ^y< T c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++0  % RJX(  X X  ZL_ж_ж ? R=  L nZ5Pk ( C ^y X < M_ȯ_ȯ ?7  2DAlgoritmo O process iniciador faz um  tentative checkpoint Pede aos outros processos fazer um  tentative checkpoint Espera a recepo dos outros processos uma msg como o  tentative checkpoint foi sucedido Quando todos os processos sucedem, decide que todos os ckpts devem ser permanente; se no, deve ser rejeitado. Informa todos os processos de sua deciso Os processos que recebem a deciso agem conformemente Z 0  V0 V0  V """ ^45Pk (C^y< X c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++  % 6.\(  \ \  Zp,M_ж_ж ? 7 M lX 5Pk ( C ^yLB \ c $D$?+ C,LB \ c $D$? C  \ <_ж_ж ?E q  [0d Z5Pk ( C ^y \ <_ж_ж ?`  [0d Z5Pk ( C ^yRB \ s *D$?+ RB \ s *D$?+5RB \ s *D$?!(RB  \ s *D$?!"(  \ <XRM_ж_ж ? } X0d Z5Pk ( C ^y  \ <l_ж_ж ?a I Y0d Z5Pk ( C ^y  \ <HgM_ж_ж ? 5w x20d Z5Pk ( C ^y  \ <rM_ж_ж ?' x30d Z5Pk ( C ^y \ < |M_ж_ж ?%  y10d Z5Pk ( C ^y \ <LM_ж_ж ?%U  y20d Z5Pk ( C ^y" \ B M_ж_ж ?3 y20d Z5Pk ( C ^y" \ BM_ж_ж ?jR  x20d Z5Pk ( C ^y \  ZxM_ж_ж ?  [  M nZ5Pk ( C ^y< \ c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++  % `b(  ` `  ZM_ж_ж ? 7[P M p\5Pk  (C^yc  `  Z0 ?  [  M nZ5Pk ( C ^y< ` c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++  % d\(  d d  ZtR ?  [  R nZ5Pk ( C ^y  d  Z ? 7[ R jV4Oj ' B ]x< d c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++  % h^(  h h  ZR_ж_ж ? =  R nZ5Pk ( C ^y h  Z(R_ж_ж ? 7& R lX 5Pk ( C ^y< h c $޽h ? ̙33ZR___PPT102.]0G+D' = @B D' = @BA?%,( < +O%,( < ++00 0lr(  lR l s *$? R l s *$?  l s *X ? (    R l s *$?  R l s *$?  : l 3 ?  B l s *޽h ? ̙33 50 `p0(  pR p s *$? N p <0( ? )   Sistemas FT precisam de metodos para reinciar os processo no seus ultimos estados O Checkpoint uma  fotografia do sistema a uma definida altura checkpointing: guardar o estado dum processo checkpoint: o ponto de restaurao onde checkpointing ocorre :0 V0 _"" \5Pk (C^yR p s *$? R p s *$?  R p s *$?  : p 3 ?  B p s *޽h ? ̙33 50 e]t(  tR t s *$?  t <h ? )   Voltar a um estado sem erros simples Checkpoint salva periodicamente quando funciona normalmente as informaes sobre o processo (...informao de controlo) Informaes guarda num espaco seguro para assegurar-se da validade do Ckpt0_" Z5Pk ( C ^yR t s *$? R t s *$?  R t s *$?  : t 3 ?  B t s *޽h ? ̙33 50 D<x(  xR x s *$? R x s *$?  x < ? )   tO conjunto de checkpoint forma um  system-wide checkpoint Observation: entre 2 ckpts so uma parte da memoria muda Uma optimisao de guardar unicamente essas modificaes, o resto pode ser lido nos outros ckpts8;0_0 _;"" \5Pk ( C ^yR x s *$?  R x s *$?  : x 3 ?  B x s *޽h ? ̙33 50 |>(  |R | s *$? R | s *$? \ | <L(F ? )  F .O conjunto de checkpoint forma um  system-wide checkpoint Optimisao: um thread para a escritura do ckpt num ficheiro, e outro para o principal0_" Z5Pk ( C ^yR | s *$?  R | s *$?  : | 3 ?  B | s *޽h ? ̙33 5Z0  (  R  s *$? R  s *$?   <v ? )  F 6nO conjunto de  recovery point tem de satisfazer 3 condies : Um ckpt para cada processo No deve haver  orphan msg No deve haver  lost msg Este conjunto chama-se  recovery line 8?0_Q0_(0_" Z5Pk ( C ^yR  s *$?  R  s *$?  :  3 ?  B  s *޽h ? ̙33 50 @9(  R  s *$?   <hdG ? )  G -eTemos 3 processos X Y Z : Os tres fazem um checkpoint inicial Depois fazem checkpoint independentemente O processo Z falha depois de ter enviado uma mensagem a Y, entao volta ao ultimo chkpt Mas agora o chkpt de Y no valido porque ele recebeu uma mensagem de Z que ele ainda no envio, ento tem de voltar ao ultimo chkpt De mesmo por o processo X 80_K0_0_f" fZ5Pk ( C ^yR  s *$?  R  s *$?  :  3 ?  B  s *޽h ? ̙33 5;0 `}(    < ZI ? )  I qO processo Y falha e volta ao ckpt Y2 Na memoria do ckpt X3 uma mensagem de X para Y foi enviada Mas agora no Y2 nenhuma mensagem foi recebida O processo X tem de voltar ao ckpt X2 *0_0_" Z5Pk ( C ^yR  s *$? R  s *$?  R  s *$?  :  3 ?  B  s *޽h ? ̙33 50 ](  R  s *$?- /  <I ? )  I  0_" Z5Pk ( C ^yR  s *$?  :  3 ?  B  s *޽h ? ̙33 5& 0 h(    <?J ? )  J \O primeiro evento T envia uma pedido para F1 e F2, e cra condies  req F1 e  req F2 Y0_Y" YZ5Pk ( C ^yR  s *$? R  s *$?  R  s *$?  :  3 ?  B  s *޽h ? ̙33 5 0 XP(  f  < ? )  J 81. a exigencia principal 2. o objectivo do algoritmo90_9" 9Z5Pk ( C ^yR  s *$? R  s *$?  R  s *$?  :  3 ?  B  s *޽h ? ̙33 5 0 z(    s *J ? (  J  R  s *$? R  s *$?  R  s *$?  :  3 ?  B  s *޽h ? ̙33 5 0 z(    s *J ? (  J  R  s *$? R  s *$?  R  s *$?  :  3 ?  B  s *޽h ? ̙33 5 0  J(    <(J ? )b  JJB___PPT9$  cada processo nota o numero de mensagens enviada aos outros, e recebida dos outros Usa contador para determinar  orphan messages RT0 q<;/_00 _"S"0" ^#>Y t 1LgR  s *$? R  s *$?  R  s *$?  :  3 ?  B  s *޽h ? ̙33 50 z@(    s *J ? (  J  R  s *$? R  s *$?  R  s *$?  :  3 ?  B  s *޽h ? ̙33 50 z`(    s *L ? (  L  R  s *$? R  s *$?  R  s *$?  :  3 ?  B  s *޽h ? ̙33 50 z(  R  s *$?   s *tL ? (  L  R  s *$?  R  s *$?  :  3 ?  B  s *޽h ? ̙33 5P0 (  R  s *$?    <M ? )  M Quando um processo faz um  tentative ckpt ele no pode enviar msg enquanto no sabe da deciso do initiatorm0 Vm" m\5Pk (C^yR  s *$?  R  s *$?  :  3 ?  B  s *޽h ? ̙33 5[0 (  R  s *$?   <M ? )b  MJB___PPT9$ ?WO pedido de Checkpoint so preciso de ser enviado aos processos incluido em ckpt_cohort VW0" ]0 ]K# ## X\5Pk ( C ^yR  s *$?  R  s *$?  :  3 ?  B  s *޽h ? ̙33 550 w(  R  s *$?B I  <(_ж_ж ? )   M Existe tambem outros protocolos sincronisado que usa um relogio Todos os T sec por exemplo todos os processos guardam o seu estado se ha uma troca de mensagem espera se a recepo um pouco mais O T no pode ser muito pequeno porque usaria muito memoria e pararia muito os processos  " Z5Pk ( C ^yR  s *$?  :  3 ?  B  s *޽h ? ̙33 5"0 d(  R  s *$?    s *R ? (  R  :  3 ?  B  s *޽h ? ̙33 50 z (    s *4R ? (  R  R  s *$? R  s *$?  R  s *$?  :  3 ?  B  s *޽h ? ̙33 5rLWbmj[puzE/ѳv&@4 KWPXjWosx{Ӂ48ܟ-iG?i G1tOh+'0@Hx %FIABILIDADE DE SISTEMAS INFORMTICOS  Paula Prata1ul@@PGjV՜.+,0d   On-screen Show?L* "Times New RomanLucida Sans UnicodeArial Unicode MS StarSymbolArial Garamond WingdingsＭＳ ＰゴシックＭＳ Ｐ明朝Default DesignDefault DesignDefault Design&FIABILIDADE DE SISTEMAS INFORMÁTICOSRECOVERING A CONSISTENT STATE1. INTRODUÇÃO1. INTRODUÇÃO2. ESTUDO DA ARTE2.1 ASYNCHRONOUS CHECKPOINT" ORPHAN MESSAGE E DOMINO EFFECT LOST MESSAGE LIVE LOCKS' MODELISACAO DO GRAFICO DE OCORRENCIA 2 algoritmos para o “asynchronous checkpointing” Checkpoint periodicamente O mais recente é o activo 2 ckpts C e C' dos processos P e P' : C é um “direct propagator” para C' se, e unicamente se, informação é enviada de P para P' quando C e C' são activos “indirect propagator” se 2 processos são “direct propagator” de um tercero processo 1. O sistema deve voltar a um estado consistente se um ou muitos processo iniciam a recuperação 2. Deve suportar a determinação dos ckpts com segurança /Cada processo mantem a dia uma “Prop-list” que contem a identidade dos ckpts por os quais os seus ckpts são “direct propagator” Quando um processo inicia uma recuperação, ele avisa todos os processo que estão na “Prop-list” do seu ckpt activo, enviando um “recovery control message”O segundo protocolo usa 2 tipos de “logs” A “volatile log” é guarda na memoria principal Mais rápido e menos caro Mas não persista depois de uma falha A “sable storage” é o contrarioOCkPti : o ckpt (stable log) que i “rollback” quando falhou RCVDi←j (CkPti / e ) : o numero de mensagens que o processo i recebeu do processor j (de acordo com a informação do ckpt i ou de e) SENTi→j(CkPti / e ) : o numero de mensagens que o processor i envio o processor j (de acordo com a informação do ckpt i ou de e) Algoritmo Quando um processo falha, recupera o ultimo CkPt. Transmite uma mensagem de erro. Outros recebem esta mensagem, e rollback ao ultimo evento. Cada processo emite SENT(CkPt) aos processos vizinhos Cada processo espera as mensagens SENT(CkPt) de cada vizinho Em receber SENTj?i(CkPtj) de j, se i observar RCVDi?j (CkPti) > SENTj?i(CkPtj), rola para trás ao evento 'e' tais que RCVDi?j (e) = SENTj?i(e) , repita 3,4,e 5 N vez (N é o número dos processos) Asynchronous Recovery2.2 SYNCHRONOUS CHECKPOINT!2.2.2 SYNCHRONOUS CKPT ALGORITHMCada mensagem é etiquetada pela ordem da emissão Labeling Scheme last_label_rcvdX[Y] : o ultimo mensagem que X recebeu de Y depois X fazer o ultimo ckpt (tentative ou permanente). Se não existe, contem o mais pequeno label first_label_sentX[Y] : primeira msg que X envia a Y depois do ultimo ckpt (tentative o permanente). Se não existe, contem o mais pequeno label ckpt_cohortX : conjunto de todos os processos que deverem fazer ckpts quando X faz o checkpoint. roll_cohortX : conjunto de todos os processos que deverem fazer “rollback” para o ultimo ckpt quando X faz um “rollback” Y reiniciará a partir do ckpt permanente apenas se last_label_rcvdY[X] > last_label_sentX[Y]mAlgorithm an initiating process takes a tentative checkpoint it requests p ∈ ckpt_cohort to take tentative checkpoints ( this message includes last_label_rcvd[reciever] of sender ) if the processes that receive the request need to take a checkpoint, they do the same as 1.2.; otherwise, return OK messages. they wait for receiving OK from all of p ∈ ckpt_cohort if the initiator learns all the processes have succeeded, it decides all tentative checkpoints should be made permanent; otherwise, should be discarded. it informs p ∈ ckpt_cohort of the decision The processes that receive the decision act accordingly 3. IMPLEMENTACAO 4. CONCLUSAO  Fonts Used Design Template Slide Titles#_ Paula Prata Paula Prata  !"#$%&'()*+,-./0123456789:;<=?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&()*+,-.012345679:;<=>?DRoot EntrydO)Picturesd{Current User8SummaryInformation('PowerPoint Document(>;DocumentSummaryInformation8/