ࡱ> n ZA%&:NbPNG  IHDResRGBPLTEٟ #IDATx͋1 68- >KlpK&/f!>flݘ@tj M鬪;RI)QOUբ}p"H;G{եleכ7Y 3/׶1N+yެٜk3[rthiNIݶvʌq$]&!Y/K/#I&0>3ۿ7YPK2ΰ`~R|0[s|yG#[_aٷub&o\;-+do}*O s}jE&ޙZC7> hhNi5`lg&s5H, ͲM !8W|96s~,#h=lCVB^$\ɜW) ˗y3U% @=,^.6ʻyy tz@Hy*6p.V:ocZK2b/KSߒ*bL[u&#vLfXD0՘s'( fP^_*!6njnјʄB .L5_B9ܘ+C`?as2=nM,\qs8`S/Lֱ?Swny= 1_2BRZa!]ϹܗwirhC>X4 O\W2h!b F4LK= %^Wfś¡||yh9 NBOgsVuR* 8Ιh<5.иқ_wYX:Q>:j2k\u%}`<+ Ce@1&?,t_Mott&B3Lw)O³dDQapnEamAp>}l254M:GiT^*f9u<ԷA:N~MX['CշbYݛ7Mov`kۙU d6$[kʊ4; Ցo̸uw@mF|WtƜjwdl拱7|\f3/J/3˻v͆}}2d4}A_Af=zwjg03zY7x+[zrik!GX]&wo䅬}j,ěvN%Oԃ.uGn&Gv ܼ <;Z~30Vs=n#>t{m Urlt9!qfnJvoɌպi4l6q1%.XKj7֌lܭ T\jo2 PfajLlg ]i4ACɀ_ĸ7qNC cU>dbqwe{oIɳEσgۙXc๓36h ڝ}H,wJK]+Gрs1hVG-f{퓺 2'uoHnq ?[NHFn2V REcO19>6S({,+0grF4^G2ui1!b?ɋE 1S&UXmjb f$qj*ϳ3~X8A\(K1뉈`jg 9sҤ)YO^L[[s _\ZVl.qTSO^,\؅M8hdn6ʓ?uZQ!]'jo><_F&5\S]ݩf TzR \'u3uו rq6O9OƟ:ƹB(ic8+]qδiIq{7ɻE,VM]bM2_Ǝ7ː0_kPͷuvdzW[M 9`E6[ ZM&큏BQaPY^E0<@ыێ?a! A^QÀm6鈘YAIa3?LNbs6ehӶ6X{{_d}̂50bm}}q726ȣxIENDB`n FzG,)PNG  IHDR/բjsRGBPLTEٟ VIDATx?P&ƕv( M [A%etIBddHE }[)r+q) *w ڈfB殇d73I%3n\ޏo{Fetd1c1c1c1c1F`0h3y/}1q)g0Ձ3H?IoF p[N_ lu8N,|դ'2W_~um6&&澷t]* A2cw.a]A0%C17z3w.ma&&Q (x"A m̶`f,̛!f0fOv슉BT*G wV @KҨ(..;qJ|VhyAHj+1 _91pqRB~*< dnp.@na_3* U}1 %B5 hJ IjLAs5fknp!8Wbɩt7ba:K)&TbF7bb%>&ScͬNOEs4V>dVK0#'; (ʔýp%`W<}]T&v f} ^mo@cRG~Sl~;kP5\0k覩7wzG,ˆ'f7ƂƼ䘍T<-ګ0}[0睟}[!Z. f^vNQܝw.F_ uDᆗ#;}ʑ; DJe:1J}@;8UG#;L假xUf"TWߥ6g3Lq S+1 $,0YNKL}10ĔA좿#,8N:)tRa"R F8[`"9B{%&7ETYA0A9ag81,C<=x4:Z[,2L)fQbIa&W]ULfNj jpp3zb,b,b,݊aU6v?ʁlcce6v+?ݶ6v0y>mc72h1nh1[sn5az7vaIP 1irm1k'-1kYN 0}aݰEyݰŔNlcznWnԶ[[Piƨ^*}F73;? iNk4vטA݌4C4D]]-;Mlc7)Wm춍<6vW6vˋh?EW r2Q5c,F}d b+M57՟j6VR"_DX66v0G3}f݌ɻ̾cͬ(Ӱjn對auj09`9h0Șb6v&{9^) x0&hp,{g-/nb2`+ ?P H`"{9#{+W|B}z|>|5$_ξo t}rd2y7?} 1+ʾoL&ȝ 4<7 cLzl&7{3D^sD7ͥI.48DQL!.~)&Z%+WM`RanBoN/N]_^nȥVF[|m% IENDB`nP$,ѹ`d`0PNG  IHDRa}mmsRGBBPLTE9<9BABMMM{}{|||hhhQ#IDATx I)t(".i3䖊a  h;$0a0a#D P #t߁aPW 0DG?J}\}sV+$1RESmQh*$V)in[=TЀ٫xgSqa_+ǻoUƉn}ԇzU86h@ T탰r|Ed*)|f+x8mVx ۻtWq"f`\U5%/u0Fyx Юs1ˀ9v>glee)4NtY2|\q087<K#`dx8< AXNeF~T`$޴w&uӵbRO]ۺuwWu0Mn( to n |fje¸QkU\ak*yb;>’)ޅaҘhO#띅̮4Sa[|Igt~#| 'I^u0] n~,[a@OL*WX`)NW+p(efF`~˰mw𵻵%H ¢MJ+@=6)%e7Xx7ǐzlBĀ@X vI'zWPTae->Nu0Z@Xɸq+:>' ¢`je0qe1XmTY^Tf(у|00T:uo&]ҠEwP1U86~uh{a!XU{*+dwuq~0a1Ns0ft-,u05v;t-PiblRqr&G\{'Cfs;X-~glʨsUz+BX#*C`>{ lUrL J!p0.vMA-8  8(@ ES~[~n)#L7d=R^]<X%*+E7ݘ`׶R|G :7DW wIO **Gм8 !WsD\#v=!z8t7mOY @'*cNv"(CQS~ ^7=ypoaQ6i7WΥ@*ɝZ<Rr;/5]O La1s08Rكr-!؆CB]66_S{e@Xo(\j!q OX/5OQ0ω{>\Ja L@Xu>x .mCfFȋrg,Ri-Ex(+JJ6Ejq~Yu6afuZ"S(ɀA3&{Խ0Kë$io-#{#>a3l_ٓ{ a lwHxR/pZLbPa-GAdӿ6E_]V7tv>U`?n MAw{9X@XqXoѸEF&Š ̢7K M碽";kdF̵ruuz(HjzqdC*dS3p*%M\y̴{zn'ʛgVE`<(XŪs43uc֔lJBg)~o٭ӒTkC9O-[yT@XBjj<ȴ_/4'YTZSGu-@䈒uaPOha1>4Ta a a A w> MCm7' ,oaVaY'U VfJ.V@X}@Xb ,D;(\ e'`q8o@Xn)k@XV3b ,?r  0\6 .r,+a9aІ!!@!`p0mp0!A @A B qωaЖA#AX2)!@XBJq4'Ya k.am`))r ,s0!`h<0h"Kb ,~Ru0!@X p15`);b ,j2Qi".bRV]gb ,:`nLAXLIK!Jy9bK@[ 5`p0mae0m|p0m9;A[avBEm A[ C0hb R2 l{e;@اrN 9EY}K )}tqc\z}〰&aI}@e0aWa} + lӔB6iB͒H9x`^B./q-:.& ,,ۿl‰~ԏB~@:1Iya]`I:ۿ~"{O%g@ܷk< R}ÃGJ0)7} IoqKa a a @@@r{`Q<pۺw|Y]"B|'M.`agm?fa>}0h'@mwXQDbE 0ґ" GW=~@X "Y,oX0mX.3a, @6E,o˗0 bYX7Bo %KNK |],S`i=],;ptTeb9JW.}$]3Ų+Sr# %ٺX&T.`>@eBk{ K73τ0b e˦}lg̤bAt./,`ԄGYɋR"ˁ ˷*C6n9-T2HeKߣ.˔,$a(H7PNː$v[ \&O+7eO=.M_6(Qk3[I|K߅2˥$!sU&B Bhc9aP̐ a AOtzu!_~íxEK)i]ը~.d@W,ۿ3 &C.c޽ee*ı ,c_S69KR͋l?7-Fp"K?GmY6~rϼ +ɝtJ/]UPl%ab,Bbp#>[^;Z16`!T]1`acRn·{)j`%]eձpp}ke7L^v"MĽktDGfaw}[K %QSw_CiVپݍue>-:4?3;7uKTʛ.YmqL6؞y׻˻DM6&{مWX%~?"J0۽;u{raśG9,yΓRr2IGԲ9EvOZG}Ā(GI߾w0c[e-]1ʬ(_o+N"/SY\%خƟa}la:KQ,~*BoMZ b/>p3;۝$4OJJ[P8”~uϿ۴56Xj<kɴ/J8Dw~Y`UG"6#f1O!G}`9bdפUK>([a2k{^f n rߝX}sK?%kjɫ扎,lffcĪ֠2=a3Ҏ-Vhc X1ͬhFǨ3ߺ$0Ӊ*Toc^)izR!o=*#S]lq/[f0P1<00bEo Iܔr}"p.)7F/|˰X32eIQ4ŕCkb3 sMP 512~@zdLѳ7 B֭d2G %RX۱f~ #!'ED]YL\1?WM ,Vx?ӽYwAgS4Qޫ?k>Z;巵ٽ~_|Zz\atŲ{z@06]jdG#UzqrX H˫x*?a6+]]Ժ(򬒙#^$z ck'Wqxڴ.nGgU)z}f)-}lC{0!W J:/1h)|6wlBTe{u+ ?zcdl3Rl״1Qr _SME>Q@u&B15#Y'DVvw,kZU=+w !6:/5F! Z uC!+A=lEQLpD9SE*>*U;5:YA+^V9"2)G8ٍF3mn^B=r,+p3ٽ,<DK&Q1\BGYl},wC}kGh 3ik*7E&",^t,9g,c^%c_GYNH:e՚#>FWS5ut4)oךCk2`A)C.rixs5 w lL^u՜hm~60sV4|¼1܊Eylgb/qr@d2t.vIU69b&amYd^ઌ>+O7힬 фmՀM۝%Yk81F1_ss*y; R`0U1ՐdiOirfJsg#p`^B./wzxOk q-RM3WsX]' tko7!3Zq?$rQu(x|ԏB~ubz)!x7iǢ-b:ۿbV]͛v ZT/ݕv7']6g>qch'/4)Dkh륞:OOIZRzl/qHjq,۠$rjUjcrLT\]th% m!7G$af%Ld®ՕEM,K[s6z嫭!0.ꆙgu.Qovb`/D »]fG4MvsOHg5/~L52^Rͽb{[r4rwɴyvpzMY'Y*bB Cm~EYF!-x{.xw8Usͻ zz'_ cPnZ[&{j9o) 49"np\ڦ@;JPy".ڗ0ls -H~Oa0a a A A A A A J9dwτߋ1qwO3;@d |5a|RtiG=IϷ|0Dӓau!6jtqngk&<6=ļϣINlX#=kے 4eyӃɟ_ͧ(]^6Gاޭ INYti5j|OT=m# rFokm/szн]]s֘;,B l~ 6D= ʩv]"L(\6ܿ[ǧ%LM焞jg939":L1g?7+ݛ@o&jlNuU+[Y^E) k;t!|aKf[+%,K~IM $ͻ r};ɜYT$6t'W~ȭ\pf{^\`:yr 6~s 9kwW۹nFnMͻ |0}:{^&Of+|r̯|?,kmjCЉe`R衍Θ9̚)ӵC lXGlǐs_e7%Lt96mNBd<g簎Ռ\x+U$3n!(@[4C#yYh񵺵zZ%X.D$ͻ {z0YFC9 ՟lA˪SqXUsv굇>-:uj>Z?K4u{Нڳl=Y9"99_Ka3UۊjYQ*˶yq|TNm~ֹ8`lWI֓ESvG Idwt@ {6U~zB t=r>޾; B @A @0@0:~<IENDB`n!Kt0C]sPNG  IHDRa}mmsRGBBPLTE9<9BABMMM{}{|||hhhQ IDATx *slvT i~Μ."E'A aAB0%("C/ Qj;xO_6(ICmVS@aT9Չ ?*)KgS)_]΢lzBCNiFE")2dkH˶q]ZM0sRښ$qz$B ljxW[ID׮%ՇlRk9eh@#R>^ _*T')lVo#K[i2?e"ӻtmOڸ,⪤R[& / ,̂n:4 hi竗u0s/8+q&Uvv*β`BK{1]ePC&9X^Z/ !,$]eVSucSdÓLKǝ`ƹw]u6.V{eTW4"v#"$uo&D( >cvGq0V"| <-٦M EG`Ce/5?cXG.{̈,@deg/逃J| ,UK~oEUӳz,騪nu/Xb>ڈMV0FyR[$0U#9:}37 U^ߑAmǢՏ[{)}2&0H:3c7ݧDnzDji #I[1N.> } o)?_2lYt؞$AEiTЁronrN솋A2-ݾ;FJW\ -6*/hqz%ڏ"ټeM{>u0AŸu?,`1(9%b0z1U`s@cԋJKaHtֽt,A\jj=it'_Ϟ!̵2#iU-Ɋ)͹:M`0s0Y;h;X4[ciUCnG׈=بC&3j=1{ ̝4ru]dmޢG=,[R(KWkoT s !m.9w@Jt2`.>`i}Vx*nWKU./9PO4{`XGzAU{)n`i3G l; j4~OB.y{N~,Qʄgbb=MΏvKT8<#l{Z>7jm+YTw!O[|oA55&6UFmWU#{,ֿ)_t!|lV3S%ڋ%Ffe-A楗*&_:QPUd1ՏPTsa}rFc`ޤz7RaBs.m#rI :[,|ϑRK]zf<  2͠h/gqI QYf8,#Na蕵TsH$`㞈OF.$TL\%Zf{m4`1@x a6r~^SƟs3$I<;;bo4`ާaf :v< 6'L }e-0c QeI_e׽*a[ˌU  = ls%1:Cg~h\OaBUcw Gy X3ۊa.(**fyKJ웃L PN:5N؛( )@lwԋG*Ǖaz*JQ9KVvODytGEuw˻fnI"DI|A[` 6?v>kmEquTw[Bc7!G!)/ջk-:Xp&*%a>HGcCJ[,}L_!FgN'%'[R`Q1s{⹛ a)uoyK``^0YZeb`1al!iro٫9ʶkuAj(ˊ0Q|kbuA!iAhlaAB0!aAB;AZ0~@ZBWEn%9c$BX ah-] AX}@Xdbm,f7 儃 ,Bv;b\ ‚r07# ,4VŽ.aA= ,)-E0,$ai3j*"GΞ0p1s0_,90rAӀPp1sQ~ggAK ,.a)0w0>.aN),ψFx ̱ )B=/*mbbm| ls`Ptq1Ta[tm}D) U aIA؆!s1۪$ tH$i)Bg:I{lAb@؇tݡ 3[9.acJW\ V/]q1[Yr uK["g 4} q\qp[g!O P{"v E![>afK? 6ÅgܖONY@2WUӬ ٺ^Tގx+BIߠԷ# Զh6pexGEa RCW˺/ E );,/^/$ u'1@OoaVmK6v*t;bd},BGۑ>zWfx۷wɤjDh+1}SW]ϖ˖%lͻNEr˼˝]y&pg_xYp2knOvXfTa3ZWvCY?vO:JLҌ!W41ͯo;x$aY8rRo;gS3*_ɺ=ؑ|V%0n98r<~8JG^vDh6cs1xͭ!8N!&/ZrVSQ܍UI]660;N#?O2H,zMEh7j+IYf聼'XyʐSHbF=e+.^>=D?o8Dc._mlTmU)9QDcnbdf]ېUzs11j3~9X2\֦ .|}( );aŠ5y2O/ ’:lpBsp]_z;xc8|qN. #A>A TIW`5f. ` Q?1ex-+o(l26Tn+$ˆHvlY ㅶ3mǩ3,mS0G)CG} lL#\wSj&؆%-w>KGN/4}XQowNRvWMt)}}rb ao LuHmt]].b{*wM*k+H+i@$-ws#*#鞵uR^{8l*a{ 6\Cq?jeR^y,۔ &&(٤=絊馒БuRhyXP~kY M$!+fS7 {"axRvIoyֽ2IU/5=A}b',^7W#,ö*V{n&NIg,n&* K-/5eAiu3_SQ}lR۱ QBp"SīS*h '`IؕRAd`]iN1}EFc?EoXO95; %15FԽdN)K*1onq֦uwmE 1/BqK/PO  586nC@"r+Q*vZ%2sx> WGˍEVm՗& rH_3B+zOҋ3bޕ59\}M.8RV[h:[ Uil{b)G~-d[*e\u|&p_OnEXpj1G>QAid8%=xzۈDSEKGvb~Q0Eh]c٤,Zdn?ZcۘH][}Vª7&nq_`I%Q$q_^{P"c+fqodAt̚v1p?dX9)>l3/b.=PYbZ[V7.8V>Nu; q8?,K!N,D>$~\J:vqчin6ad;Thc3D78^^ςl_yO░ʪhZz+Kf|7 ixl6}}V-7|[Y\z/84eM.N.O>/p {z,f(>lwv0~f>+vgje|nI2b&OdEϿq33kuA]xi|ͣhPNϸ̖(foV;3=X:o㋚]VMO4}pJef5R4#?ca;e^$,w9XC\t˶"gj”>g~/jjXvuo߇At9 qfFonza!C0!aAB0 !aAB0 !aAB0 !CAB! !CAB!^?w3;0 IENDB` W( "/ 00DArialngsRo<Lv 0( 0"DGaramondRo<Lv 0( 0 DTimes New Romanv 0( 00DWingdingsRomanv 0( 0 `0. @n?" dd@  @@`` 80 C     >>() 5        </   Ob$ ZA%&:Nb b$FzG,)  b$,ѹ`d`0X$[b$Kt0C]s!8 0AA@8ʚ;ʚ;g4IdIdv 0Vppp@ <4dddd` 0L g4XdXdv 0p@ pp<4BdBd` 0L<4!d!d` 0L"0___PPT10 pp___PPT9<P?  O  =M3O Problema Do Acordo Distribudo (Acordo Bizantino)44..Trabalho realizado por: Lus Almeida n 15101Blocos Bsicos de Construo$ O objectivo dos sistemas tolerantes a falhas o de continuar a fornecer servios apesar de alguns dos seus componentes falharem. Blocos bsicos de construo so as suposies feitas acerca do comportamento dos sistemas e dos seu modos de falha e, Os mtodos para suportar essas suposies. % Acordo Bizantino!Quando um sistema falha, pode comportar-se de maneira totalmente arbitrria. Esta falha chamada Falha Bizantina. Protocolos de Acordo Bizantino. O modo de falha considerado o mais geral. Se se conseguir lidar com o Acordo Bizantino, ento podem-se mascarar a maioria do tipo de falhas.""BAcordo Bizantino - Definio do Problema e Resultados Impossveis(C&/ Vamos considerar: Um sistema com vrios componentes, no qual h troca de informao entre eles. Um sistema distribudo no qual os ns so os componentes e a informao trocada por passagem de mensagens. Os nodos podem ser defeituosos e podem exibir falhas Bizantinas.* BAcordo Bizantino - Definio do Problema e Resultados Impossveis(C&/O objectivo a atingir : Todos os ns no defeituosos devem chegar a um consenso sobre os valores correctos. Cada n deve tomar uma deciso baseada nos valores recebidos dos outros ns, e todos os ns no defeituosos devem tomar a mesma deciso. ~TT BAcordo Bizantino - Definio do Problema e Resultados ImpossveisC&/: Exigncias para o problema geral do consenso: 1. Todos os ns no defeituosos produzem o mesmo valor. Chamamos v(i) ao valor do n i. 2. Se o n emissor, i, funcionar correctamente, ento todos os ns no defeituosos usam o valor que i envia. Este problema tambm chamado Problema da Consistncia Interactiva. /E/AN% BAcordo Bizantino - Definio do Problema e Resultados Impossveis(C&/#Figura 1: Dois cenrios Impossveis$P$ 3Acordo Bizantino - Protocolos com mensagens comuns(4&  S possvel chegar a um consenso caso, sendo m o nmero de ns defeituosos, haja pelo menos um total de 3m+1 ns. Assume-se que o n no defeituoso executa o protocolo correctamente. Um n defeituoso comporta-se de uma maneira qualquer.@0; 3Acordo Bizantino - Protocolos com mensagens comuns4&" Suposies assumidas sobre o sistema de passagem de mensagens: S1. Cada mensagem que enviada por um n entregue correctamente pelo sistema de mensagens ao receptor. S2. O receptor sabe qual o n que lhe enviou a mensagem. S3. A falta de uma mensagem pode ser detectada.*@@3Acordo Bizantino - Protocolos com mensagens comuns4&" Algoritmo da Consistncia Interactiva: S funciona se as 3 suposies anteriores forem satisfeitas. m representa o nmero total de ns defeituosos. n representa o nmero total de ns. n >= 3m + 1. 1 n o transmissor. Os restantes ns so os receptores.((=.">3Acordo Bizantino - Protocolos com mensagens comuns4&"Funciona por etapas. Cada etapa consiste em troca de mensagens entre ns. Etapa 1: Transmissor envia valores para os outros n-1 ns. Etapa 2: Cada n tem de comunicar aos outros n-2 ns o valor que recebeu na etapa 1. Etapa 3: As mensagens so de novo enviadas. & TZ2Z ZLZ Z#ZZT) $' #3Acordo Bizantino - Protocolos com mensagens comuns4&"Algoritmo ICA(0). O Transmissor envia o seu valor para todos os outros n-1 ns. Cada n usa o valor que recebe do transmissor, ou usa o valor por defeito, se no receber nenhum valor. Algoritmo ICA(m), m>0. O Transmissor envia o seu valor para todos os outros n-1 ns. Seja vi o valor que o n i recebe do transmissor, ou seja o valor por defeito se no receber nenhum valor. O n i age como sendo o transmissor no algoritmo ICA(m-1) para enviar o valor vi para cada um dos restantes n-2 ns. Para cada n i, seja vj o valor recebido pelo n j (j `" i). O n i utiliza o valor majority(v1, & , vn-1). ZnZnZZnZnZ 5p  5              V    +                                 "                        3Acordo Bizantino - Protocolos com mensagens comuns4&"t Acaba a recursividade na etapa m+1. O n transmite a mensagem que recebeu na etapa m. O valor em maioria o enviado na etapa m. Este valor  filtra-se para cima na cadeia de recurso.^4):3Acordo Bizantino - Protocolos com mensagens comuns(4& Figura 2: Algoritmo ICA(1).P6Acordo Bizantino - Protocolos com mensagens assinadas7&%H ICA(m) complicado. O problema torna-se mais simples se restringirmos a habilidade dos ns em alterar as mensagens. O transmissor envia uma mensagem  assinada .b`-6Acordo Bizantino - Protocolos com mensagens assinadas7&%^ Um transmissor envia uma mensagem assinada a outros ns. Um n adiciona a sua assinatura mensagem que recebe, e envia-a na prxima etapa. Se o n no for defeituoso, a sua mensagem igual que recebeu do transmissor. Se o n for defeituoso, este tem de enviar a mensagem original ou no enviar nenhuma (uma mensagem alterada pode ser detectada).__6Acordo Bizantino - Protocolos com mensagens assinadas(7&#5 V -> o conjunto de valores recebidos. choice(V) -> funo utilizada para devolver um nico valor do conjunto de valores. Requisitos para a funo choice(V): Se V={} -> choice(V)=0. (pode ser outro) Se V s tiver um valor, ento choice(V) = v. Noutros casos a escolha pode ser a mdia ou a soma dos valores. " I  2 A6Acordo Bizantino - Protocolos com mensagens assinadas7&% i envia o valor x para outro n -> x : i. Se j recebe esse valor e depois o envia ento -> x : i : j. O protocolo SM(m) chega a um consenso com at m ns defeituosos.-6Acordo Bizantino - Protocolos com mensagens assinadas7&%Algoritmo SM(m) No incio Vi = O transmissor assina os seus valores e envia-os para os outros ns. Para cada i: (A) Se o nodo i recebe uma mensagem do tipo v : 0 do transmissor ento (i) Vi = {v}, e (ii) envia a mensagem v : 0 : i para todos os outros ns. (B) Se o n i recebe uma mensagem do tipo v : 0 : j1 : j2 : & : jk e v no pertence a Vi , ento (i) adiciona v a Vi , e (ii) se k<m envia a mensagem v : 0 : j1 : j2 : & : jk : i para todos os nodos exceptuando j1, j2, & , jk. Para cada i: quando o nodo i no recebe mais mensagens, ele considera o valor final como sendo choice(Vi). Rqskq   "N                        '                                                              !                 C   2 6Acordo Bizantino - Protocolos com mensagens assinadas7&% No passo 2, um n ignora uma mensagem que contenha um valor v que j tenha recebido. Ignora tambm qualquer valor que no possua a sequncia correcta de assinaturas. So usados  timeouts para determinar quando no iro chegar mais mensagens, ou ento outros mecanismos.2<!6Acordo Bizantino - Protocolos com mensagens assinadas7&% Se o transmissor no for defeituoso ento ir enviar o mesmo valor v para todos os outros nodos. Desde que a sua assinatura no possa ser falsificada, nenhum n pode receber qualquer outro valor no passo 2 (B) do algoritmo. choice ir escolher esse valor.HC$?Acordo Bizantino - Protocolos com mensagens assinadas: Exemplo@&.< Nos slides seguintes apresenta-se um exemplo para 3 ns sendo 1 deles faltoso. Tem-se ento n=3 e m=1. O exemplo consiste em 3 generais (1 comandante e 2 tenentes) que tm de decidir se atacam ou se se retiram. A ordem inicial dada pelo comandante, aos outros 2 tenentes. No entanto o prprio comandante pode ser faltoso e enviar informao diferente para cada um dos tenentes. Por isso eles tm de desconfiar da deciso dele, e encontrar uma maneira de chegarem a uma deciso em comum. Neste exemplo, vamos considerar exactamente o caso, em que o comandante faltoso.=P=&?Acordo Bizantino - Protocolos com mensagens assinadas: Exemplo@&.No inicio : Vi = , i=1,2. O valor por defeito de choiche() =  retirar . O Comandante tem o n 0, o Tenente1 o n1 e o Tenente2 o n 2.  ~  !""""K"""4 e '?Acordo Bizantino - Protocolos com mensagens assinadas: Exemplo@&.# Passo (2) Neste ponto temos que saber se executamos o passo (A) ou o (B). No nosso caso cada n i (1 e 2) recebeu uma mensagem do tipo v : o, logo o passo a executar o (A). Passo (2) (A) (i) -> (ii) -> Enviar v : 0 : i para os outros tenentes (neste caso, o 1 para o 2 e vice-versa). PPPPeP V&# B#?Acordo Bizantino - Protocolos com mensagens assinadas: Exemplo@&. %?Acordo Bizantino - Protocolos com mensagens assinadas: Exemplo@&.RTemos agora de decidir se voltamos a executar o passo (A) ou vamos executar o passo (B). Como cada tenente recebeu uma mensagem do tipo v : 0 : j1 : j2 : & : jk , ento temos de executar o passo (B). Passo (2) (B) Para cada i: i = 1 -> recebeu:  retirar : 0 : 2  retirar ainda no est em V1 -> executar o sub-passo (i). i = 2 -> recebeu:  atacar : 0 : 1  atacar ainda no est em V2 -> executar o sub-passo (i). Passo (2) (B) (i) Passo (2) (B) (ii) Verificar se k < m. m = 1. Temos v : 0 : j1 -> 1 = 1, logo no se executa o sub-passo (ii). Z ZZ(ZZHZZ     6 @ > (     2(?Acordo Bizantino - Protocolos com mensagens assinadas: Exemplo@&.vPasso (3) Para cada i: Como cada tenente no recebe mais mensagens, ento temos de executar a funo choice(Vi). choice({ atacar ,  retirar }). Neste caso como no existe um valor em maioria, escolhe-se por exemplo o valor que estava definido por defeito, ou o outro. O importante que os dois tenentes vo utilizar o mesmo valor para executarem. Os dois tenentes sabem que o comandante faltoso, porque quando trocaram mensagens entre si, viram que as mensagens dele tinham assinaturas diferentes. E sabido que s o comandante pode alterar as sua prpria assinatura.  S  P  /"  ` 3333ff3` 3333f33ff3` "3333̙ff3` Kf3̙` &e̙3g3f` f333̙po7` ___f3̙;/f9` ff3Lm` ff3LmNLm>?" dd@*?nAd@q<nAqFLK#M n?" dd@   @@``PR    M`2p>> 1)x(  x x HD;? ?" `}  ]%Clique para editar o estilo do ttulo&& \ x Ha? ?" `  nClique para editar os estilos de texto do modelo global Segundo nvel Terceiro nvel Quarto nvel Quinto nvel8  o  x 6a #" `] `}  `*   x 6ܽa #" ``  a X*   x 6Pa #" `] `} a X*   x C @ABCDE FjJ@3"0`B x s *DjJ"0 `0H x 0޽h ? ___f3̙;/f9___PPT10i.  +D=' $= @B + DModelo de apresentao predefinido  @|(  | | H؞a? ?"@ a ]%Clique para editar o estilo do ttulo&&  | H$:a? ?"  a v>Faa clique para editar o estilo do subttulo do modelo global??  | 60a #" `] `} a `*   | 6ds #" `]}  a X*   | 6Lis #" `] `} a X*   | C @ABCDE F8c@3"@B | s *DjJ"  ,$0H | 0޽h ? ___f3̙;/f9___PPT10i.  +ityD=' $= @B +60 pF(    05 P   s X*   05    s Z* d  c $ ?  52  0$5  0 5 nClique para editar os estilos de texto do modelo global Segundo nvel Terceiro nvel Quarto nvel Quinto nvel8   o  65 _P  5 X*   6x5 _  5 Z* H  0޽h ? 3380___PPT10.p`_ (    0p P    X*   0     Z*   6< _P   X*   6D _   Z* H  0޽h ? 3380___PPT10.|w0 00(  x  c $ss|@ s x  c $|ts|  s H  0޽h ? 3380___PPT10.o@&%$  P$(  r  S dx `}   r  S >x `  H  0޽h ? ___f3̙;/f980___PPT10.p0 $  $(  r  S H$x `}   r  S $x `  H  0޽h ? ___f3̙;/f980___PPT10.ptv$  $(  r  S Dx }   r  S x `  H  0޽h ? ___f3̙;/f980___PPT10.pЃd^$  $(  r  S ,x }   r  S x `,  H  0޽h ? ___f3̙;/f980___PPT10.pJ4$  $(  r  S lx }   r  S x `  H  0޽h ? ___f3̙;/f980___PPT10.pb_  _(  r  S  x }   r  S  x9    J  C "A Fig1 M   B ?"' W  a1Impossibilidade de resolver o problema com 3 ns.22H  0޽h ? ___f3̙;/f980___PPT10.p05$  $(  r  S (Ax `}   r  S Ax `  H  0޽h ? ___f3̙;/f980___PPT10.pR}  $(  r  S "x `}   r  S 3x `  H  0޽h ? ___f3̙;/f9___PPT10i.pn+D=' $= @B +}  $(  r  S  x `}   r  S  x `  H  0޽h ? ___f3̙;/f9___PPT10i.p B +D=' $= @B +}  $(  r  S 0x `}   r  S /x `  H  0޽h ? ___f3̙;/f9___PPT10i.p`W+D=' $= @B +  :(  r  S h ax `}  a   S `x ` a "hu=H  0޽h ? ___f3̙;/f9___PPT10i.p *+D=' $= @B +}   $(  r  S Usx `}  s r  S hysx ` s H  0޽h ? ___f3̙;/f9___PPT10i.pWV+D=' $= @B +T   T(  r  S ,|ax `}  a r  S |axIc a J  C "A Fig2 t`  0p~a' -N 1: majority(x,x,y) N 2: majority(x,x,y) >.0 2  0|a   -N 1: majority(x,y,z) N 2: majority(x,y,z) >.0 2H  0޽h ? ___f3̙;/f980___PPT10.p6ʘ}  0$(  r  S R5x `}  5 r  S R5x ` 5 H  0޽h ? ___f3̙;/f9___PPT10i.p+D=' $= @B +}  @$(  r  S T5x `}  5 r  S  Y5x ` 5 H  0޽h ? ___f3̙;/f9___PPT10i.pra_+D=' $= @B +}  P$(  r  S sx `}  a r  S Psx ` s H  0޽h ? ___f3̙;/f9___PPT10i.p඗@+D=' $= @B +}  `$(  r  S 5x `}  5 r  S (K5x ` 5 H  0޽h ? ___f3̙;/f9___PPT10i.pP;+D=' $= @B +  p:(  r  S phx `}     S Sx `  "hu=H  0޽h ? ___f3̙;/f9___PPT10i.ppBP+D=' $= @B +}  $(  r  S ax `}  a r  S ax ` a H  0޽h ? ___f3̙;/f9___PPT10i.p0!+D=' $= @B +$  $(  r  S Xx `}   r  S x `  H  0޽h ? ___f3̙;/f980___PPT10.pl}  $(  r  S (75x }  5 r  S 55x ` 5 H  0޽h ? ___f3̙;/f9___PPT10i.Vq+D=' $= @B +  (  r  S x@5x <}  5 r  S 5x ` 5   0% 7J  ? Passo (1) 0 2 ^  0 )  DV1 = { atacar }. V2 = { retirar }.b#0 24    J  C "A Fig5 H  0޽h ? ___f3̙;/f9___PPT10i.P4+D=' $= @B +   (  r  S Xx `}   r  S /x `    0d;W D0 2   0l>a F0 2 L  0@% ^  FV1 = { atacar }. V2 = { retirar }. N#00 24      0G z z  `-> deixar Vi = {v}20 2  H  0޽h ? ___f3̙;/f9___PPT10i.R+D=' $= @B +   " (  r  S x }     0d@t JPasso (2) (A) (ii)0 2N  C &AFig4_1H  0޽h ? ___f3̙;/f9___PPT10i.O}0eu+D=' $= @B +  (  r  S xsx `}  s r  S  sx  s b  0c G  nV1 = { atacar ,  retirar }, V2 = { atacar ,  retirar }.<804  H  0޽h ? ___f3̙;/f980___PPT10.j$  $(  r  S Aax }  a r  S Tax ` a H  0޽h ? ___f3̙;/f980___PPT10.@*I0 ` (  X  C    s  S Q 0  s " H  0޽h ? 3380___PPT10.p)_r@vW?cKx wz|~'?čIiřJϞTMk٣^tq%2 v(tOh+'0l hp   $ 0<D4O Problema Do Acordo Distribudo (Acordo Bizantino) Lus Almeida AcEdgeAlm Paula Prata76lMicrosoft Office PowerPoint@#, @?+o@ fBgQGg  4& &&#TNPP2OMir & TNPP &&TNPP    --- !---&&~w@ ww0- @Garamond ww0- . 2 1.&4t-̙-$ ?BB@@@??--&&-̙- $||--&--Y`-- @Garamond ww0- f3.'2 jO Problema Do Acordo 0"/0) . f3.42 'jDistribudo (Acordo Bizantino)/ ) %.--Y-- f3@"Arialw@ ww0- .*2 Trabalho realizado por:    . .2 4 Lus Almeida   . .2 4n 15101 .--"System 0-&TNPP &՜.+,0    On-screen Shown-ss  Arial GaramondTimes New Roman Wingdings#Modelo de apresentao predefinido4O Problema Do Acordo Distribudo (Acordo Bizantino)Blocos Bsicos de ConstruoAcordo BizantinoCAcordo Bizantino - Definio do Problema e Resultados ImpossveisCAcordo Bizantino - Definio do Problema e Resultados ImpossveisCAcordo Bizantino - Definio do Problema e Resultados ImpossveisCAcordo Bizantino - Definio do Problema e Resultados Impossveis4Acordo Bizantino - Protocolos com mensagens comuns4Acordo Bizantino - Protocolos com mensagens comuns4Acordo Bizantino - Protocolos com mensagens comuns4Acordo Bizantino - Protocolos com mensagens comuns4Acordo Bizantino - Protocolos com mensagens comuns4Acordo Bizantino - Protocolos com mensagens comuns4Acordo Bizantino - Protocolos com mensagens comuns7Acordo Bizantino - Protocolos com mensagens assinadas7Acordo Bizantino - Protocolos com mensagens assinadas7Acordo Bizantino - Protocolos com mensagens assinadas7Acordo Bizantino - Protocolos com mensagens assinadas7Acordo Bizantino - Protocolos com mensagens assinadas7Acordo Bizantino - Protocolos com mensagens assinadas7Acordo Bizantino - Protocolos com mensagens assinadas@Acordo Bizantino - Protocolos com mensagens assinadas: Exemplo@Acordo Bizantino - Protocolos com mensagens assinadas: Exemplo@Acordo Bizantino - Protocolos com mensagens assinadas: Exemplo@Acordo Bizantino - Protocolos com mensagens assinadas: Exemplo@Acordo Bizantino - Protocolos com mensagens assinadas: Exemplo@Acordo Bizantino - Protocolos com mensagens assinadas: Exemplo  Fonts UsedDesign Template Slide Titles#_ Paula PrataPaula Prata  !"#$%&'()*+,-/0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root EntrydO)Pictures=ZCurrent UserSummaryInformation(PowerPoint Document(.6DocumentSummaryInformation8