Aar큀  0 P   `0@0P` 0HH $ @d HHHH̀̀̀ff@  d Footnote TableFootnote**.\t.\t/ - :;,.!? 7d7dTOCHeading1Heading2   BEquationVariablesJ;`<<=7=P=i=@ABbB7HG@;@=@?@AEuIo <$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>EHTML Headings++A88::33557AHHA{;b;d;f;h;j;l;n;p;r;t;v;x;z;|;~;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<<<<<< < <<<<<<<<<<< <"<$<&<(<*<,<.<0<2<4<6<8<:<<<>@B=R=T=V;#=X=Z=\;/;2@C@E$1.@F%2.@O@&=^=`=b=d=f=h=k=m=o=q=s=u=w=y={=|@Q'C @@@&@AAA&A%2.A&D3AA'A$1.AcAlAeAmAzA{A|A}A~AAAA&C7D<&D=,B&$1.B+-a.B,)b.B%2.B0&CBXC&B]B^B_BaBrBtBCC&C.C&C,C,D&D,D!,D",D>,D7&D8$1.D?,DB,DO&DP,DR,DS,DT,DU,DX,D.D.D$1.D%2.E.ED,E-a.E)b.FE%2.E-a.E)c.E)b.E%3.Eg%4.Es&En%3.E&E$1.F?PF%F&FFiG GGFFFGG&G.G$1.G%2.G.G$1.G-a.G)b.G%2.G-a.G&H2H>III I I I IIHHHHHHHII'$1.I)&I*I+&I,,I-,I.,I/,I0&I1.I2$1.I3.I[%2.Ih%2.Ij.I}%3.Il$1.IE,IP%2.I&I.I$1.I%2.JhIIIIIIIJm$1.Jn-a.Jq)b.Jr%2.Js-a.Jt)b.Ju)c.Jv%3.Jw-a.Jx)b.Jy)c.Jz)d.J{)e.J|)f.J})g.J~%4.J-a.J)b.J)c.J)d.J2i.J1ii.J1iii.J1iv.J1v.J1vi.J1vii.J%5.J-a.J)b.J)c.J)d.J)e.J2i.J1ii.J1iii.J%6.J-a.J)b.J)c.J)d.J%7.J-a.dq5+H8̨@_^`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;_d1QRUX[^adgjmpsvy| %).1W/Bm }d ;ad WeHTML Mapping Table }Hd ;cHd We }Hd ;eHd We }Hd ;gHd We }Hd ;iHd We }H;kH% FrameMaker PE Source Item }H ;mH We HTML 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#H W e New Topic? }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 Q'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(( 1eP 2e Parent = OL Q3e 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((GeLI He Parent = UL QIe 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;^`HR% P:HeadingRuPEnIn }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<hjCH\% P:TableFootPEnote }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((beLI ce Parent = OL Qde Depth = 0 }]H( H "W4e }©H <=?©H #W5e }H©H <>@H©H #W6e }©H <?A©H #W7e }©H <@B©H #W8e } ©H <AC ©H #W9e }»d <BF»d $W:eHTML Options Table }D»d <D»d $W;e }D»d <D»d $W<e }D <CGD %W=e }DH <FHDH %W>e }H <GIH %W?e }D <HJD &W@e Image Format }DH <IKDH &WAeIMAGGIF }H <JLH &WBe }D <KMD 'WCeBanners }DH <LNDH 'WDeN }H <MOH 'WEe }D<NPD(F% Banner ReferPE ence Frame }DH<OQDH (WGe }H<PH (WHe }D(<DSD((F)I% Copy Files  Imported by PE Rerefernce }DH(<DRTDH( F)WJe }H(<DSUH( F)WKe }DD <DTVDD F*WLe }DDH <DUWDDH F*WMe }DH <DVXDH F*WNe }Vd <DW[Vd F+WOeSystem Macros }?Vd <D?Vd F+WPe }?Vd <D?Vd 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 =D_arH F-WWe }~? =D`b~? F.WXe EndOfDoc }?~H = Dac?~H F.WYe }~H = Dbd~H F.WZe }?= Dce?F/[% StartOfSubPEDoc }?H=Ddf?H F/W\e }H=DegH F/W]e }?=Dfh?F0^% EndOfSubPEDoc }?H=Dgi?H F0W_e }H=DhjH F0W`e }?=Dik?F1a% StartOfFirstPESubDoc }?H=Djl?H F1Wbe }H=DkmH F1Wce }?=Dln?F2d% EndOfFirstPESubDoc }?H=!Dmo?H F2Wee }H=#DnpH F2Wfe }?=%Doq?F3g% StartOfLastPESubDoc }?H='Dpr?H F3Whe }H=)DqsH F3Wie } ?=+Drt ?F4j% EndOfLastPESubDoc }? H=-Dsu? H F4Wke } H=/Dtv H F4Wle }&? =1Duw&? F5Wme }?&H =3Dvx?&H F5Wne }&H =5Dwy&H F5Woe }8d =8Dx|8d F6WpeCross-Reference Macros }?8d =:D?8d F6Wqe }?8d =<D?8d F6Wre }H? =>Dy}H? F7Wse Macro Name }?HH =@D|~?HH F7Wte Replace With }HH =BD}HH F7Wue Comments }T?=DD~T? F8Wve See Also }?TH=FD?THF8w% See Also: PE <$paratext> }TH=HDTH F8Wxe }n? =JDn? F9Wye }?nH =LD?nH F9Wze }nH =NDnH F9W{e }d =QD d F:WeGeneral Macros }?d =SD?d F:We }?d =UD?d F:We }?d =WD?d F:We }? =YD"? F;We Macro Name d= d= d l d= do  WBm }d = d  <W|eHeadings Table }Hd = Hd  <W}e }Hd = Hd  <W~e }H= H =%Paragraph ForPEmat }HH= HH  =WeHeading Level }H= H  =We Comments }H= H >W eTitle }HH= HH  >We }H= H  >We }KH = KH  ?We Heading1 }HKH = HKH  ?We }KH = KH  ?We }WH = WH  @We Heading2 }HWH = HWH  @W e }WH = WH  @W e }cH = cH  AW e }HcH = HcH  AW e }cH = cH  AW e $z@ $z$$?z@;$?z$??d@48H}?H =[D #?H F;We Replace With }H =]D"$H F;W eHead }H =_D#%H F;W!e Comments }? =aD$&? FCW"e }?H =cD%'?H FCW#e }H =eD&(H FCW$e }H =gD')H FCW%e }d =jD(.d FDW&eCharacter Macros HHˆ;"HHˆ+Ge HHˆ;$3HHˆ**l}?d =lD?d FDW'e }?d =nD?d FDW(e }? =pD)/? FEW)e Macro Name }?H =rD.0?H FEW*e Replace With }H =tD/1H FEW+e Comments }? =vD0B? FFW,e HUV ;.HUV 3Ge HUV ;05+HUV 22l H$ ;1H$ 5Ge H$ ;33H$ 44l HHˆ;4HHˆS[//7  `!Distributed Systems Fundamentals Q`Distributed system? R` What is it? S` Why use it? TNs`System Architectures U`minicomputer mode VgD=`workstation model W`processor pool X`Issues Y`global knowledge Z`naming [` scalability \`compatibility ]`'process synchronization, communication ^` security _` structure `*` Networks a`goals bwa`!message, packet, subnet, session c`Yswitching: circuit, store-and-forward, message, packet, virtual circuit, dynamic routing d`OSI model: PDUs, layering e`*physical: ethernet, aloha,  etc . f`8data link layer: frames, parity checks, link encryption !g 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) !h gtransport: services provided (UDP vs. TCP), functions to higher layers, addressing schemes (flat, DNS, @,etc.), gateway fragmentation and reassembly i`:session: adds session characteristics like authentication j`Cpresentation: compression, end-to-end encryption, virtual terminal k`!application: user-level programs l!`Clocks m`happened-before relation n`|Lamports distributed clocks:  a      b  means  C ( a ) <  C ( b ) o`yExample where  C ( a ) <  C ( b ) does  not  mean  a      b p`"Vector clocks and causal relation q`;ordering of messages so you receive them in the order sent r`why s`0for broadcast (ISIS): Birman-Schiper-Stephenson t`)for point to point: Schiper-Eggli-Sandoz u]` Global state v`;Show problem of slicing state when something is in transit w* z`?Define local state;  send ( m ij )     LS i  iff time of  send ( m ij ) < current time of  LS i ; similar for receive x =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  yUU`)Consistent global state: Chandry-Lamport zCw;`Termination detection A{`Haung HHˆ;6HHˆa66 lH$ @5!:H$ 99l H$ @6!H$ 8Wh9February 17, 2000ECS 251 Winter 2000Page  1  HUV @7!8HHUV GGl$lz@ <$lz$ll6 @ ;=6 ? @ <>?  @ =? xUU @ >@xUU  @ ?A Sh @ @JSh }?H =xD1C?H FFW-e }H =zDBH FFW.e d=~EEd=DdFF l d=DdRCERUX[^adgjmpsvy| %).1 HUV @8!HUV :WlCLast modified at 4:55 pm on Thursday, February 17, 2000 HHˆ@9!:HHˆII l HHˆ@:!HHˆHW`  @ AK gh @ JLgh dUVUU @ KMdUVUU UU+ӌ"Gw@ LNUU+ӌ"GwUU^UU^P 1 UU)"Gw@ MOUU)"GwUU@VUU@VP 2 UUg+ӌ"Gw@ NPUUg+ӌ"GwUUo^UUo^P 3 @z'݈@ OQ@z'݈@@e11 UUz'݈@ PRUUz'݈UUUUe12 z$ҍ݈@ QSz$ҍ݈zUzUe21 $ҍ݈@ RT$ҍ݈UUe22 $ҍ݈@ SU $ҍ݈ U Ue23 GUU]}݈@ TVGUU]}݈GUUa^GUUa^e31 j^z'݈@ UWj^z'݈jbjbe32 $@ VX$UU b}݈@ WYb}݈b^b^e13PUU@ XZPUU^UUUUU @ Y[UUUUU UUUdU$BUB&@ Z\$BUB&$BUgUVhUYUUB"(@ []YUUB"(YUUj{UUB @ \^ )UVp@@ ])UVp@)UV^)UV^e24dAaa HHˆA_HHˆ̑aI `Lamports Clocks ,` Introduction  oLamports clocks keep a virtual time among distributed systems. The goal is to provide an ordering upon events I@within the system. ab` Notation b*t`P i  process c`>C i . clock associated with process  P i  0` Protocol *UL`2Increment clock  C i  between any two successive events in process  P i :  C i      C i  +  d  ( d  > 0) UL*"  @Let event  a  be the sending of a message by process  P i ; it is given the timestamp  t a  =  C i ( a ). 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) ̨"h Example 2*wR 2Assume all clocks start at 0, and  d  is 1 (that is, each event incrememts the clock by 1). At event  e 12 ,  C 1 ( e 12 ) = 2. Event L?e 12  is the sending of a message to  P 2 . When  P 2  receives the message (event  e 23 ), its clock  C 2  = 2. The clock is reset to 2%D@3. Event  e 24  is  P 2 s sending a message to  P 3 . That message is received at  e 32 .  C 3  is 1 (as one event has passed). By @)rule 2,  C 3  is reset to the maximum of  C 2 ( c 24 )+1 and the current value of  C 3 , so  C 3  becomes 5. 4!`Problem 5̚`=Clearly, if a    b, then  C ( a ) <  C ( b ). But if  C ( a ) <  C ( b ), does  a      b ? 6*̙ 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 causally unrelated; that is,  e 31    / e 12 . However,  C 1 ( e 11 ) <  C 3 ( e 32 ), and clearly  e 11      e 32 . Hence one cannot say one way UUv2@or the other. Q3w<` HHˆA_HHˆ7`` lHcwKxAAcd dA 4zAEbe4z44zAFbdf4z44fzAGbeg4fz4ffF AH bfhF O AI bgiO < AJ bhj< UU< AK bikUU< < AL bjl< cc< AM bkmcc< -< AN bln-< wb AO bmowb tUVN AP bnptUVN UǓ"GwAQ boqUǓ"GwUUUUP 1 UU""GwAR bprUU""GwUUEOUUEOP 2 UUǎ"GwAS bqsUUǎ"GwUUiUUiP 3 P ݈AT brtP ݈PPe11 UU ݈AU bsuUU ݈UUUUe12 ˍ݈AV btvˍ݈ENENe21 ˍ݈AW buwˍ݈ENENe22 ˍ݈AX bvxˍ݈ENENe23 WUUXav݈AY bwyWUUXav݈WUU[WUU[e31 zY ݈AZ bxzzY ݈z\z\e32 rav݈A[ by{rav݈rre13PUUA\ bz|PUUUUENUU A] b{}UUENUU UUENtEN4ENB&A^ b|~4ENB&4ENwUVcENiUU"(A_ b}iUU"(iUUdUU< A` b~< 9UVp@Aa b9UVp@9UV9UVe24 HHˆAcHHˆ9wbb7 `Vector Clocks 8,` Introduction < 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. db` Notation et`n  processes  f*`P i  process g 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 UK@in process  P k . =` Protocol >**`LIncrement clock  C i  between any two successive events in process  P i :  C i [ i ]     C i [ i ] +  d  ( d  > 0) 9UL*] 0) :wK"h Example  ?!`9Here is the progression of time for the three processes: A*!`-e 11 :  C 1  = (1, 0, 0) BF`-e 31 :  C 3  = (0, 0, 1) @UL*w:`&e 21 :  C 2  = (0, 0, 1) as  t a  =  C 3 ( e 31 ) = (0, 0, 1) and previously,  C 3  was (0, 0, 1) C*L`-e 22 :  C 2  = (0, 1, 1) D`J`-e 12 :  C 1  = (2, 0, 0) EUL*`!e 23 :  C 2  = (2, 1, 1) as  t a  = C 1 ( e 12 ) = (2, 0, 0) and previously,  C 2  was (0, 1, 1) F*w$`-e 24 :  C 2  = (2, 2, 1) GUL*`&e 13 :  C 1  = (2, 1, 1) as  t a  =  C 2 ( e 22 ) = (0, 1, 1) and previously,  C 1  was (2, 0, 0) H(]`&e 32 :  C 3  = (2, 2, 1) as  t a  =  C 2 ( e 24 ) = (2, 2, 1) and previously,  C 3  was (0, 0, 1) _I*4L^`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ˆAcHHˆa  l | ]B| ]||dC HHˆCHHˆwî J `#Birman-Schiper-Stephenson Protocol K,` 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. M` Notation N*`n  processes  h**`P i  process k 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 A@in process  P k . lULUUU5`kt m  vector timestamp for message  m  (stamped  after  local clock is incremented) i` Protocol t * U4`-P i  sends a message to  P j jUL*(`P i  increments  C i [ i ] and sets the timestamp  t m  =  C i [ i ] for message  m . u *(z`2P j  receives a message from  P i OUL*9*n`!When  P j ,  j   i , receives  m  with timestamp  t m , it delays the messages delivery until  both : P\`DC j [ i ] =  t m [ i ] 1; and Q`for all  k   n  and  k   i ,  C j [ k ]  t m [ k ]. R*hLt`\When the message is delivered to  P j , update  P j s vector clock UU+`8Check buffered messages to see if any can be delivered. S"h Example  U`5Here is the protocol applied to the above situation: WUL*%n`ye 31 :  P 3  sends message  a ;  C 3  = (0, 0, 1);  t a  = (0, 0, 1) X5z 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 *C@>the message is accepted, and C 2  is set to (0, 0, 1) ZUL*TC 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 *b@Cthe message is accepted, and  C 1  is set to (0, 0, 1) _YUL*r`ye 22 :  P 2  sends message  b ;  C 2  = (0, 1, 1);  t b  = (0, 1, 1) HuUTB6UT mUU5ZLBY "mUU5ZLmUU`556zB: 6z6UTzB; UTzUTUT6czB< 6cz6ccH B=  H HHˆCHHˆ lx| B?  x| UUx{ B@  UUx{ x| BA x| e`x| BB e`x| dC y_ BD y_ vUV#& BE vUV#& UU"GwBF UU"GwUU+ѡUU+P 1 UUN"GwBG UUN"GwUU'UU'P 2 UU^"GwBH UU^"GwUUg+ѡUUg+P 3 #\3݈BI  #\3݈ # #e11 HHˆCHHˆ*O  \UL*UL 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 **@Cthe message is accepted, and  C 1  is set to (0, 1, 1) ]UL* 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*E`9Now, suppose  t a  arrived as event  e 12 , and  t b  as event  e 11 . Then the progression of time in  P 1  goes like this: 1Th 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 dU@_message is held until another message arrives. The vector clock updating algorithm is not run. LUL*r 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 mesCsage 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], PU,@uand  C 1 [3]  t b [3], that message is accepted and  C 1  is set to (0, 1, 1). ݈BK ݈&&e21 ݈BL ݈&&e22HHˆCHHˆ = l YUUUN݈BN YUUUN݈YUUY+YUUY+e31 |VG݈BO |VG݈|Y{|Y{e32 tN݈BP  tN݈t+t+e12HTuUTEv:UT#CEUU&UU BR !UU&UU UU&v&UU5BS  "UU5UU5yUV`&kUU{"(BT !kUU{"(kUUa{UU{6zEw$6z6UTzEx#%UTzUTUT6czEy$&6cz6ccH Ez %'H x| E{ &(x| UUx{ E| ')UUx{ x| E} (*x| e`x| E~ )+e`x| UV_.UT E *,UV_.UT HUVx| E +-HUVx| UU"GwE ,.UU"GwUU+ѡUU+P 1 UUN"GwE -/UUN"GwUU'UU'P 2 UU^"GwE .0UU^"GwUUg+ѡUUg+P 3 #\3݈E /1 #\3݈ # #e11 ݈E 02݈&&e21 ݈E 13݈&&e22 YUUUN݈E 24YUUUN݈YUUY+YUUY+e31 VUU݈E 35VUU݈YYe32 F݈E 46F݈F'F'e12ƪ'E 57ƪ'ƪ+KUVTNE 68TN`kUU{"(E 7?kUU{"(kUUa{UU{SUVUVAF DBSUVUVASUVUUUTUVdGFe dE== HHˆE;HHˆ =T `Schiper-Eggli-Sandoz Protocol V,` 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 o`n  processes p*`P i  process q 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 UI@in process  P k . rULUU=`kt m  vector timestamp for message  m  (stamped  after  local clock is incremented) n*`7t i  current time at process  P i  s TV i  vector of  P i s previously sent messages;  V i [ j ] =  t m , where  P j  is the destination process and  t m  the vector times*$@tamp of the message;  V i [ j ][ k ] is the  k th component of  V i [ j ]. zULUUU`0V m  vector accompanying message  m m-m` Protocol ` *?U`-P i  sends a message to  P j vUL*O `}P i  sends message  m , timestamped  t m , and  V i , to process  P j  . w``FP i  sets  V i [ j ] =  t m . x *n`2P j  receives a message from  P i |;`}When  P j ,  j   i , receives  m , it delays the messages delivery if  both : {ULUU/d&V m [ j ] is set; and |`)V m [ j ] <  t j ~*= When the message is delivered to  P j , update all set elements of  V j  with the corresponding elements of  V m , except @+for  Vj [ j ], as follows: ZdZIf  Vj [ k ] and  Vm [ k ] are uninitialized, do nothing. Y`If  Vj [ k ] is uninitialized and  Vm [ k ] is initialized, set  Vj [ k ] =  Vm [ k ]. C` If both  Vj [ k ] and  Vm [ k ] are initialized, set  Vj [ k ][ k  ] = max( Vj [ k ][ k  ],  Vm [ k ][ k  ]) for all  k   = 1, ,  n **#`)Update  P j s vector clock. YUULA`8Check buffered messages to see if any can be delivered. HHˆE;HHˆF<< lOx| F ?@Ox| ^U\F 8>^U\_k_k' Z݈F >AZ݈Z'Z'e23 UUUF@DUUUUUU5UUU5 G݈F 9CG݈}}e13UV F BUV >FA9>>4>4 HHˆG:HHˆ* F"h Example y`5Here is the protocol applied to the above situation: }UL*`Ve 31 :  P 3  sends message  a  to  P 2  .  C 3  = (0, 0, 1);  t a  = (0, 0, 1),  V a  = (?, ?, ?);  V 3  = (?, (0, 0, 1), ?) * Xe 21 :  P 2  receives message  a  from  P 1 . As  V a [2] is uninitialized, the message is accepted.  V 2  is set to (?, ?, ?) and  C 2  is @set to (0, 0, 1).  UL*ʪ`Te 22 :  P 2  sends message  b  to  P 1 .  C 2  = (0, 1, 1);  t b  = (0, 1, 1),  V b  = (?, ?, ?);  V 2  = ((0, 1, 1), ?, ?)  *z`Ve 11 :  P 1  sends message  c  to  P 3 .  C 1  = (1, 0, 0);  t c  = (1, 0, 0),  V c  = (?, ?, ?);  V 1  = (?, ?, (1, 0, 0)),  i Xe 12 :  P 1  receives message  b  from  P 2 . As  V b [1] is uninitialized, the message is accepted.  V 1  is set to (?, ?, ?) and  C 1  is @set to (1, 1, 1).  UL**a Xe 32 :  P 3  receives message  c  from  P 1 . As  V c [3] is uninitialized, the message is accepted.  V 3  is set to (?, ?, ?) and  C 3  is @set to (1, 0, 1). UL*$T`fe 23 :  P 2  sends message  d  to  P 1 .  C 2  = (0, 2, 1);  t d  = (0, 2, 1),  V d  = ((0, 1, 1), ?, ?);  V 2  = ((0, 2, 1), ?, (0, 0, 1)), 5*H se 13 :  P 1  receives message  d  from  P 2 .  As   V d [1] <  C 1 [1], so the message is accepted.  V 1  is set to ((0, 1, 1), ?, ?) and  C 1  is B@set to (1, 2, 1). UL*Q;`1Now, suppose  t b  arrived as event  e 13 , and  t d  as event  e 12 . Then the progression in  P 1  goes like this: b*/`Se 12 :  P 1  receives message  d  from  P 2 . But  V d [1] = (0, 1, 1) < / (1, 0, 0) =  C 1 , so the message is queued for later delivery. p*2 Xe 13 :  P 1  receives message  b  from  P 2 . As  V b [1] is uninitialized, the message is accepted.  V 1  is set to (?, ?, ?) and  C 1  is set to (1, 1, 1). The message on the queue is now checked. As  V d [1] = (0, 1, 1) < (1, 1, 1) =  C 1 , the message is now \*i@caccepted.  V 1  is set to ((0, 1, 1), ?, ?) and  C 1  is set to (1, 2, 1). HHˆG:IHHˆ=kEE lHUݼsUVHiUVHhj UU"EXhH3 GgUU"EXhUU"EUUn"EUUfGzH:FJUUfGzUUfGUUfGUUGzH:IKUUGzUUGUUGUUGzH:JLUUGzUUGUUGUUfG H :KMUUfG UUaG H :LNUUaG UVb3 H :MOUVb3 Ӫ3 H :NPӪ3 UV3 H :OQUV3 UU3 H :PRUU3 xUU3 H :QSxUU3 UUG H :RTUUG bޜ H :SUbޜ j^"GwH! :TVj^"GwjfGjfGP 1 j p"GwH" :UWj p"GwjIUUI oqs>IUUpo*UUI ortpo*UUoUVc~UUI osuoUVc~UUĂUVI otvĂUVĂ@Ko-ENĂUVI ouwENĂUVENĂqUUeo-o-UVI ovxo-UVo-Bo-GUUo-UUI owyGUUo-UUGUUJĂro- E^ I oxzE^ @؄@P0 J I oy{J Jo-Jo-P1 UU I oz|UU UUo-UUo-P2 t I o{}t tĂtĂP3 tS I o|tS tZĂtZĂP4dJi HHˆJj~HHˆXf&&oo * d'Huangs Termination Detection Protocol 3,d Introduction 4dRThe goal of this protocol is to detect when a distributed computation terminates. 5Vd Notation 6hdn  processes  7*wdfP i  process; without loss of generality, let  P 0  be the  controlling agent 8d W i . weight of process  P i ; initially,  W 0  = 1 and for all other  i ,  W i  = 0. 9UUULdDB ( W ) computation message with assigned weight  W CUKdgC ( W ) control message sent from process to controlling agent with assigned weight  W :d Protocol ; *UJd9P i  sends a computation message to  P j <*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 .) DLd4Send  B ( W j ) to  P j = dWP j  receives a computation message  B ( W ) from  P i 2 D*d*W j  =  W j  +  W >fHd?If  P j  is idle,  P j  becomes active @ ]*d P i  becomes idle:  B5]d4Send  C ( W i ) to  P 0 ?CdW i  = 0 A3dP i  becomes idle F dBP i  receives a control message  C ( W ): Gmdd*W i  =  W i  +  W H{d9If  W i  = 1, the computation has completed. E*dExample J*$`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@ C BodySpaced. f@ C Bulleted\t. f@ C...Date. mf@ Cl. DateProject. @@ CHeader Double Line. f@  $.6.Z.~..CodeC. f@T CHeading1Body. $f@ C Answer. f@ C NumberedSpaced. f@ CBody. @@ CHeader Double Line. f@ C CellFooting. f@ C CellHeading. f@ C CellBody. @@ CMapping Table Cell. f@ C.Reading. @@Mapping Table Cell.  f@PCTitleBody. @@ Mapping Table Cell. @@ CMapping Table Cell. f@$C.Line Single Line.  f@PCTitleBody. f@ CCellBody. f@ C CellHeading. f@ C Footnote. f@T CHeading2Body. f@T C HeadingRunInBody. f@ C Indented. f@ C TableFootnote. f@NE C Numbered1 N:.Numbered. L̀Lf@N C Numbered N:.< =1>. f@T CHeading1Body. f@T CHeading2Body. $f@L C$. LetteredL:.. f@T C TableTitleT:Table : . f@NE C Numbered1 N:.Numbered. f@ C Bulleted\t. $f@LE C$. Lettereda L:.Lettered. f@ CBody. $f@LE C$. Lettereda L:.Lettered. 6$f@R C6. RomanR:.. 6$f@RE C6. Romani R:.Roman. 6$f@RE C6. Romani R:.Roman. $f@L C$. LetteredL:.. L̀Lf@N C Numbered N:.< =1>. 6$f@R C6. RomanR:.. f@ C BodyIndent. f@  $.6.Z.u..CodeASM. Hf@ CH.. CodeComment.  C CCEmphasis C  C ڝCCCEquationVariables   BoldItalic CItalic C ڝC  Subscript C C Subscript C C CBold@ Symbol  Computer @  Symbol "  Superscript C Superscript C C Subscript C C C C  C  Cq7C Subscript 34@  Symbol ZZdZdZZdZdZdZdThinMediumDoubleThick@ Very Thin HHHHHFormat A HHHHHFormat BH Mapping TableH Mapping Tableh*|#HHHHHf$*DHH+5?HH&69?HH :C?HHH DF?HH*6 ? @ 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#B#» %C$D$E$ $&F%G%H% %'I&J&K& &(L'M'N'')O(P(Q(((*FR)S)T)D )FU*V*W*V ,FX+Y+Z+f +-F[,\,],r ,.F^-_-`-~ -/Fa.b.c..0Fd/e/f//1Fg0h0i002Fj1k1l113Fm2n2o224Fp3q3r3 35Fs4t4u4& 4Fv5w5x58 7Fy6z6{6H 68F|7}7~7T79F888n 8F999 ;F:::: :CF ;";#;$; =  <<<<> ====? >>>K >@ ???W ?A @@@c @ AAA ;F%C&C'C(C EF)D,D-D DFF.E/E0E EF1FBFCFComment @<@@d BlackT!WhiteddARedddGreendd BluedCyandMagentad YellowHeader/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 FrameRoman FrameRoman M.Symbol.PSymbol FrameRoman M.Times.BITimes-BoldItalic FrameRomanUCourier Helvetica?SymbolBTimes#Regular#Roman MediumBoldRegular ObliqueItalicle=>w\Ĩ{:,G]czp*x(:&Rn x_+a) Дųֺ Tt7n!FL5QW"+˾ IM)Y ~#{ƟQk qz!f)u`ǾV{ h%Ӛ҇͒,m=λQHq_|mb}e͚1JI-َ.ʔOYԴ4[2,]}وYKtž3bVK`P?af!ݪ_2Z