ࡱ> `!-}WB6)E>y$$ M dHG7Ix}dzg[<X]XB܂.%8! !y{ɞAx=#!LeB%Bm8R|W?~m'ȷ}/ԞX{?Ӌ[/+!oFO$AQ]JFSn*kiK;WWq]7\tU/tq׻e]I#.OoZ)r֬sf+lƹjc Ѯjҕ5e] 1iD/wA) (lEAI;hfi&-b^,s\0+L";Զ-[̜8\yn+tq_ahp`7 ޠ- R0: e\~=n)mZ"ib械K]=BWں(h:Bo( ӄ|)p] KjSGGi_ :OV ?oNV0` brO󀛛\ٜf?G-l~K|'nLVn^fm~n&~ePxGs!1胹Add-r&ŵ)H)y*dR]ۖl4ƾev;𚭈m|e* 를!a0!U0 "q)ك; BcTzqgpH\VSomk͠ G⯳gzlϳvN_h/mkKٶaid[ن0~ CHaB3CP^ D؜hl;|lYs784ה2먕B_TɜR aH1uYx3 NdQbOlR93hgR`2%np h;[HأB1AN5ӚjG<…x6VZh.fj(ʳ޴[\L-q U/SrK>]ܤp!4bh̤0X%tZxj@y)X@E`UTvSfFI` )iѯj2Qh 4Uj V}NT[Q*MTv)N-U@u+aau smSj0 6 XDub+,Zc ;8o K}1? 3x[pwc+8{yOwK{簈 zkX̛e7 m՛}Y8LO^|~B?3R†*56QZvTo Z=|$ufXmUd i̠0WX,}#m.!-愘#0/gŢ\q p' s*|$:`aoej&6*ZWURUH=S~ruOIUi~5OZ ~M}ΏH4~Fϥ2UUJ_]RoU~!5/&i[WQ{+ʢFj֨Mꬺ^8XZ@ox&~Sྺ /Gq\4 /ƅ"cѨa$*{1> @U+|E?\zBg)tV>ZGi9pQnuFkRP\ MuG4]6 mem5eli)ɠTH5V3'f?+~bCu-^7hmhmm"SW//52Q^m ~~6/m ]?s!˖T?v]dߨ,0ӆY辥<rhoS~/>AV^P!n=F _[]K.꾛޹*NM$JV CX2rabXc(ӧldɒ-WK,O/oaK~].%z{áAcRol:6;N1x* U!~ W~LJ $\A 0 tB^8e,ցS aw-lN llx/a6]2h 6Ά8T(S .l@zC9DPHc10'q7U dxV:|'m0LBq\5qau0Fb 42/_6I$~#tNI8-z#PlA5Po|q8Li[qGeb|,MS}Ĭĭ_HL^ǽ{#Q]LI0/tT?Nd%h ;JtFVl,k]KVyp搱3ğeEw`b&Mvz'}2\}'{Kp"<on黎Ej5d*i'r"ւXza9h%Wc vw[N@HC8Ns`9l 0v@`/MEZ!mp^!,RWnę_Zn,cek)]euhQCfƥg$ ݡ0 mv:@$QY=wQ1vc2/ϖ;G}Tі ;iGW0 3ڟ%i8{USwL#, !΄ukZ(SJc],e~'yT/^f[ s;Z7Uhk;&vu;\/jc{C5k{9>vn04e6Tz9u3ʫ{RA@ *Nʡt:NЉu&Yօc-m.WVSq=ATS仙]J x]wŷ.~u11o'Dg=\l8Jaz+ԻwaKW^rL )#giy~K[0bm%iXcc*(S\ɍ<+lvK. |J+ z Au ɿ[iigqrae'K|u=7(@͹ :TQ)By2eI9Lt5ף1M;]贮KGnHu}Zk! (JIt#:5u K(Du^jsRwf,_gG:-%*)ĦiȐcĵhԦaP@-9 hL9-6 $_i#_թJ*K %=PT2QO{ FcߗחFs9Z*ō)\#傁\4y(Ak-1X/ Rrw[DMeZwkNm]K"m.4Hd}Ucߝ#FYC5 G[~}ӷķ)-K[}?y:鿚slrMx A1܉stӯ܈nsSzm(d'{ܤ#&^eJ豦dJfhjc.ǯ9?8qܜѩFLIMNgZ\.f &R76qeܧ) ͗Ř졭5G9Fgid.PȆ^t{Q=(Wԃ =Bo1=Z_gÃ(;Ki$_µOjqQp‘Ԅ3Q9i8%zSnA>/'.H'u.ګv68i~[T7񰾀!^[xzhp0 wĂXt|/hC Sf\:nC ys4dPk@.9 0b~6 TkZw ~_! pj% .7{Гa^ vDIoz\K)j9:O\[,LZ`ur^ y^K#tmo]M<[{Ywfqhbt^܍rGQBsRj.WR?:/_H>Eyw,><}[VKCx2R.9xRf^ÊGG8*u&߿Sb2W u8oIx\kj>eYf6~ ɸ9X[p-[Gr5.bGA>ȹaJp&SAk^}o!:%^+7kCIc؜;\9L DA)Hk|>7 ̛rh>r!&CIt.p&4y]Se6\SGh2%5CDg"vZKA^Nlwk&Q\صl"#\M!z%]zsVrwukwB7v[u%L|]M5x{] \]̵]]Ǖ9]~!Jr)J0v-hzPS > "MAl@ \lX{lhaA9U4 9)MM~f2.\b~ 6pYVldcNs |k_I_~ZK~e{o`Q=vkc1S?n*M:Q~1[tfMWWs[..08Ov obo xw Mw7sy愌I_x qI. ǛaR&"M3`y1,1a9!f 1`YTmF03Ԇڦ2) M%3'6S^#\Tiotf65y =Lv'vs\"6-f 0=i'MyRRoo*&E*)u/ICB|^Il{hHhpNHh2>})>ߍ E-*{ubK\'J4NZŵ?c8XAfdŸG:Z | ;$t.)+>B}\%[ylEـe.*h+t_h'+F7t@OLEo·bXtM81aA%+=֢SG jhzlkS&qȊXd@ rb92b5B9n3݌$݆w5t.>g{M'.e. ]ɳ~]8݄t;qt߰r5{Gc]l;qͶ\ǚ4ChDzuOek*T>rR [qݏ"zopNdף,{nEg[EF&IGKًg>Gr(qq /< F~%lu.6~y (@Fly;9Sٴ"b}w1l7aQ0Əc~>6jqh(k*Li~7:VJczOU,ix;$Fq2O4f|ϫ>+Oc^Gu=Ok' ߅C݃u>לI:tV*o&&a,,lz} -3=5^L=q+4:Q3{u)vq1詥GՓ< Ff%k7+KX7E6{aE쎖+֪v@kXֱmi֦LBmmsMׯlFjotuӟN:>jj knrJj׽VHY>=n9A<̞H2ȥ!bleU$^fz ;iég]-:Vjm1<0;}ׯvʞisjZ.T(m%nUgG"5ZBW$/m86!LDa;f df5]l͙bTa g,@-ٙ)Ӣ}ړ>KHkKfXGK;d?{7x?-𐱔TO1V9wO_]}5A_K_k~C^ԟֺTZZ]k=;]hF}i:k'3O)p[ 'MV*vdZX&-0Wd22Pٷ3K)l(22Qdqd 싖"0]v`l9r "uMJՒDf|/~ɜ ).S8g \22ld=&YtAv@6AI 9c#dC2L=='e;gd|:3a%}#nqYND3;B[wH"?e{ R1/ DG joڼ+^I{V}3h ?xKʵ_;B̷iu(OḑQdaD7V퐑qVk"VcB0-osTc^I֪Z SŴ0rQ.+)y='0BxGd/w4wǪ]C#6G ."䜏5?sUR&55Ⱥ9Y)9%@3ks:t9buԅUOg%:ړgE1R @lҁq:X="o5ś5Zt EۼUuvNͻ4;^2͛]h'Õi =M})X[2_'G2bz}2e9%Pnz 99>;ɛ"WNhA;LrAy[E "-cQ!E+rKrs,R6X^xrEyr] &RoXd?U7{rF?z#OK}A |@yH ,)3ܫCk'O`_SٷGh=ײZ͆6|هCzRsF6vH;M6Ss.]޸Z,kgНvޙ:Վ W=9)d]2s/ɒY\zk^re.xkǼЄ~j_nyH֒X?Z-;ƚhj8TCXp<-me(X|@T{MŨ75TOC PB;XKc6e>jA L>y%JG,ml'vR>sR⥪ݐvG)z0Ss XdU ׮&='v\>l9?F*iuZ,ie$#y-GzX_he6QftR[$lpo[8y܎;-ܰkrݗ+I4}H{QYT=ht7T gZls"?:ld5Rm}ٶrr2qP6,y6Ybr>e<ODmܷ xty$/93y4+f&хXaK_#.K#|G%mU:3v;J7'wh%B'} {pHxS2Pb)I/RI~EJnK^ ~9KC`M7f҇Ѵc12~A6vA0igC Hk(u"RRj1ʛVjꔫN*|.' RМ%"\Rs~&.u-yf{ˮH{}][2–uulb3܏`|$wƹSV˭nUsM& ?u?]][zWܲ8KrX "pK(Q.5vQG9wHBCw (토fns30m!. %btc.6-뻾r9E qrupЍ>vaN@q]W#h"07y9?.w쿇8w,i{6vehv?ZaNJntVm$NZY`﹇Vٽ]C5j4:.sc%e oK,ѹ@;K mrI#ZnK"D[iC Cۮnfc5NN8Y7]4eF '7-?~7tQ׵D ۃk e%7,ebs-{r<|P(ij9\kځf\o ww? ba/`7C { v˟nK?#_5R~KN .~PS^_*NxԾjI[!޺"^p{!WN:b(TZ~ތ=޲VEX[ސ.ut'Qyky\;ok*Y ?]Z5ױfح ٞ5(E{(WIKgjz$+pV{(TAݎ:_#gy/K"`JʌamF-gYѫkִڝߊ~'!3`!wI)Vc$h xڕyTUǟEʢ(hF&hh1'y%q"5q4\rI1P/~p>lwy}_W[3/Vfm$c|ynUX?$#%~BZicÒ'#Fts*6ܭ|askʧKS6* ؟ETM6jeyN^7q& I&~99+l1~z73!Z`B{ȏ&\Lb:}n-1;㣧5 g$ܖ,|l 8qYbre)s:ydl3$M($ cR(lS3CiN.~Ϛ߳,llvX"a)QUڠL^@4cM;];CRBK12 @.H&kD(j2t *d4_]Fa EHJ/n'ܥ;hyJ,zK4FK+L,&X'a%RjDXB{}jx'jIb;rwcioI&e\=ki~ iw4ԿyG3<$:l99!ij3*AHzHbL9 !f3)r$ 6P;~߅ -z 5wvl6Vs3ENnϿsg, >rWBgMH?)aR,(,$ ! l &~ K^9m%>>7;-|GcC&d*dJl|4x@ a>A2V# 1S08 B$ !Qa 3&a?mLWwCwƤ) /ڐґؿ}G.2I< 1Οuj1GQChNxWb>X)gBܣ^eԐ >CZ$D@ƒTɔd)IM2F|ʤ<=b{Pٻ׹6 l I&Y@fsӌ;Fm L1 i}q|!WȢ~Cr DI ˰sw_SWe:A$ԥ}wK]ݥ=RX;9+4^ ?@R7P+#S_N{# vzXK:$8u:E}^iW)-ƹ;9}GJH8u ՗jě:oڽMjćj0 LJB8^R'#$U;9k[mCֵI /:&I}Mkүbǻ:guְ^笾O@iuO(K?;Q;9ZCyN6cG^W/IPpK)f bM]AfY|ns1`:O]*:Ho2^Ցz"ʗD%ѿqWw+ND^&]骿h7&SkNw@^iJc҄44H"\WsҔzV_?ab\֖Dq6"IsMy)d_1X9W>hUC^j~uܹ;X;sp&8\}םǺ+GYe*1;Y8*EV$@[+D+jRVU'pqnVTyXX f ^&M:XJi#,hFЂ}hVdU@-,Es,A,f,2b sbUGM9(@G(ytR2^fTb,cR.XNv9-; ˬ5SܷrIӧPi.Z[=_9KP%( (/ 0DTimes New Roman20Wo 0DArialNew Roman20Wo 0" DCourier (W1)an20Wo 0 10DSymbol (W1)an20Wo 0@DWingdings1)an20Wo 0PDScript MT Bold20Wo 0B ` .  @n?" dd@  @@`` =R W $? I-6 9& Kk  `,   (?2$}WB6)E>y52$ 4AC52$wI)x,c $P333@Eg4<d<d0ppp@ <4!d!d 0L3 uʚ;hZ5ʚ;<4ddddЁ 0<4BdBdЁ 0___PPT9z{L10p " ? %idChanging the Tapestry Inserting and Deleting NodesoKris Hildrum, UC Berkeley hildrum@eecs.berkeley.edu Joint work with John Kubiatowicz, Satish Rao, and Ben Zhaoppt    03*!Tapestry with Inserts and Deletes 3%OutlineNInsert Finding surrogates Constructing Neighbor tables Delete Unplanned Delete600!Requirement for Insert and DeleteUse no central directory No hot spot/single point of failure Reduce danger/threat of DoS. Must be fast/touch few nodes Minimize system administrator duties Keep objects available6AZAZRAcknowledged Multicast Algorithm Locates & Contacts all nodes with a given suffix S!2PCreate a tree based on IDs as we go Starting node knows when all nodes reached  PQThree Parts To Insertion yEstablish pointers from surrogates to new node. Notify the need-to-know nodes Create routing tables & notify other nodes ,y" y+ Finding the surrogatesThe new node sends a join message to a surrogate The primary surrogate multicasts to all other surrogates. Each surrogate establishes a pointer to the new node. When all pointers established, continueZ)8&=Constructing the Neighbor Table via a nearest neighbor search*> $$$/Suppose we have a good algorithm A for finding the three nearest neighbors for a given node. To fill in a slot, apply A to the subnetwork of nodes that could fill that slot. For ????1, run A on network of nodes ending in 1 Can do something more that requires less computation, but uses nearest neighbor.1Q!T7!Q 0"Finding Nearest NeighborLet j be such that surrogate matches new node in last j digits of node ID G = surrogate G sends j-list to new node; new node pings all nodes on j-list. If one is closer, G = closest, goto A. If not, done with this level, and let j = j-1 and goto A.4YZ" ZY.!IIs this the nearest node? Yes, with high probability under an assumption$J.=Pink circle = ball around new node of radius d(G, new node) Progress = find any node in pink circle Consider the ball around the G containing all its j-list. Two cases: Black ball contain pink ball; found closest node High overlap between pink ball and G-ball so unlikely pink ball empty while G-ball has k nodes .ZZ1#The Grid-like assumptionThe algorithm for finding the first entry works for any grid-like network Same as the assumption that Plaxton, Rajaraman, and Richa make.>h   Delete - TerminologyPlanned Delete TNotify its neighbors (O(log2 n)) To out-neighbors: Exiting node says  I m no longer pointing to you To in-neighbors: Exiting node says it is going and proposes at least one replacement. Exiting node republishes all objects ptrs it stores Use republish-on-delete to clean things up Objects rooted at exiting node get new roots Either proactive pointer copying, or wait for republishes and mean time, switch routing planes. !ZZ.ZaZZ DW_.a Republish-On-DeleteUnplanned DeletePlanned delete relied exiting node s neighbor table. List of out-neighbors List of in-neighbors Closest matching node for each level. Can we reconstruct this information? Not easily Fortunately, we probably don t need to.L7Q&37Q&3Handle Unplanned Delete LazilylA notices B is dead, A fixes its own state A removes B from routing tables If removing B produces a hole, A must fill the hole, or be sure that the hole cannot be filled use acknowledged multicast A republishes all objs with next hop = B. Use republish-on-delete as before Good: Each node makes a local decision, so no DoS problems. Problems Delete may never  finish and new nodes may get outdated information. Partial delete undetected.+Z ZzZ*Z"ZEZaZ+ z*"  Ea?u JConclusion  Insert and Delete works!&&( / ,-/4 ` ` ̙33` 333MMM` ff3333f` f` f` 3>?" dd@,|?" dd@   " @ ` n?" dd@   @@``PR    @ ` ` p>> (    6k P  T Click to edit Master title style! !B  00n <$ 0  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  0r ``  71/17/01  0w `   <   0y `   @*H  0޽h ? ̙33 Default Design 0 x*(  x x 0 P   0 X*  x 0    0 Z* d x c $ ?   x 0h  @  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S x 6 `P   X*  x 6S0 `  0 Z* H x 0޽h ? ̙33 8(    0X? P    >*   0|B     @*   6F `P   >*   6XO `   @* H  0޽h ? ̙33  P(  r  S E    S  `  <$ 0  H  0޽h ? ̙33  ld@DJ(  r  S Q`0   X2  0 X2  0X2  0 p` X2  0  X2  0 p` X2  0  X2  0P @X2  0 @0 2  6хp p`  : X2  0 pX2  0  X2  0P @ X2  0 X2  0 `P X2  0p`P` X2  0  X2  0 X2  0  X2  00 R2  s *P @ X2  0P@X2  02  6م3p`  : RB  s *D  RB  s *DP ` RB  s *D@  RB  s *D P@ RB @ s *D RB ! s *D 0 0 RB # s *D 0 RB $@ s *D`PRB %@ s *D RB &@ s *D RB '@ s *D0 ` RB ( s *D PP RB ) s *Dp  RB *@ s *D@ `` RB + s *D @ RB , s *D 0 P RB - s *D@`PRB .@ s *D RB / s *D RB 1 s *D PRB 3 s *D pRB 4 s *DP RB 5 s *D`RB 6 s *DRB 7 s *D @ RB 8 s *D p RB 9 s *D  @ RB : s *D @RB ; s *DP RB < s *D 0pRB = s *DRB ? s *D`  RB @ s *D ` RB A s *D p0 RB B s *D @ 8 0 E@ ZB C s *D>0ZB D s *D>0F 0 F P p ZB G s *D>0ZB H s *D>0RB I s *D  RB J s *D H  0޽h ? ̙33  P$(  r  S P   r  S   H  0޽h ? ̙33  `h$(  hr h S P   r h S   H h 0޽h ? ̙33  bZp,L0 (  Lx L c $P    L  < PpP    L B  ?54345  L B  ?04345 " L 60px  HThe node then sends to any ?0345, any ?1345, any ?3345, etc. if possibleXI  L BX 0    5??345   L B &o  5?1345   L B0   ??4345 B L BDjJ P ,$D 0l    ,L  ,$D 0B L <D P ,$D 0t    $L  ,$D 0 L B0pz  I 04345 & 54345   B LB <D 0  ,$D 0  L 60  6,$D 0 T?4345 sends to 04345, 54345& if they exist+ +B L@ s *D P0 ,$D 0B L s *D 0 ,$D 0B  L@ s *D ` P ,$D 0B !L s *D p,$D 0l P   *LP  ,$D 0B L <D  ,$D 0 (L 0 0 P p  < 2l  @S +L @S,$D 0r "L 6GEH5`I: P S,$D  0 )L 0|$0P @@  < 2H L 0޽h ?  LL"L ̙33  l:(  lr l S t0`Pp0  0  l S Hz0@  0 "p`PpH l 0޽h ? ̙33  j 0(  r  S x0P  0   S ,0   <$ 0 0 B ' <DP  ,$D  0B (@ <D ,$D 0z 6V )   ,$D 02 * s *6|V,$D 0 + <N?9,$D 0 =01234B 7 s *D 0 ,$D 0B 8 s *D ` ,$D 0B 9 s *D` ,$D 0B : s *D 0 ,$D 0B I s *D` 0 @ ,$D 0B ` s *Dp,$D  0_ l @ 40  j@ 40 ,$D 0t UV ^04,$D  02 / 6fV,$D 0 1 BɻUO,$D 0 =013342 4 6P p0` ,$D  0 5????42 5 6ܐ00  ,$D  0 5???342 6 6 0@ @ 0 ,$D  0 4Gate v Up  a  ,$D 02 b 0v Uf ,$D 0 c <0Hv Lp ,$D 0 =79334 v Uz  d ` Z,$D 02 e 0v Uf ,$D 0 f <0Hv Lz ,$D 0 =39334B g@ s *D`` ,$D  0 h 040PP @p > surrogates 2  i 00  <new node 2 H  0޽h ? ̙33R 0(    6tb 0 fNeed-to-know nodes,  04k  &Need-to-know = a node with a hole in neighbor table filled by new node If 01234 is new node, and no 234s existed, must notify ???34 nodes Acknowledged multicast to all matching nodes During this time, object requests may go either to new node or former surrogate, but that s okay Once done, delete pointers from surrogates.jG!0Zq!0Z!0ZGpH  0޽h ? ̙33  $(  r  S 0`P  0 r  S p0 0 H  0޽h ? ̙33   +@(  r  S 0`  0   S `00  <$ 0 0 "P@08Xz 6V    ,$D 02  s *6|V,$D 0   <T0?9,$D 0 =01234 z UV   04,$D 02   0fV,$D 0   <00UO,$D 0 =013342  00P @ ,$D 0 5615242  0*0 P ,$D 0 5321346l   ( ,$D 0B B s *D   ,$D  0B  s *D,$D  0B B s *D0,$D  02 # 0P  ,$D 0 511111J    )#   ,$D 0B B s *D  ,$D  0B B s *D   ,$D  0B ! s *D  ,$D  0l   + ,$D 0B  0DP ,$D 0B $ 0D @  ,$D 0 & 0޻``L,$D 0 g7j-list is closest k=O(log n) nodes matching in j digits8 8H  0޽h ? ̙33  -_ H(  r  S ,0`  0 r  S 0P  0  * 00   *G, matches in j digits + <00P 7V 8New node 2 d2  <  d2  <  d2  <33ox  ^2  63x ` LF^2  6i ^2  6b < ^2  6 a ^2  6 Da ^2  6 5R7 ^2  6 /L ^2  6E b ^2  6T q ^2 ! 6 w ^2 " 6 ^2 # 6 Ro! ^2 $ 6q ^2 % 67 wT ^2 & 6 J h ^2 ' 6 w ^2 / 6 / l8  Q0  [0T  0  L#  Q0 f2 M 6 f2 N 6   f2 O 633o@0 f2 P 6 0 `2 Q 0 [; `2 R 0@  `2 S 0  `2 T 0 ; `2 U 0 p k `2 V 0 + `2 W 00p { `2 X 00P { `2 Y 0  `2 Z 0p K RB \ s *D @RB ] s *D0P P RB ^ s *D` RB _@ s *D  H  0޽h ? ̙33  0$(  r  S Dr  r r  S 'r r H  0޽h ? ̙33?    @#0 (  0l 0 C /rP  r |l ` 0 !0` 0,$D 0fB 0 6D ` fB 0 6D ` fB  0 6Dp ` Z2 0 s *P P 2 0 00 P  ?543212 0 0 0  711115 0 <0rV G   =xxx45 0 <t4r 4 T  5xxxx5 0 < 9r O   In-neighborsl *   0* ,$D 02 0 6;r@`  J 12345( 0 <h@r *J   exiting nodewl 0:  #0:0 ,$D 0 0 0Cr` @: 511111V@ 0:  "00: fB 0 6D 0 @fB 0 6D0 pfB 0B 6D0 0 Z2 0 s * Z2 0 s *0 2 0 0HIr0 p0 :  0 <Hr T  =xxxx1 0 < Pr:Z ! out-neighborsH 0 0޽h ? ̙33  P $(   r  S |dr  r r  S  er P` r H  0޽h ? ̙33  UM`+H8(  8l 8 C krP  r tl   8 ,$D 0`2 8 00  `2 8 0  `2 8 0 `2 8 0 `2 8 0 @ p `2 8 00 `2  8 0  PfB  8 6D p fB  8 6DP fB  8 6D  fB 8 6D  fB 8 6D  fB 8 6D` ` fB 8 6D `fB 8 6DP0 fB 8 6D  fB 8 6D0 fB 8 6Dp p ` fB 8B 6D Pl    8 P ,$D 0fB 8 6D>  fB 8 6D>   8 s * ,$D 0B 8 6D  ,$D 0l   .8 ,$D 0fB %8B 6D` @ fB &8B 6D` fB '8B 6D0 `  +8 BCPDEF00hxP@   fB -8 6D 0  08 0$,r0  ,$D 0 E republish  48 0wrP @$ ,$D 0 E republish  58 0|r ,$D  0 E republish B >8@ BD>0 ` ,$D  0l  `P  G8 `P ,$D 0 38 0gr `,$D 0 E republish lR D8 <ZGHI P l  p  H8p ,$D  0 18 0r p D,$D  0 E republish fr E8B 6GH\I  H 8 0޽h ?/@88D8 88E8 ̙33>  p~(  r  S 8 P   r  S P  &  C AC:\Documents and Settings\hildrum.EECS\Application Data\Microsoft\Media Catalog\Downloaded Clips\cl33\j0128138.wmfP0 $  C AC:\Documents and Settings\hildrum.EECS\Application Data\Microsoft\Media Catalog\Downloaded Clips\cl0\PE02435_.wmf @H  0޽h ? ̙33  P(  r  S "P   r  S #  $  C AC:\Documents and Settings\hildrum.EECS\Application Data\Microsoft\Media Catalog\Downloaded Clips\cl1\SO02914_.wmfP H  0޽h ? ̙33  6.<(  <r < S P/P    < 60`T  zNo central point of failure Touches only polylog n nodes. Minimizes system administrator duties Objects always available{ 2{ H < 0޽h ? ̙33 0 |^(  |X | C x   0 | S x_0x @  0 `LDoesn t save bandwidth/transit time. Problem solved is that we don t know the names of all nodes. (hence locate) Takes time proportional to number of nodes contacted.H | 0޽h ? ̙33n 0 .&(  X  C x   0&  S 10x @  0 Explain surrogate. One root per routing plane; ignoring multiple routing planes in this talk. Routing tables and notifiy ohters same step.q H  0޽h ? ̙33 0 4(  X  C x   0  S @0x @  0 6"Fairly small number about 16 nodesH  0޽h ? ̙33! 0  o(  X  C x   r  S Drx @  r q]Imagine network two dimensional grid Intersection could easily be empty for general metrics. H  0޽h ? ̙33  0 .(  X  C x   0  S L?0x @  0 0Green nodes are surrogates. H  0޽h ? ̙33r@X%7 ի W Uei .(3o9gk-ɖ3 S@8Ʉ#&8sOh+'0D `h  Removing Nodes from TapestrytNo NameK H34Microsoft PowerPointape@Z@P\@ jm%I.G8 g  *& &&#TNPP2OMir & TNPP &&TNPP    --- !---&G&rw@ + UwUw0- @Times New Roman UwUw0- .2 R1/17/01   .&Gy& --Qq@-- @"Arialw@ 1 UwUw0- .'2 }Changing the Tapestry+$!#$$$$!#!$!  . . 2 :. .*2 Inserting and Deleting $!!$$!#$+! $$. .2 E~Nodes+$$ !.--Q1-- @"Arialw@W UwUw0- .2 'Kris   . .2 gHildrum . .2  , UC Berkeley   . .(2 hildrum@eecs.berkeley.     . . 2 redus. .'2 FJoint work with John       . .2 F Kubiatowicze . . 2 Fn, . .2 F Satish Rao  . . 2 F, . .2 m|and Ben   . . 2 mZhao.--"System 0-&TNPP &՜.+,0     6On-screen Show  UC BERKELEY% Times New RomanArial Courier (W1)Symbol WingdingsScript MT BoldDefault Design3Changing the TapestryInserting and Deleting Nodes"Tapestry with Inserts and DeletesOutline"Requirement for Insert and DeleteSAcknowledged Multicast Algorithm Locates & Contacts all nodes with a given suffix Three Parts To InsertionFinding the surrogatesPowerPoint Presentation>Constructing the Neighbor Table via a nearest neighbor searchFinding Nearest NeighborJIs this the nearest node? Yes, with high probability under an assumptionThe Grid-like assumptionDelete - TerminologyPlanned Delete Republish-On-DeleteUnplanned Delete Handle Unplanned Delete Lazily&Conclusion Insert and Delete works!  Fonts UsedDesign Template Slide Titles_K HK H  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root EntrydO)Pictures;5Current UserSummaryInformation(PowerPoint Document(DocumentSummaryInformation8