WordProLWP7. YƤ1NWord Pro Text File/DFBA@PPPPP-PPP@Jeffab?GLH @@@d*p  lC|@@@"q!@@ @@P@c xpp  @@@PppP @@@ fqcP`R@d H@dZZ Z Z Z pH@PZ  pH@P pH@P pH@P pH@PZZZZ(( /!("(# ($(%(&('Z(3Z)Z*Z+!Z,Z-fZ.cZ/dZ0eZ17Z2$Z3Z4?Z5Z6nZ7*Z8 #Z9 %Z:Z;Z Z Z >H@@ ??X@P`@@P`@@Pp@P`@@Hx``@@Hx``PC q@@P@A!@B?Bp=  xA % x@@@Q $$ %yy A&PHPH q %@@@@Q  yx@Hx@Hx@Hx@Hx`'ABBBBRBBB A]Ay- }Ex$ ?}pExP:An@P@P@@@ P@@@P @@@ X@@@Pp>!A*@EH@ Default Textlq@@@@P |C@@@P !"AO@@ @@P@3 &tB?!xBz$Bp= 7@-@<@Pc@P c@P c@P |p@@@P *>pEH @ Heading 1 #Ox@@@P@A@Aj& $ p`@x@%]A$Az&A3Bz$Bz*&  p`@x@ ABff4]A%AHHPHA s-ExP:A@P@P@@@ P@@@P @@@ P@@@PpO!A #@@ @@P@ A%@p@ q@AJBABffbff,7q@P@P@@@ P@@@P @@@PpP@@@  Aff, ABffbff€BBBH$@P@P P P  DADxQE @QDs%D@@EBodytBPP@EBody@p F  yPu .A +AV@@ Default PageQA@JIXA @CPageH@@Default Page Style$@@ Default TextIxAA~AyAc@ iAfAdAe@ @Printer Folder SettingH$@@@ CA =AT@iH@IAAuP@CPageIAu+ A p@ &d@Q ,@FStory D mt q@@P#AyU@@Default FooterXA@BQJA +AP@EFooter %A@@@Default Footer Style$@aAAAyA@ @YAfAdAe@ XQ$@c CU =@pH@B PRy =P@EFooterI HA#A %Iyy@ @Y XQ@cT AxpA@P H*8A Byd@Q C @@FStory8A BY IA IAmq#yU@@Default HeaderXA@BQJPA#AP@EHeader A@@@Default Header Style$@aAAAyA@ @YAfAdAe@ XQ@c =Wq Cy@pH@B PRPA CA .P@EHeaderI BAA Iyy@ @Y XQ@c B* HA /yd@Q = @@FStory HA /Y KA KAm 1mT(A@BB1SSEnd KwPAmT(A B@B Jeff Absher @ @ @ FDistE @ @ @ FAlgsE @ @ @ DHWC C4.SSEnd/d A8x @mzqk@ Default TextP@@@i@@Default Text Style@@@pE A@x`aAnD}AA"x@@@PP@@@  r H@@a  IPAmT(A H@ASSEnd  A AB  PP  ZHZOZIZGtZLZP:ZNYmZ~V uAuxpA@PU AxpA@PW AxpA@PX AxpA@P\[u^_`abZJZKZQb(Ru(S CM;(e(f8c(g(h(i(j]##AyU@@ Default FrameQ A@IQXAAP@DFrameH@@Default Frame Style$@@ Default TextIAAAAc@ @YAfAdAe@ A]@ .Y +u@pA@B PRA =A +P@EFooterI /A#A %Iyy@ @Y XQ@c +Xq .yu@pA@B PRPA .A#P@EHeaderI ,AA Iyy@ @Y XQ@c 'Ayd@d@FStoryAYAAm 8"q Hyd@d@DStoryq HY9A9AmU@@Default Drop CapQ A@IQXAAP @FDropCapIAxH@@Default Drop Cap Style$@@ Default TextI&AAAyA@!AfAdAe@ X@Dzb%@@ /* BA ,yd@Q . $@FStory BA ,Y 0A 0Amk0mAo@ Note Initials`P@Y@x`al2 tzu:1@Engineering NumberingI8@ OXj3@Viewed Anchor (A)P@@@@Y@x`Affj~.B @ ClickHereP@@@@Y@x`A)\mrW@@ Default TableQH@@RB0PAAP @ SuperTableH@@Default Table Style Ay@. A@_X@@Default Right ColumnQ@H@@@QH0@AAP@CCellX$@@ Default Texty@!qyX@@ Default CellQAA@@@R@0@AAP@CCellH@@Default Table Cell Style$@ @ Table TextI3AAAA@7Ay[AyX@@Default ColumnQ@H@@@QH0@AAP@CCellX$@@ Default Texty@!`AyX@@Default Left ColumnQ@H@@@QH0@AAP@CCellX$@@ Default Texty@!1b@Default Headingsa;'y:qAu ,, /Bqd@Q + $@FStory /BQ -A -Am 'Ayd@d@FStoryAYAAmaSm@D@@ap@PT@@apE.@@ap@PT@@apE.@@ap@PT@@apE.@@ap@PT@@apE.@@ap@PT@@apE.@@ap@PT@@apE)@@ap@PT@@apE)@@ap@PT@@apE)@@apE(@@ap@P T@@apB)SSEnd9RSm8@D@@ap@PT@@apF.0@@apE.@@ap@PT@@apE.@@ap@PT@@apE.@@ap@PT@@apE.@@ap@PT@@a?pE.@@a?p@PT@@apE.@@ap@PT@@apE.@@ap@PT@@apE.@@ap@P QSSEnd *yd@Q $@StoryYAAm 0PAm /@ASSEndo,kA @ Note Date`P@Y@x`al2 tt Zu.A:@Legal NumberingI@ OXj/~ @ Anchor (A)P@@@@Y@x`A+B~ @Outline (Not Indented)P@@@i@"@ Left Justified Outline Numbering@@@pE A@A+@D  O @@@QP Za'  ;#  ) ,Bqd@d@FStory ,BWm -PAm ,@ASSEndTSm@D@@@Px@PT@@@PxE.@@@Px@PT@@@PxE.@@@Px@PT@@@PxE.@@@Px@PT@@@PxE.@@@Px@PT@@@P?xE.@@@P?x@PT@@@PxE.@@@Px@PT@@@PxE.@@@Px@PT@@@QpE.@@@Qp@P QSSEnd 'yd@d@Story_mPAm@ASSEndGoA @ Body Singlep@i@P@@@pE A@Am@D= Z ,q@Default OutlineI@ OP+@Outline (Indented)P@@@i@(@&Traditional Indented Outline Numbering@@@pE A@CfD?" @@@QP  {U  c'  SmCHHBvSSEnd SmCHHBSSEndZB @GBullet 1p@i@P@@@pE A@Am@D  " @@@RH Xw+@DTitleP@ @@ i@P@@@pEAm@DdB}q*A # @@@  f\Uw @ Number Listp@i@P@@@pE A@Am@D  ! @@@QP  ACDU[Df @ Heading 3P@ @@i@P@@@pEAm@D B}t> # @@@  c  b ZB( @GBullet 2p@i@P@@@pE A@Am@D  " @@@RH c PwOf @ Table Textp@i@P@@@pE A@Am@Db|r}#  qC2D[2U @ Heading 2P@ @@ i@P@@@pEAm@D B}t> # @@@   c (S2 @First Line Indentp@i@P@@@pE A@Am@D-# c P2[(D @ Heading 1P@@@i@P@@@pEAm@D B}t> # @@@       1 2AHamT(A@ASSEnd 2Z 5A 1HPAmTFA@B+1. Design an algorithm based on logical @ @ @ timestamps (the @ @ @ LamportE @ @ @ timestamp' version where each event has a unique @ @ @ timestamp) for simulating @ @ @ single-writer/multi-reader+ shared memory algorithms in an asynchronous network. Each reader of a shared variable x should keep a local copy of x. Each read and write operation on x should be assigned a logical time, and the operations should be performed on each local copy in the order of their logical times. All operationsSSEnd 5j 6A 2HamT(A@BGmust be guaranteed to terminate. We assume that channels preserve FIFO.SSEnd 6 7A 5HamT(A@ASSEnd 7 gA 6HPAmTQA@BDoes your algorithm work for @ @ @ multi-writer/multi-reader8 shared memory algorithms? If not, modify it so it does.SSEnd 8 9A yHamT(A@ASSEnd 9 :A 8H amT(A@ASSEnd :z =A 9H ZmTأ8A@R2. Consider a "banking system" in which each processor in a network keeps a number indicating an amount of money. We assume, for simplicity, that there are no external deposits or withdrawals, but money transfers between processors are done through messages between processors at arbitrary times. We assume that channels preserve FIFO.SSEnd = >A :H amT(A@ASSEnd > AA =HZmTأ8A@WDesign a distributed algorithm that allows each processor to compute its own balance, so that the total of all the balances is the correct amount of money in the system. Assume that a subset of processors is told to initiate this algorithm at arbitrary times. Your algorithm should not interfere with the application doing the money transfers.SSEnd A  >HZmT(A@ASSEnd C) DB @amT(A@BGPart 2SSEnd D EA CHamT(A@ASSEnd Eh FA DHamT(A@BERead sections 6.3, chapter 7, section 8.1, 8.2, and chapter 13 of DC.SSEnd F GA EHamT(A@ASSEnd G HA FHamT(A@ASSEnd H= c GHamT(A@B3. Problem 8.1 page 190.SSEnd I JB c@amT(A@ASSEnd J KA IHamT(A@ASSEnd K= v JHamT(A@B4. Problem 8.4 page 190.SSEnd M NB @amT(A@ASSEnd N  MHamTQA@B5. Problem 8.10 page 191. Better hint: Show that totally ordered reliable broadcasting could be used to solve asynchronous consensus, which is impossible.SSEnd g jA 7HZmT(A@ASSEnd j` A gHSmT(A@D@ @ @ EW@ @ @ rite_shared@ @ @ (value)SSEnd me pA HSmT(A@AL@ @ @ Write(@ @ @ value,E @ @ @ Emem)SSEnd p| sA mHSmT(A@AL@ @ @ Broadcast(@ @ @ write,E @ @ @ lamport time stamp)SSEnd s A pHZmT(A@ASSEnd v: A HSmT(A@D@ @ @ Read_sharedSSEnd y# 8A HSmT(A@AISSEnd 9 A sHSmT(A@D@ @ @ Recv_writeSSEnd s @BA@  q AA PP    A HSmT(A@AJ Broadcast ( @ @ @ write_@ @ @ GAck@ @ @ C,E @ @ @ lamportE @ @ @ timestampC )SSEnd  A HZmT(A@ASSEnd  vA HZmT(A@ASSEnd  yA HZmT(A@ASSEndZ   f A HSmT(A@AJSet @ @ @ local_shadow = @ @ @ read(mem)SSEnd | A AmT(A@AL@ @ @ Broadcast(read,E @ @ @ lamportE @ @ @ timestamp)SSEnd  A HZmT(A@ASSEnd 8 A HSmT(A@D@ @ @ Recv_readSSEnd  A HSmT(A@AJ Broadcast( @ @ @ read_@ @ @ FAck,E @ @ @ lamportE @ @ @ timestampC )SSEnd  mA jHSmT(A@AJIf have @ @ @ Grecvd a read or a @ @ @ read_@ @ @ Fack, wait for @ @ @ read_Ack from all N processors.SSEnd @ A HZmT(A@AJPut write event into queueSSEnd  A vHSmT(A@AJIf have @ @ @ Grecvd a write or a @ @ @ write_ack, wait for @ @ @ write_ack from all N processorsSSEnd   @SmT(A@BSend( @ @ @ Famt,E @ @ @ Proc@ @ @ C, VC ) (includes @ @ @ EnumE @ @ @ G:=numF + 1)SSEnd O B AHZmT(A@B,Using Vector Clocks with each transaction...SSEnd `  @SmT(A@D@ @ @ GInit:E @ @ @ Gans@ @ @ F=nullSSEnd L  @SmT(A@D@ @ @ Startcut@ @ @ F_recvSSEnd   BR  mT(A@B?Then to determine the amount of money in the system, start the @ @ @ Fdist consistent cut @ @ @ Galg@ @ @ B.SSEnd r HBA@    I V @SmT(A@AJGIf @ @ @ Eans == nullSSEnd w  V@SmT(A@AJSend @ @ @ startcut to all @ @ @ neigbors@ @ @ B.SSEnd  CB @ZmT(A@ASSEnd V  @SmT(A@AJThen @ @ @ EansG = @ @ @ Gnum@ @ @ C, display @ @ @ Eamt at time @ @ @ DnumSSEnd c IA HHSmTTA@BIf it were not causal @ @ @ thenthatB would mean that happens-before was violated. That would mean the @ @ @ event1 and @ @ @ event2 for which @ @ @ event1 => @ @ @ event2& occurred out of order. Yet we are SS @ @ @ GFifo,# so no events can be received from @ @ @ Gproc0 before a later event from @ @ @ proc0,1 so they could not have occurred out of order from a single source. If they came from different sources, then they must have arrived in the same order at all nodes, so therefore they must have occurred A OvirtuallyA O in order as far as the rest of the system is concerned, and cannot be out of order.SSEnd v z KHSmT(A@BExtend @ @ @ GAss@ @ @ DymE @ @ @ Ealg 8.2.3 to provide @ @ @ Ffifo orderingSSEnd z- ~ v@ZmT(A@B Send( m )SSEnd ~7  z@ZmT(A@AJBroadcast to allSSEnd   @ZmT(A@ASSEnd B  @SmT(A@D@ @ @ King_recv(E m )SSEnd h  @SmT(A@AJ Wait for (m, @ @ @ timestamp) from all N processorsSSEnd   @SmT(A@AL@ @ @ Broadcast(m,E @ @ @ max(@ @ @ timestamp@ @ @ E)@ @ @ B)SSEnd   @ZmT(A@ASSEnd   ~@ZmT(A@ASSEnd L  @SmT(A@D@ @ @ Recv_bdcast@ @ @ C_mSSEnd e  @SmT(A@AJ Send( m, @ @ @ timestamp@ @ @ C) to kingSSEnd x  @SmT(A@D@ @ @ Recv_king(m@ @ @ C,E @ @ @ timestamp@ @ @ B)SSEnd   @SmT(A@AJPlace into queue at @ @ @ (timestamp),E @ @ @ Frecv everything in queue w/ smaller @ @ @ timestamp first.SSEnd  MB @ZmT(A@ASSEnd   NIRmT(A@ASSEnd :u J  mT(A@BNo clue.. Sorry :(SSEnd  @H$@P@P P P DAiEa H@H@@P@@P@@PPpPP`@p@P P w@<DQGAOALQPQHATANAYAZAVAUAWAXA\A[A^A_A`AaAbAIAJAKAQARASAM@ dAeAfAcAgAhAiAjPAH dP@QH pcPay c pcH pcPa pc cpccpcPaUUH cpcP@QHdP@QTT cpcP@QTT cpcP@QH dP@QUUH cpcP@QHdP@P@@Times New RomanHWH@ MS Sans Serif H @ WingdingsH @ Arial Black H@Arial hWy@H@@pGi]AAQrys@@George P. Burdell832882267FA iaA@H@@P@@P@@PPpPP'@%c:\lotus\smasters\wordpro\default.mwpH@p@P P pAO\\goo\hpdj832cAFTC@D od@@B,@B,ULetter pPPQDINU"R0$CR  `???????*$T$$T$P@@d@PAH@@ELPT1:@\\goo\hpdj832c @winspoolP@E1-9999XPDUVerI@P@Original Version@Jeffab?GA?AAAB@@Jeffab1020020543A DYƤ1:.P@@CHHBFI III=III I+I0IXI"I4III'IFIIsIIIaIjIIIIIIIIIZI9IHIQIcIlIuI~IIIIIIIIIIII II$I0I<IHITI`IlIII HLQI IDI I IuIZIlIkItIIIIcII}IIIHIIIIIII)III4I?IJIUI`IIiIIIIIIIIIIII I6 I IIRI`IIII'IIIII I IDI{ I;IIs^DYƤ1kh PIHBJN   JGQv1XA<U]1!@Ec1AFe1H@a @F2"@U&/2! ?0/2*G${R02UE72#E{23FKM5@F?G!II IoII II IXIIIDIIIyI2II IaIIIIIIIII I1IPP I_ IKIs I II>$I"I-!I P I6 IxIIIIInII3I I7I%I&Iu(I(I )I)I)I*I+I+I7-I^-I-I-I%.IK.Iq.I.I.I/IH/Io/I80I_0I0I41I1I1I!2IL2I2I2I2Iy3I3I3I3I3Ih4I4I5IS5I5I6I6I7Ii8I8I(9I|9I7:IS:Ib:I:I2;IZ;I  ?. @)% 1  !     !#-3 )4   (   (* .9'       8e! e! e!  e/l! l! l!lO7! )! )!99\! \! \!  \Az! s! s! ;Z! Z!  Z!  Z 9c!c! c!  c3" !  ! M:! *! ,!  <   R     ! $  !  &#HN   8   9 :'";/ /    37(  0        "a%   .5!         $ 4      3|}} MiscellaneousMiscellaneousFileProtectionHeaderLWPStreamTypePreviewWordProData  kl NNRNk0kkk k~kCMHdrk