Aa!re}  0 @   0p` `HH $ @d HHHH̀̀̀ff@  d Footnote TableFootnote**.\t.\t/ - :;,.!?4eeTOCHeading1Heading2   ;EquationVariablesX ;`<<=7=P=i=@E@F Q3@;@=@?@AQc_Q}QR5RcUTV  <$lastpagenum><$monthname> <$daynum>, <$year>"<$monthnum>/<$daynum>/<$shortyear>J<$hour>:<$minute00> <$ampm> on <$dayname>, <$monthname> <$daynum>, <$year>"<$monthnum>/<$daynum>/<$shortyear><$monthname> <$daynum>, <$year>"<$monthnum>/<$daynum>/<$shortyear> <$fullfilename> <$filename> <$paratext[Title]> <$paratext[Heading1]> <$curpagenum> <$marker1> <$marker2> (Continued)+ (Sheet <$tblsheetnum> of <$tblsheetcount>)Heading & Page <$paratext> on page<$pagenum>Pagepage<$pagenum>See Heading & Page%See <$paratext> on page<$pagenum>. Table All7Table<$paranumonly>, <$paratext>, on page<$pagenum>Table Number & Page'Table<$paranumonly> on page<$pagenum>Heading <$paratext>HTML Headings++A88::335579AHHA;b;d;f;h;j;l;n;p;r;t;v;x;z;|;~;;;;;;;;;;;;;;;;;;;;;LFL;;;;;;;;;LGL;;;;;;;;;;;;;;;;;;;LGEL;;;;;;;;;<<<<<< < <<<<<<<<M;GM=<"<$<&<(<*<,<.<0<2<4<6<8<:<<MoGMqR?R@RARBRCRDRERFRGRHRIRJRK0RLRM0RN.RO.RP.RQ.RR.RS0RT3RU$1.RV+2.RW3RX$1.RY+2.RZ3R[$1.R\+2.R]+3.R^3R_$1.R`+2.Ra0RbRsRtRuRvRwRxRSSU 0RSSSRUUUU&U8'a.VyW&WW:W'a.W-b.W31 W?:oEvExEzE|E~EEEEEEEEEEEEEEEEEFFFHHHHHHHHHHHHHHHHHHHHHHHHHHHHOHHHHNHHHHHHHIIIIII I IIIIINIIII I"I$I&I(I*I,I.I0I2I4I6I8I:I<I>I@IBIDIFIHIJILINIPIRNSIVIXIZNUIeNINJOJ%JJJJJJKTKVGKX2dq5+H5̨Q4d^e d;]d;L HmR;MHmRHRHRFootnote Hr@;NHr@HzHz Single LineH;O Footnote ;P  HD;Q HDHH Double LineH;R Double Line;S ;T H;U  Single Line;V HZ;W  TableFootnoted5p77 EGxR;XEGxREPwEPw TableFootnoted;^dEl d;_d'00zupkfa\WRMHC>vCFILORUX[^adgjmpsy| %).12/,)&#W/Bm }d ;ad WeHTML Mapping Table }Hd ;cHd We }Hd ;eHd We }Hd ;gHd We }Hd ;iHd We }H&;kH&g% FrameMaker E Source Item }H ;mH We XML Item }H ;oH We }H&;qH& W eInclude Auto# } H&;s H& W e Comments }H;uH W e }HH;w HH W eElement }H;y#Hg %New Web EPage? }H;{H We } H;} H We }H ; $H We P:Date Line }HH ;#%HH WeP }H ;$&H WeN }H ;%'H WeN } H ;&( H We }EH ;')EH We P:Reading }HEH ;(*HEH WeP }EH ;)+EH WeN }EH ;*,EH WeN } EH ;+- EH We }QH ;,.QH WeP:Title }HQH ;-/HQH WeH* }QH ;.0QH WeN }QH ;/1QH WeN } QH ;02 QH We }]H ;13]H WeP:Body }H]H ;24H]H W eP }]H ;35]H W!eN }]H ;46]H W"eN } ]H ;57 ]H W#e }iH(;68iH( W$e P:Numbered1 }HiH(;79HiH((&eLI %e Parent = OL A'e Depth = 0 }iH(;8:iH( W(eN }iH(;9;iH( W)eY } iH(;:< iH( W*e }H ;;=H  W+e P:Heading1 }HH ;<>HH  W,eH* }H ;=?H  W-eN }H ;>@H  W.eN } H ;?A H  W/e }H(;@BH(  W0e P:Numbered }HH(;ACHH(( 2eP 1e Parent = OL A3e Depth = 0 }H(;BDH(  W4eN }H(;CEH(  W5eY } H(;DF H(  W6e }H ;EGH  W7e P:CellBody }HH ;FHHH  W8eP }H ;GIH  W9eN }H ;HJH  W:eN } H ;IK H  W;e }H ;JLH  W<eP:CellHeading }HH ;KMHH  W=eP }H ;LNH  W>eN }H ;MOH  W?eN } H ;NP H  W@e }H ;OQH  WAe P:Footnote }HH ;PRHH  WBeP }H ;QSH  WCeN }H ;RTH  WDeN } H ;SU H  WEe }H(;TVH( WFe P:Bulleted }HH(;UWHH((HeLI Ge Parent = UL AIe Depth = 0 }H(;VXH( WJeN }H(;WYH( WKeN } H(;XZ H( WLe }H ;Y[H WMe P:Heading2 }HH ;Z\HH WNeH* }H ;[]H WOeN }H ;\^H WPeN } H ;]_ H WQe }H;^`HgR% P:HeadingRuEnIn }HH;_aHH WSeP }H<`bH WTeN }H<acH WUeN } H<bd H WVe }7H <ce7H WWe P:Indented }H7H < dfH7H WXeP }7H < eg7H WYeN }7H < fh7H WZeN } 7H <gi 7H W[e }CH<hjCHg\% P:TableFootEnote }HCH<ikHCH W]eP }CH<jlCH W^eN }CH<kmCH W_eN } CH<ln CH W`e }]H(<mo]H( Wae P:TableTitle }H]H(<npH]H((ceLI be Parent = OL Ade Depth = 0 }]H( H "W4e }©H <=?©H #W5e P:Answer }H©H <>@H©H #W6eP }©H <?A©H #W7eN }©H <@B©H #W8eN } ©H <A ©H #W9e }Td <D=FTd F$W:eHTML Options Table }DTd <DDTd F$W;e }Td <DTd F$W<e }dD <DCGdD F%W=eControl }DdH <DFHDdH F%W>eValue }dH <DGIdH F%W?e Comments }pD6<DHJpD6 F&W@e Image Format }DpH6<DIKDpH66F&A2% 0001IMAGGIF  MACP0001GIPdEF }pH6<DJLpH6 F&WBe }D <DKMD F'WCeBanners }DH <DLNDH F'WDeN }H <DMOH F'WEe }D<DNPDF(F% Banner ReferPE ence Frame }DH<DOQDH F(WGe }H<DPRH F(WHe }D(<DQSD((F)I$% Copy Files  Imported by PE Rerefernce }DH(<DRTDH( F)WJe }H(<DSUH( F)WKe }D(<DTVD((F*L$% Copy Files  Imported by PE Reference }DH(<DUWDH( F*WMeN }H(<DVH( F*WNe }Vd <D[Vd F+WOeSystem Macros }?Vd <D?Vd F+WPe }Vd <DVd F+WQe }f? <DX\f? F,WRe Macro Name }?fH <D[?fH F,WSe Replace With }fH <D^fH F,WTe Comments }r? =D]_r? F-WUe StartOfDoc }?rH =D^?rH F-WVe }rH =DarH F-WWe }~? =D`b~? F.WXe EndOfDoc }?~H = Da5?~H F.WYe }~H = D5d~H F.WZe }Š?= DceŠ?F/[% StartOfSubPEDoc }?ŠH=Dd6?ŠH F/W\e }ŠH=D6gŠH F/W]e }¤?=Dfh¤?F0^% EndOfSubPEDoc }?¤H=Dg7?¤H F0W_e }¤H=D7j¤H F0W`e }¾?=Dik¾?F1a% StartOfFirstPESubDoc }?¾H=Dj8?¾H F1Wbe }¾H=D8m¾H F1Wce }?=Dln?F2d% EndOfFirstPESubDoc }?H=!Dm9?H F2Wee }H=#D9pH F2Wfe }?=%Doq?F3g% StartOfLastPESubDoc }?H='Dp:?H F3Whe }H=)D:H F3Wie }?=+t?4j% EndOfLastPESubDoc }?H=-s;?H 4Wke }H=/;yH 4Wle }BH HDBwBH F5Wme C:Wingding }HBH HDvxHBH F5WneEM }BH HDw<BH F5WoeN }y}L? 7Wse Macro Name }?LH =@|~?LH 7Wte Replace With }LH =B}LH 7Wue Comments }X?=D~X? 8Wve See Also }?XH=F?XH8w% See Also: PE <$paratext> }XH=HXH 8Wxe }Vd EDVd F+Wye }fH ED\]fH F,WzeHead }rH ED_`rH F-W{e }xd =Q xd :WeGeneral Macros }?xd =S?xd :We }xd =Uxd :We }xd =Wxd :We }? =Y"? ;We Macro Name d= d= d l d= d  WBm }d = d  <W|eHeadings Table }Hd = Hd  <W}e }Hd = Hd  <W~e }H= H  =WeHeading Level }HH= HH =g%Paragraph ForEmat }H= H  =We Comments }H= H >W e2 }HH= HH  >We Heading1 }H= H  >We }KH = KH  ?We3 }HKH = HKH  ?We Heading2 }KH = KH  ?We }WH = WH  @We4 }HWH = HWH  @W e Lettereda }WH = WH  @W e }cH = cH  AW e5 }HcH = HcH  AW e LineComment }cH = cH  AW e $zQ5 $z$$?zQ6;$?z$??d@48H}?H =[ #?H ;We Replace With }H =]"$H ;W eHead }H =_#%H ;W!e Comments }? =a$&? CW"e }?H =c%'?H CW#e }H =e&(H CW$e }H =g')H CW%e }d =j(.d DW&eCharacter Macros HHˆ;"HHˆ+Ge HHˆ;$3HHˆ**l}?d =l?d DW'e }d =nd DW(e }? =p)/? EW)e Character }?H =r.0?H EW*e Replace With }H =t/1H EW+e Comments }? =v0B? FW,e HUV ;.HUV 3Ge HUV ;05+HUV 22l H$ ;1H$ 5Ge H$ ;33H$ 44l HHˆ;4HHˆs227  `Outline for January 23, 2001 `Greetings and felicitations! `eNo class on January 25 or January 30; no office hours on Wednesday, January 24 or Monday, January 29 `1Extra office hour: Friday January 26: 11 AM1 PM `Distributed system? ` What is it? ` Why use it? 0`System Architectures 1`minicomputer mode 2`workstation model 3`processor pool 4`Issues 5`global knowledge 6`naming 7` scalability 8`compatibility 9`'process synchronization, communication :` security ;` structure <` Networks =`goals >`!message, packet, subnet, session ?`Yswitching: circuit, store-and-forward, message, packet, virtual circuit, dynamic routing @`OSI model: PDUs, layering A`*physical: ethernet, aloha,  etc . B`8data link layer: frames, parity checks, link encryption !C jnetwork layer: virtual circult vs. datagram, routing via flooding, static routes, dynamic routes, central@jized routing vs. distributed routing; congestion solutions (packet discarding, isarithmic, choke packets) !D gtransport: services provided (UDP vs. TCP), functions to higher layers, addressing schemes (flat, DNS, @,etc.), gateway fragmentation and reassembly E`:session: adds session characteristics like authentication F`Cpresentation: compression, end-to-end encryption, virtual terminal G`!application: user-level programs H`Clocks I`happened-before relation J`|Lamports distributed clocks:  a      b  means  C ( a ) <  C ( b ) K`yExample where  C ( a ) <  C ( b ) does  not  mean  a      b L`"Vector clocks and causal relation M`;ordering of messages so you receive them in the order sent N`why O`0for broadcast (ISIS): Birman-Schiper-Stephenson P`)for point to point: Schiper-Eggli-Sandoz R` Global state S`;Show problem of slicing state when something is in transit T*`?Define local state;  send ( m ij )     LS i  iff time of  send ( m ij ) < current time of  LS i ; similar for receive U< =transit( LS i ,  LS j ); inconsistent( LS i ,  LS j ); consistent state is one with inconsistent set empty for all pairs  LS i , @ LS j VUU`)Consistent global state: Chandry-Lamport Wd*t`Termination detection AX`Haung HHˆ;6HHˆf66 lH$ @5!:H$ 99l H$ @6!H$ 8WhN Outline for January 23, 2001ECS 251 Winter 2001Page  1  HUV @7!8HHUV GGl$lzQ7 <$lz$ll6 Q8;=6 ? Q9<>?  Q:=? xUU Q;>@xUU  Q<?A Sh Q=@JSh }?H =x1C?H FW-e¢ }H =zB2H FW.e d=~EEd=DdFF l d=Dd& zrE zupkfa\WRMHC>vCFILORUX[^adgjmpsy| %).12/,)&# HUV @8!HUV :WlALast modified at 2:14 pm on Tuesday, January 23, 2001 HHˆ@9!:HHˆII l HHˆ@:!HHˆHW`  Q>AK gh Q?JLgh dUVUU Q@KMdUVUU UU+ӌ"GwQALNUU+ӌ"GwUU^UU^P 1 UU)"GwQBMOUU)"GwUU@VUU@VP 2 UUg+ӌ"GwQCNPUUg+ӌ"GwUUo^UUo^P 3 @z'݈QDOQ@z'݈@@e11 UUz'݈QEPRUUz'݈UUUUe12 z$ҍ݈QFQSz$ҍ݈zUzUe21 $ҍ݈QGRT$ҍ݈UUe22 $ҍ݈QHSU $ҍ݈ U Ue23 GUU]}݈QITVGUU]}݈GUUa^GUUa^e31 j^z'݈QJUWj^z'݈jbjbe32 $QKVX$UU b}݈QLWYb}݈b^b^e13PUUQM XZPUU^UUUUU QN Y[UUUUU UUUdU$BUB&QO Z\$BUB&$BUgUVhUYUUB"(QP []YUUB"(YUUj{UUB QQ\^ )UVp@QR ])UVp@)UV^)UV^e24H]wKxQdg`|h4zQe_a4z44zQf_`b4z44fzQg_ac4fz4ffF Qh_bdF O Qi_ceO < Qj_df< UU< Qk_egUU< < Ql_fh< cc< Qm_gicc< -< Qn_hj-< wb Qo_ikwb tUVN Qp_jltUVN UǓ"GwQq_kmUǓ"GwUUUUP 1 UU""GwQr_lnUU""GwUUEOUUEOP 2 UUǎ"GwQs_moUUǎ"GwUUiUUiP 3 P ݈Qt_npP ݈PPe11 UU ݈Qu_oqUU ݈UUUUe12 ˍ݈Qv_prˍ݈ENENe21 ˍ݈Qw_qsˍ݈ENENe22 ˍ݈Qx_rtˍ݈ENENe23 WUUXav݈Qy_suWUUXav݈WUU[WUU[e31 zY ݈Qz_tvzY ݈z\z\e32 rav݈Q{_uwrav݈rre13PUUQ| _vxPUUUUENUU Q} _wyUUENUU UUENtEN4ENB&Q~ _xz4ENB&4ENwUVcENiUU"(Q _y{iUU"(iUUdUU< Q_z|< 9UVp@Q _{9UVp@9UV9UVe24HTuUTQmUT~n6zQ}6z6UTzQ}~UTzUTUT6czQ}6cz6ccH Q}H x| Q}x| UUx{ Q}UUx{ x| Q}x| e`x| Q}e`x| y_ Q}y_ vUV#& Q}vUV#& UU"GwQ} UU"GwUU+ѡUU+P 1 UUN"GwQ} UUN"GwUU'UU'P 2 UU^"GwQ} UU^"GwUUg+ѡUUg+P 3 #\3݈Q} #\3݈ # #e11 ݈Q} ݈&&e21 ݈Q} ݈&&e22 YUUUN݈Q} YUUUN݈YUUY+YUUY+e31 |VG݈Q}|VG݈|Y{|Y{e32 tN݈Q}tN݈t+t+e12UU&UU Q }UU&UU UU&v&UU5Q }UU5UU5yUV`&kUU{"(Q }kUU{"(kUUa{UU{mUU5ZLQ }mUU5ZLmUU`55 | ]Q }| ]||HTuUTQsUT4t6zQ6z6UTzQUTzUTUT6czQ6cz6ccH QH x| Qx| UUx{ QUUx{ x| Qx| e`x| Qe`x| UV_.UT Q UV_.UT HUVx| Q!HUVx| UU"GwQ "UU"GwUU+ѡUU+P 1 UUN"GwQ!#UUN"GwUU'UU'P 2 UU^"GwQ"$UU^"GwUUg+ѡUUg+P 3 #\3݈Q#% #\3݈ # #e11 ݈Q$&݈&&e21 ݈Q%'݈&&e22 YUUUN݈Q&(YUUUN݈YUUY+YUUY+e31 VUU݈Q')VUU݈YYe32 F݈Q(*F݈F'F'e12ƪ'Q )+ƪ'ƪ+KUVTNQ *,TN`kUU{"(Q +-kUU{"(kUUa{UU{ ^U\Q,.^U\_k_k Ox| Q-/Ox| Z݈Q.0Z݈Z'Z'e23 UUUQ /1UUUUUU5UUU5 >Q 02>>4>4SUVUVAQ 13SUVUVASUVUUUTUV G݈Q24G݈}}e13UV Q3UV HTsUVR|UV6T}UU"EXhR 57UU"EXhUU"EUUn"E M{񻈣R568M{񻈣Q Q  s1ફ"EWUUiUUR 579ફ"EWUUiUUફ"E8ow &MR 58:&M&Qw&Qws2UUzR59;UUzUUUUUUzR5:<UUzUUUUUUazR5;=UUazUUaUUaRUU R 5<>RUU UVV6 R!5=?UVV6 V5 R"5>@V5 UVV6 R#5?AUVV6 fUU^V6 R$5@BfUU^V6 0UUV6 R%5AC0UUV6 zUU] R&5BDzUU] w R'5CEw ^"GwR(5DF^"Gw P 1 ,"GwR)5EG,"Gw^ᢪ^P 2 \^"GwR*5FH\^"Gwe e P 3 SUU%݈R+5GISUU%݈SUU5SUU5e11 ʪ%݈R,5HJʪ%݈ʪ5ʪ5e12 ]݈R-5IK]݈^^e21 UU]݈R.5JLUU]݈UU^UU^e22 UU]݈R/5KMUU]݈UU^UU^e23 ZS{݈R05LNZS{݈ZW ZW e31 u{݈R15MOu{݈u u e13UU6PUUR2 5NPUU6PUUUU6 ƪ^UU R3 5OQƪ^UU ƪ^w^7^B&R4 5PR7^B&7^z^^l5"(R5 5QSl5"(l_55V6 R65RTV6 <5p@R7 5S<5p@< < e24H*Rd7Vc8ĀUURe UWĀUU@o*UURf UVX@o*UU>IUURg UWY>IUUpo*UURh UXZpo*UUoUVc~UURi UY[oUVc~UUĂUVRj UZ\ĂUVĂ@Ko-ENĂUVRk U[]ENĂUVENĂqUUeo-o-UVRl U\^o-UVo-Bo-GUUo-UURm U]_GUUo-UUGUUJĂro- E^ Rn U^`E^ @؄@P0 J Ro U_aJ Jo-Jo-P1 UU Rp U`bUU UUo-UUo-P2 t Rq Uact tĂtĂP3 tS Rr UbtS tZĂtZĂP4dR{ff HHˆR|dHHˆL: fY `Lamports Clocks Z,` Introduction [ oLamports clocks keep a virtual time among distributed systems. The goal is to provide an ordering upon events I@within the system. \b` Notation ]*t`P i  process ^`9C i . clock associated with process  P i _` Protocol `*UL`2Increment clock  C i  between any two successive events in process  P i :  C i      C i  +  d  ( d  > 0) aUL*"  >Let event  a  be the sending of a message by process  P i ; the timestamp is  t a  =  C i ( a )  after  the clock is incremented. ΢@_Let  b  be the receipt of that message by  P j . Then when  P j  receives the message,  C j     max( C j ,  t a  +  d ) ( d  > 0) b̨"h Example  cwR`Assume all clocks start at 0, and  d  is 1 (that is, each event incrememts the clock by 1). The events and clocks are: *wQ`/e 11 :  C 1     1 }UL*E`ce 31 :  C 3     1; timestamp  t 3,1   of message is 1 .U`se 21 :  C 2     2 as  t 3,1  = 1, after the increment  C 2     1, and  C 2     max( C 2 ,  t 3,1  + 1) = max(1, 1 + 1) = max(1, 2) = 2 `ce 22 :  C 2     3; timestamp  t 2,2   of message is 3 `ce 12 :  C 1     2; timestamp  t 1,2   of message is 2 `se 23 :  C 2     4 as  t 1,2  = 2, after the increment  C 2     4, and  C 2     max( C 2 ,  t 1,2  + 1) = max(4, 2 + 1) = max(4, 2) = 4 `ce 24 :  C 2     5; timestamp  t 2,4   of message is 5 `se 13 :  C 1     4 as  t 2,2  = 3, after the increment  C 1     3, and  C 1     max( C 1 ,  t 2,2  + 1) = max(3, 3 + 1) = max(3, 4) = 4 `se 32 :  C 3     6 as  t 2,4  = 5, after the increment  C 3     2, and  C 3     max( C 3 ,  t 2,4  + 1) = max(2, 5 + 1) = max(2, 6) = 6 d6`Problem eHLC`=Clearly, if a    b, then  C ( a ) <  C ( b ). But if  C ( a ) <  C ( b ), does  a      b ? f*TLB RThe answer, surprisingly, is not necessarily. In the above example,  C 3 ( e 31 ) = 1 < 2 =  C 1 ( e 12 ). But  e 31  and  e 12  are causb!ally unrelated; that is,  e 31    / e 12 . However,  C 1 ( e 11 ) = 1 < 6 =  C 3 ( e 32 ), and clearly  e 11      e 32 . Hence one cannot say UU@one way or the other. Qg{` HHˆR~dHHˆ7iee ldRii HHˆRgHHˆ€!^ __ih `Vector Clocks i,` Introduction j uThis is based upon Lamports clocks, but each process keeps track of what is believes the other processes interrnal I@nclocks are (hence the name, vector clocks). The goal is to provide an ordering upon events within the system. kb` Notation lt`n  processes m*`P i  process n AC i . vector clock associated with process  P i ;  j th element is  C i [ j ] and contains  P i s latest value for the current time @in process  P k . o` Protocol p**`LIncrement clock  C i  between any two successive events in process  P i :  C i [ i ]     C i [ i ] +  d  ( d  > 0) qUL*] >Let event  a  be the sending of a message by process  P i ; its vector timestamp is  t a  =  C i ( a )  after  the clock is incre*̯mented.. Let  b  be the receipt of that message by  P j . Then when  P j  receives the message, it updates its vector UL*L@clock for all  k  = 1, ,  n :  C j [ k ]    max( C j [ k ],  t a [ k ]) rwK"h Example Q!`9Here is the progression of time for the three processes: s*!`7e 11 :  C 1     (1, 0, 0) tUL*`se 31 :  C 3     (0, 0, 1); timestamp  t 3,1   of message is (0, 0, 1) 1uFn ~e 21 :  C 2     (0, 1, 1) as  t 3,1  = (0, 0, 1),  C 2     (0, 1, 0) after the increment,  C 2 [0]    max( C 2 [0],  t 3,1 [0]) = max(0, 0) = 0, @FC 2 [1]    max( C 2 [1],  t 3,1 [1]) = max(1, 0) = 1, and  C 2 [2]    max( C 2 [2],  t 3,1 [2]) = max(0, 1) = 1 v`se 22 :  C 2     (0, 2, 1); timestamp  t 2,1   of message is (0, 2, 1) w`se 12 :  C 1     (2, 0, 0); timestamp  t 1,1   of message is (2, 0, 0) ! }e 23 :  C 2     (2, 3, 1) as  t 1,1  = (2, 0, 0),  C 2     (0, 3, 1) after the increment,  C 2 [0]    max( C 2 [0],  t 1,1 [0]) = max(0, 2) = 2, @FC 2 [1]    max( C 2 [1],  t 1,1 [1]) = max(3, 0) = 3, and  C 2 [2]    max( C 2 [2],  t 1,1 [2]) = max(0, 1) = 1 y`se 24 :  C 2     (2, 3, 1); timestamp  t 2,2   of message is (2, 3, 1) !z }e 13 :  C 1     (3, 2, 1) as  t 2,1  = (0, 2, 1),  C 1     (3, 0, 0) after the increment,  C 1 [0]    max( C 1 [0],  t 2,1 [0]) = max(3, 0) = 3, @FC 1 [1]    max( C 1 [1],  t 2,1 [1]) = max(2, 0) = 2, and  C 1 [2]    max( C 1 [2],  t 2,1 [2]) = max(1, 0) = 1 !x }e 32 :  C 3     (2, 3, 2) as  t 2,2  = (2, 3, 1),  C 3     (0, 0, 2) after the increment,  C 3 [0]    max( C 3 [0],  t 2,2 [0]) = max(2, 0) = 2, @FC 3 [1]    max( C 3 [1],  t 2,2 [1]) = max(3, 0) = 3, and  C 3 [2]    max( C 3 [2],  t 2,2 [2]) = max(1, 2) = 2 _|*z`4Notice that  C 1 ( e 11 ) <  C 3 ( e 32 ), so  e 11      e 32 , but  C 1 ( e 11 ) and  C 3 ( e 31 ) are incomparable, so  e 11  and  e 31  are concurrent. HHˆRgHHˆflhh ldRll HHˆRjHHˆsnl~ `#Birman-Schiper-Stephenson Protocol ,` Introduction * %The goal of this protocol is to preserve ordering in the sending of messages. For example, if  send ( m 1 )    send( m 2 ), Kathen for all processes that receive both  m 1  and  m 2 ,  receive ( m 1 )    receive ( m 2 ). The basic idea is that  m 2  is not given to [the process until  m 1  is given. This means a buffer is needed for pending deliveries. Also, each message has an associUUuated vector that contains information for the recipient to determine if another message preceded it. Also, we shall s*@Sassume all messages are broadcast. Clocks are updated only when messages are sent. ` Notation *`n  processes **`P i  process  AC i . vector clock associated with process  P i ;  j th element is  C i [ j ] and contains  P i s latest value for the current time UB@in process  P k . ULUUU5`kt m  vector timestamp for message  m  (stamped  after  local clock is incremented) 慠` Protocol *U4`'P i  broadcasts a message  UL*(`P i  increments  C i [ i ] and sets the timestamp  t m  =  C i  for message  m .  *z`2P j  receives a message from  P i  UL*0*n`!When  P j ,  j   i , receives  m  with timestamp  t m , it delays the messages delivery until  both :  U`DC j [ i ] =  t m [ i ] 1; and  `for all  k   n  and  k   i ,  C j [ k ]  t m [ k ]. a`tWhen the message is delivered to  P j , update  P j s vector clock for all  k  = 1, ,  n :  C j [ k ]    max( C j [ k ],  t a [ k ]) Up4`8Check buffered messages to see if any can be delivered. HHˆRjHHˆiokk ldRoo HHˆRmHHˆ|0 }o"h Example `5Here is the protocol applied to the above situation: UL*`ye 31 :  P 3  sends message  a ;  C 3  = (0, 0, 1);  t a  = (0, 0, 1) * e 21 :  P 2  receives message  a . As  C 2  = (0, 0, 0),  C 2 [3] =  t a [3] 1 = 1 1 = 0 and  C 2 [1]  t a [1] and  C 2 [2]  t a [2] = 0. So *@>the message is accepted, and C 2  is set to (0, 0, 1)  UL*`ye 22 :  P 2  sends message  b ;  C 2  = (0, 1, 1);  t b  = (0, 1, 1) O e 11 :  P 1  receives message  a . As  C 1  = (0, 0, 0),  C 1 [3] =  t a [3] 1 = 1 1 = 0 and  C 1 [1]  t a [1] and  C 1 [2]  t a [2] = 0. So *@Cthe message is accepted, and  C 1  is set to (0, 0, 1) UL*U e 12 :  P 1  receives message  b . As  C 1  = (0, 0, 1),  C 1 [2] =  t b [2] 1 = 1 1 = 0 and  C 1 [1]  t b [1] and  C 1 [3]  t b [2] = 0. So * *e@Cthe message is accepted, and  C 1  is set to (0, 1, 1) UL*Y e 32 :  P 3  receives message  b . As  C 3  = (0, 0, 1),  C 3 [2] =  t b [2] 1 = 1 1 = 1 and  C 1 [1]  t b [1] and  C 1 [3]  t b [2] = 0. So *'@Cthe message is accepted, and  C 3  is set to (0, 1, 1) UL*C"hNow, suppose  t a  arrived as event  e 12 , and  t b  as event  e 11 :  {**E`BThen the progression of time in  P 1  goes like this: UL*ܪ9`ye 31 :  P 3  sends message  a ;  C 3  = (0, 0, 1);  t a  = (0, 0, 1) o_ e 21 :  P 2  receives message  a . As  C 2  = (0, 0, 0),  C 2 [3] =  t a [3] 1 = 1 1 = 0 and  C 2 [1]  t a [1] and  C 2 [2]  t a [2] = 0. So *@>the message is accepted, and C 2  is set to (0, 0, 1)  UL* s`ye 22 :  P 2  sends message  b ;  C 2  = (0, 1, 1);  t b  = (0, 1, 1) #Tm e 11 :  P 1  receives message  b . As  C 1  = (0, 0, 0),  C 1 [2] =  t b [2] 1 = 1 1 = 0 and  C 1 [1]  t b [1], but  C 1 [3] <  t b [3], so the )Թ@_message is held until another message arrives. The vector clock updating algorithm is not run. UL*8Z e 12 :  P 1  receives message  a . As  C 1  = (0, 0, 0),  C 1 [3] =  t a [3] 1 = 1 1 = 0,  C 1 [1]  t a [1], and  C 1 [2]  t a [2]. The mesHNCsage is accepted and  C 1  is set to (0, 0, 1). Now the queue is checked. As  C 1 [2] =  t b [2] 1 = 1 1 = 0,  C 1 [1]  t b [1], @uand  C 1 [3]  t b [3], that message is accepted and  C 1  is set to (0, 1, 1).   e 32 :  P 3  receives message  b . As  C 3  = (0, 0, 1),  C 3 [2] =  t b [2] 1 = 1 1 = 1 and  C 1 [1]  t b [1] and  C 1 [3]  t b [2] = 0. So ^*wԈ@Cthe message is accepted, and  C 3  is set to (0, 1, 1) HHˆRmHHˆlrnn ldRrr HHˆRpHHˆ L   r `Schiper-Eggli-Sandoz Protocol ,` Introduction  vThe goal of this protocol is to ensure that messages are given to the receiving processes in order of sending. Unlike Iqthe Birman-Schiper-Stephenson protocol, it does not require using broadcast messages. Each message has an associ0Wxated vector that contains information for the recipient to determine if another message preceded it. Clocks are updated @only when messages are sent. z` Notation `n  processes  *`P i  process ! AC i . vector clock associated with process  P i ;  j th element is  C i [ j ] and contains  P i s latest value for the current time @in process  P k . "ULUU=`kt m  vector timestamp for message  m  (stamped  after  local clock is incremented) #*`2t i  current time at process  P i $ CV i  vector of  P i s previously sent messages;  V i [ j ] =  t m , where the last message sent to  P j  has the vector timestamp @|t m ;  V i [ j ][ k ] is the  k th component of  V i [ j ]. %UU`0V m  vector accompanying message  m &U` Protocol '*/`-P i  sends a message to  P j (UL*@`}P i  sends message  m , timestamped  t m , and  V i , to process  P j  . )QLm`PP i  sets  V i [ j ]     t m . **_n`2P j  receives a message from  P i +mC`}When  P j ,  j   i , receives  m , it delays the messages delivery if  both : ,ULUU}`&V m [ j ] is set; and -nr`)V m [ j ] <  t j nq`+Otherwise it is queued for later delivery. .*<`^If the message can be delivered to  P j ,  the following three actions occur:  UL*`Update all set elements of  V j  with the corresponding elements of  V m , except for  V j [ j ], as follows: /`dIf  V j [ k ] and  V m [ k ] are uninitialized, do nothing. 0`5If  V j [ k ] is uninitialized and  V m [ k ] is initialized, set  V j [ k ]     V m [ k ]. 1`,If both  V j [ k ] and  V m [ k ] are initialized,  V j [ k ][ k  ]    max( V j [ k ][ k  ],  V m [ k ][ k  ]) for all  k   = 1, ,  n 2Ԙ`@Update  P j s vector clock for all  k  = 1, ,  n :  C j [ k ]    max( C j [ k ],  t m [ k ]) U3`8Check buffered messages to see if any can be delivered. HHˆRpHHˆouqq ldRuu HHˆRsHHˆY: u4"h Example 5 }Here is the protocol applied to the above situation. [ ... ] and { ... } are like ( ... ) but used when too many parentheses @*would be confusing (to me, at any rate!): 6UL*`e 31 :  P 3  sends message  m 3,1  to  P 2 .  C 3  = (0, 0, 1);  t 3,1     (0, 0, 1),  V 3,1     (?, ?, ?);  V 3     [ ?, (0, 0, 1), ? ] 7* 2e 21 :  P 2  receives message  m 3,1  from  P 3 . As  V 3,1 [2] = (?, ?, ?)[2] is uninitialized, the message is accepted. *@xV 2     [ ?, ?, ? ] and  C 2      max [(0, 0, 0), (0, 0, 1)] = (0, 0, 1) 8UL*` e 22 :  P 2  sends message  m 2,1  to  P 1 .  C 2     (0, 1, 1);  t 2,1     (0, 1, 1),  V 2,1     [ ?, ?, ? ];  V 2     [ (0, 1, 1), ?, ? ]  i` e 11 :  P 1  sends message  m 1,1  to  P 3 .  C 1     (1, 0, 0);  t 1,1     (1, 0, 0),  V 1,1     ( ?, ?, ? );  V 1     [ ?, ?, (1, 0, 0) ] :i 4e 32 :  P 3  receives message  m 1,1  from  P 1 . As  V 1,1 [3] = ( ?, ?, ? )[3] is uninitialized, the message is accepted. *U@V 3     [ ?, (0, 0, 1), ? ] and  C 3      max [(0, 0, 1), (1, 0, 0)] = (1, 0, 1). 9UL* 4e 12 :  P 1  receives message  m 2,1  from  P 2 . As  V 2,1 [1] = [ ?, ?, ? ][1] is uninitialized, the message is accepted. *%X@V 1     [ ?, ?, (1, 0, 0) ] and  C 1      max [(1, 0, 0), (0, 1, 1)] = (1, 1, 1) U< 2e 21 :  P 2  receives message  m 3,1  from  P 3 . As  V 3,1 [2] = (?, ?, ?)[2] is uninitialized, the message is accepted. **@xV 2     [ ?, ?, ? ] and  C 2      max [(0, 0, 0), (0, 0, 1)] = (0, 0, 1) @UL*` e 22 :  P 2  sends message  m 2,1  to  P 1 .  C 2     (0, 1, 1);  t 2,1     (0, 1, 1),  V 2,1     [ ?, ?, ? ];  V 2     [ (0, 1, 1), ?, ? ] Q` e 11 :  P 1  sends message  m 1,1  to  P 3 .  C 1     (1, 0, 0);  t 1,1     (1, 0, 0),  V 1,1     ( ?, ?, ? );  V 1     [ ?, ?, (1, 0, 0) ] Q 4e 32 :  P 3  receives message  m 1,1  from  P 1 . As  V 1,1 [3] = ( ?, ?, ? )[3] is uninitialized, the message is accepted. *@V 3     [ ?, (0, 0, 1), ? ] and  C 3      max [(0, 0, 1), (1, 0, 0)] = (1, 0, 1). UL*`e 23 :  P 2  sends message  m 2,2  to  P 1 .  C 2     (0, 2, 1);  t 2,2     (0, 2, 1),  V 2,2     [ (0, 1, 1), ?, ? ];  V 2     [ (0, 2, 1), ?, ? ] ?T`Ke 12 :  P 1  receives message  m 2,2  from  P 2 . But  V 2,2 [1] = (0, 1, 1) < / (1, 0, 0) =  C 1 , so the message is queued. T 4e 13 :  P 1  receives message  m 2,1  from  P 2 . As  V 2,1 [1] = [ ?, ?, ? ][1] is uninitialized, the message is accepted. */V 1     [ ?, ?, (1, 0, 0) ] and  C 1      max [(1, 0, 0), (0, 1, 1)] = (1, 1, 1). UL*@T The message on the queue is now checked. As  V 2,2 [1] = (0, 1, 1) < (1, 1, 1) =  C 1 , the message is now accepted. ^*N*0@XV 1     [ ?, ?, (1, 0, 0) ] and  C 1  is set to (1, 2, 1). HHˆRvHHˆu{ww ldR{{ HHˆRyHHˆ{ A `/Chandy-Lamport Global State Recording Protocol B,` Introduction C vThe goal of this distributed algorithm is to capture a consistent global state. It assumes all communication channels I@\are FIFO. It uses a distinguished message called a  marker  to start the algorithm. Db` Protocol E*t`P i  sends marker F`4Pi  records its local state  LS i  G` For each  C ij  on which  P i  has not already sent a marker,  P i  sends a marker  before  sending other messages. H`/P i  receives marker from  P j I`;If  P i  has  not  recorded its state: J `0Record the state of  C ji  as empty KUU`#Send the marker as described above L*Ԑ`:If  P i  has recorded its state  LS i M Record the state of  C ji  to be the sequence of messages received between the computation of  LS i  and the Pg@ marker from  C ji . HHˆRyHHˆx~zz ldR~~ HHˆR|HHˆa55~ N"l Example O*$Here, all processes are connected by communications channels  C ij . Messages being sent over the channels are repreUURD(sented by arrows between the processes. P*QdSnapshot  s 1 : Qd_P 1  records  LS 1 , sends markers on  C 12  and  C 13 RGUH$JP 2  receives marker from  P 1  on  C 12 ; it records its state  LS 2 , records state of  C 12  as empty, and sends marker on  C 21  Dand  C 23 S$JP 3  receives marker from  P 1  on  C 13 ; it records its state  LS 3 , records state of  C 13  as empty, and sends markers on  C 31  Dand  C 32 . Td#P 1  receives marker from  P 2  on  C 21 ; as  LS 1  is recorded, it records the state of  C 21  as empty. Ud#P 1  receives marker from  P 3  on  C 31 ; as  LS 1  is recorded, it records the state of  C 31  as empty. Vd#P 2  receives marker from  P 3  on  C 32 ; as  LS 2  is recorded, it records the state of  C 32  as empty. Wd#P 3  receives marker from  P 2  on  C 23 ; as  LS 3  is recorded, it records the state of  C 23  as empty. XdfSnapshot  s 2 : now messages are in transit on  C 12  and  C 21 . Yd_P 1  records  LS 1 , sends markers on  C 12  and  C 13 Z$LP 2  receives marker from  P 1  on  C 12  after the message from  P 1  arrives; it records its state  LS 2 , records state of  C 12  as DAempty, and sends marker on  C 21  and  C 23 [$JP 3  receives marker from  P 1  on  C 13 ; it records its state  LS 3 , records state of  C 13  as empty, and sends markers on  C 31  Dand  C 32 . \$:P 1  receives marker from  P 2  on  C 21 ; as  LS 1  is recorded, and a message has arrived since  LS 1  was recorded, it records D@H6H F9W+eEM }6H HD?A6H F9W,eN }6H HD@B6H F9W-eN } 6H HDAv 6H F9W.e }*H HDLD*H FRW/eC:Superscript }H*H HDCEH*H FRW0eEM }*H HDDF*H FRW1eN }*H HDEG*H FRW2eN } *H HDF> *H FRW3e }H HDQIH FSW4e C:Subscript }HH HDHJHH FSW5eEM }H HDIKH FSW6eN }H HDJLH FSW7eN } H HDKC H FSW8e }H HDVNH FTW9e C:Emphasis }HH HDMOHH FTW:eEM }H HDNPH FTW;eN }H HDOQH FTW<eN } H HDPH H FTW=e }H HD[SH FUW>e C:Computer }HH HDRTHH FUW?eEM }H HDSUH FUW@eN }H HDTVH FUWAeN } H HDUM H FUWBe }H(HD`XH( FVWCe P:Romani }HH(HDWYHH((FV$eLI De Parent = OL Qe Depth = 0 }H(HDXZH( FVWEeN }H(HDY[H( FVWFeN } H(HDZR H( FVWGe }H(HDe]H( FWWHeP:Roman }HH(HD\^HH((FW$eLI Ie Parent = OL Qe Depth = 0 }H(HD]_H( FWWJeN }H(HD^`H( FWWKeN } H(HD_W H( FWWLe }HHDjbHFXM% P:LineComPEment }HHHDacHH FXWNeH* }HHDbdH FXWOeN }HHDceH FXWPeN } HHDd\ H FXWQe }H IDogH FYWReP:Line }HH IDfhHH FYWSeP }H IDgiH FYWTeN }H IDhjH FYWUeN } H I Dia H FYWVe }H I DtlH FZWWe P:Lettereda }HH I DkmHH FZWXeH* }H IDlnH FZWYeN }H IDmoH FZWZeN } H IDnf H FZW[e }\H(IDyq\H( F[W\e P:Lettered }H\H(IDprH\H((F[$eLI ]e Parent = OL Qe Depth = 0 }\H(IDqs\H( F[W^eN }\H(IDrt\H( F[W_eN } \H(IDsk \H( F[W`e }PH ID~vPH F\WaeP:CodeN }HPH I!DuwHPH F\WbeP }PH I#DvxPH F\WceN }PH I%DwyPH F\WdeN } PH I'Dxp PH F\Wee }6HI)D{6HF]f% P:CodeComPEment }H6HI+Dz|H6H F]WgeP }6HI-D{}6H F]WheN }6HI/D|~6H F]WieN } 6HI1D}u 6H F]Wje }H I3H ^GkeP:CodeC }H I5H ^GleP }H I7H ^GmeN }H I9H ^GneN }H I;H ^Goe }H I= H _Gpe P:CodeASM }H I?H _GqeP }H IAH _GreN }H ICH _GseN }H IEH _Gte }H IG H `Gue P:BodyIndent }H II H `GveP }H IK H `GweN }H IM H `GxeN }H IO H `Gye }H(IQBH( aGze P:Answer1 }H(ISH((aeLI {e Parent = UL Ae Depth = 0 }H(IUH( aG|eN }H(IWH( aG}eN }H(IY H( aG~e dIf" dIgds%sy| %).12/,)&#dIidE l}6DJD6DFb% CSS Export PE Encoding }D6HJDD6H FbWe ISO-8859-1 }6HJDX6H FbW e }DJDWDFc % Export EnPEcoding }DHJDDH FcW e ISO-8859-1 }HJDH FcW e }HKS H  dG e1 }HKU H dG* eTitle }HKW H  dGe x| V" x| e`x| V!e`x| UV_.UT V "UV_.UT `UV#' V!#`UV#' UU"GwV"$UU"GwUU+ѡUU+P 1 UUN"GwV#%UUN"GwUU'UU'P 2 UU^"GwV$&UU^"GwUUg+ѡUUg+P 3 #\3݈V%' #\3݈ # #e11 ݈V&(݈&&e21 ݈V')݈&&e22 YUUUN݈V(*YUUUN݈YUUY+YUUY+e31 VUU݈V)+VUU݈YYe32 ^O݈V*,^O݈^+^+e12ƪ+%V +-ƪ+%ƪ++%TNV ,.TN`kUU{"(V -/kUU{"(kUUa{UU{ ^U\V.0^U\_k_k Ox| V/1Ox| Z݈V02Z݈Z'Z'e23 UUUV 14UUUUUU5UUU5SUV+%*0V 25SUV+%*0SUVUUcUV+% G݈V46G݈}}e13UV V5UV dW99 HHˆW7HHˆLf&&UU9 ` d'Huangs Termination Detection Protocol a,d Introduction bdRThe goal of this protocol is to detect when a distributed computation terminates. cVd Notation dhdn  processes e*tdfP i  process; without loss of generality, let  P 0  be the  controlling agent fd W i . weight of process  P i ; initially,  W 0  = 1 and for all other  i ,  W i  = 0. gUUzULdDB ( W ) computation message with assigned weight  W hUKdgC ( W ) control message sent from process to controlling agent with assigned weight  W id Protocol j*UJd9P i  sends a computation message to  P j k*dhSet  W i  and  W j  to values such that  W i  +  W j  =  W i ,  W i  > 0,  W j  > 0. ( W i  is the new weight of  P i .) lLd4Send  B ( W j ) to  P j mdWP j  receives a computation message  B ( W ) from  P i nD*d*W j  =  W j  +  W o fHd?If  P j  is idle,  P j  becomes active pE*dP i  becomes idle: q)]d4Send  C ( W i ) to  P 0 r7dW i  = 0 s3dP i  becomes idle tdBP i  receives a control message  C ( W ): uadd*W i  =  W i  +  W vod9If  W i  = 1, the computation has completed. w*dExample x*$`The picture shows a process  P 0 , designated the  controlling agent , with f&" W 0  = 1. It asks  P 1  and  P 2  to do some computation. It sets  W 1  to 0.2,  W 2  to 2 0.3, and  W 3  to 0.5.  P 2  in turn asks  P 3  and  P 4  to do some computations. It D: . f@ < BodySpaced. f@N < Numbered N:.< =1>. f@ <...Date. mf@ <l. DateProject. @@ <Header Double Line. f@  $.6.Z.~..CodeC. f@T <Heading1Body. $f@ < Answer. f@ < NumberedSpaced. f@ <Body. @@ <Header Double Line. f@ < CellFooting. f@ < CellHeading. f@ < CellBody. @@ <Mapping Table Cell. f@ <.Reading. @@Mapping Table Cell.  f@P<TitleBody. @@ Mapping Table Cell. @@ <Mapping Table Cell. f@$<.Line Single Line.  f@P<TitleBody. f@ <CellBody. f@ < CellHeading. f@ < Footnote. f@T <Heading2Body. f@T < HeadingRunInBody. f@ < Indented. f@ < TableFootnote. f@NE < Numbered1 N:.Numbered. f@ < NumberedSpaced. f@T <Heading1Body. $f@LE <$. Lettereda L:.Lettered. f@NE < Numbered1 N:. Lettereda. f@NE < Numbered1 N:. Lettereda. f@T < TableTitleT:Table : . L̀Lf@N < Numbered N:.< =1>. $f@LE <$. Lettereda L:.Lettered. $f@L <$. LetteredL:.. f@ < Bulleted\t. 6$f@R <6. RomanR:.. f@T <Heading1Body. UUf@ <Body. f@T <Heading2Body. f@ <Body. 6$f@R <6. Romani R:.. f@ < Bulleted\t. f@N < Numbered N:.< =1>. $f@L <$. LetteredL:.. f@ <Body. 6$f@R <6. Romani R:.. 6$f@R <6. RomanR:.. f@ < BodyIndent. f@  $.6.Z.u..CodeASM. Hf@ <H.. CodeComment. f@   .$.H.l..... .D.h.CodeN. Hf@ <H. LineComment. @@ <Mapping Table Cell. @@<*Mapping Table Cell. $ < <<Emphasis <  < ڝ<<<EquationVariables   BoldItalic <Italic 8 Symbol ڝ< < < Subscript < < < <Bold8 Symbol   Computer < Superscript < < Subscript < 348 Symbol < <  <  <q7< Subscript < < < Superscript < Subscript < Superscript < Superscript B  Wingding<ZZdZdZZdZdZdZdZdThinMediumDoubleThick@ Very Thin HHHHHFormat A HHHHHFormat BH Mapping TableH Mapping Tableh65HHHHH$bDHH+4?HHH68?HH :C?HHHTDL?HH*H ? @ h( A B C D E h  F G H I J h  K L M N O h  P Q R S T h( UVWXYh Z[\]^h_`abc7h defghChijklm]h(nopqrh stuvwh xyz{|h(}~h h    h  h h h)h  !"#$5h%&'()Oh  *+,-.[h!/ 0 1 2 3 uh "4!5!6!7!8!h!#9":";"<"="©h "a>#?#@#A#B#Td %FC$D$E$d $&FF%G%H%p6%'FI&J&K& &(FL'M'N'')FO(P(Q(((*FR)S)T)()cFU*V*W*Vd ,FX+Y++Z+f +-F[,\,,],r ,.F^-_--`-~ -/Fa.b.5.c.Š.0Fd/e/6/f/¤/1Fg0h070i0¾02Fj1k181l113Fm2n292o224Fp3q3:3r33s4t4;4u4Bh 9Fv5w5x5<5=59?9@9A9B9xd ;:::: :C ;";#;$; =  <<<<> ====? >>>K >@ ???W ?A @@@c @d AAA ;%C&C'C(Cd E)D,D-D DF.E/E0E EQ1FBFCF M#L$L%L NL&M'M(M OM)N*N+N PN,O-O.O QO/P0P1P FP2Q3Q4Q*h S9FCRDRERFRGRh TRFHSISJSKSLSh USFMTNTOTPTQTh VTFRUSUTUUUVUh(WUFWVXVYVZV[Vh(XVF\W]W^W_W`WhYWFaXbXcXdXeXh ZXFfYgYhYiYjYh [YFkZlZmZnZoZ\h(\ZFp[q[r[s[t[Ph ][Fu\v\w\x\y\6h^\Fz]{]|]}]~]h _]^^^^^h `^_____h a_ ` ` ` ` `h(#`aaaaa6cFbbb*bFcccA dddComment @D @<@@ d@ BlackT!WhiteddARedddGreendd BluedCyandMagentad Yellowd PICT Color 1Header/Footer $1Header/Footer $1Header/Footer $2Header/Footer $2IndexIndexCommentCommentSubjectSubjectAuthorAuthorGlossaryGlossaryEquationEquation Hypertext Hypertext  Cross-Ref Cross-Ref Conditional TextConditional TextPositionFMPrivatePositionFMPrivateRangeEndFMPrivateRangeEndFMPrivate HTML Macro HTML Macro M.Times.P Times-Roman FrameRoman M.Times.B Times-Bold FrameRoman M.Courier.PCourier FrameRoman M.Helvetica.BHelvetica-Bold FrameRomanM.Helvetica.BIHelvetica-BoldOblique FrameRoman M.Times.I Times-Italic FrameRoman M.Symbol.PSymbol FrameRoman FrameRoman FrameRoman M.Times.BITimes-BoldItalic FrameRoman M.Wingdings.P Wingdings FrameRomanHCourier Helvetica7Symbol;TimesA Wingdings#Regular#Roman MediumBoldRegular ObliqueItalic?P,däFag)"U~MRQ1!zR)^$m_gQ[5™!Ǻ3mc)H] ZEν AQbjq"&g%tIlܯ֭pp(gyg 5׫Rx"UJDH<8ʔ,t HOB]QVJM[IJlSҀ딪+t_ު5a,ڻqU+ǖ6ۏE6k&0x]%Ϟ]6N7,V'ld