From lynch@theory.lcs.mit.edu Sun Aug 18 11:59:38 2002 Date: Sun, 14 Jul 2002 23:17:50 -0400 From: Anish Arora X-Accept-Language: en To: lynch@theory.lcs.mit.edu Subject: Followup on our last conversation Content-Type: multipart/mixed; boundary="------------BE6B3BE9422290BF20B8AA17" X-Spam-Level: X-Spam-Status: No, hits=1.8 required=5.0 tests=DEAR_SOMEBODY,DATE_IN_FUTURE version=2.20 X-Spam-Level: * This is a multi-part message in MIME format. --------------BE6B3BE9422290BF20B8AA17 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Dear Nancy, I'm delighted you're planning on discussing stabilization in some depth in your course. Here are my suggestions: 1. Distributed Reset A. Arora and M. G. Gouda. IEEE Transactions on Computers, 43(9), 1026--1038, 1994. http://www.cis.ohio-state.edu/siefast/group/publications/distributed-reset.pdf I use this, if not Dijkstra's token rings, to introduce stabilization (in the traditional sense). As you might recall, the problem deals with faults occurring in the reset process itself; stabilization occurs in the presence of dynamic nodes and links; and layering as well as refinement of stabilization are discussed. 2. Designing masking fault-tolerance via nonmasking fault-tolerance. A. Arora and S. Kulkarni. IEEE Transactions on Software Engineering, Vol. 24, No. 6, 435-450, 1998. http://www.cis.ohio-state.edu/siefast/group/publications/masking.pdf Next, I discuss weakening stabilization to occur not from arbitrary states, but from the more limited illegitimate states that are reached, in this case, in the presence of dynamic (node and link) faults. This paper also makes the point that stabilization in this weak form is an adequate basis for designing masking fault-tolerance. A couple of nice examples of stabilization in this weak form in the presence of dynamic faults are in: Fault-tolerant reconfiguration of trees and rings in distributed systems. A. Arora and A. Singhai. Journal of High Integrity Systems, 1(4), 375c-384, 1995. http://www.cis.ohio-state.edu/siefast/group/publications/tree-rings.pdf 3. Compositional design of multitolerant repetitive Byzantine agreement. S. Kulkarni and A. Arora. Proceedings of the 18th Intl. Conf. on the Foundations of Software Technology and Theoretical Computer Science, Kharagpur, India, 1997. http://www.cis.ohio-state.edu/siefast/group/publications/ka1997-cdomrba-fsttcs.pdf This paper makes the point that stabilization is possible with respect to Byzantine faults. It does not, however, make the point that for some problems it is possible to stabilize from a larger number of Byzantine faults than it is possible to mask. That aspect is considered in our more recent work. This paper also makes the point that it is possible to co-satisfy stabilization (with respect to one class of faults) with masking tolerance (with respect to another class of faults). Such "multitolerance" and its systematic (& even automatic) design has been one of the themes in our work. Shlomi's book covers convergence in the presence of Byzantine faults too: ``Self-Stabilizing Clock Synchronization in the Presence of Byzantine Faults,'' Dolev, S., and Welch, J., Proc. of the 2nd Workshop on Self-Stabilizing Systems, UNLV, May 1995. http://www.cs.bgu.ac.il/~dolev/publications.html 4. In terms of patterns and methods for stabilization, George Varghese's work (on local checking/correction, constraint satisfaction, counter flushing, window washing) is a fine starting point. By way of contrast, our work focuses on separating the aspect of stabilization (or tolerance) from the functional part of systems: Detectors and correctors: A theory of fault-tolerance components. A. Arora and S. Kulkarni. ICDCS'98. http://www.cis.ohio-state.edu/siefast/group/publications/ak1998-dacatoftc.pdf While the terms detectors/correctors unfortunately sound generic, the intent is to stabilize and/or preserve safety via enforcement of state predicates, as opposed to, say, enforcement of preconditions and postconditions on method arguments or enforcement of temporal rely-guarantee contract of a server with respect to a client. It has led us to building in our DARPA project (C and C#) frameworks for dynamically composing detector-corrector wrappers around components. =========== As I mentioned, Shlomi's book covers themes other than the ones I've focussed on here. I think the strength of his book lies in discussing: 1. minimal state needed to design stabilization 2. minimal convergence time needed for stabilization 3. containment of a bounded number k of faults (e.g. crashes or transients at k nodes), while still achieving stabilization. 4. transformers between models that preserve stabilization =========== It was my impression that you would prefer not to cover recent papers whose themes are still being flushed out. Allow me, still, to comment on some interesting new themes that are being developed in the area. 1. Snap-stabilization: The idea here is that stabilization occurs in 0 time. This is of course possible when all states are legitimate, but it is possible in a more interesting way when there are illegitimate states, but every fresh method invocation returns only correct results (by cleaning the component state in the course of execution). It is only the partial method executions that can yield incorrect results upon starting from an arbitrary state. Vincent Villain in France is the best advocate in this direction. See, for example, A. BUI, A.K. DATTA, F. PETIT, V. VILLAIN. State-Optimal Snap-Stabilizing PIF in Tree Networks. 4th Workshop on Self-Stabilizing Systems (WSS '99) 2. Data structure stabilization: In my opinion, the new aspect in considering stabilization of data structure components is the dependency/effect of the data on the client(s) of that data. In other words, even though a data server may be stabilizing in its own right and its client may be likewise be stabilizing, the composition of the two may not, if the server responds with incorrect results on the client invokes with incorrect arguments. Ted Herman at Iowa is leading this direction. http://www.cs.uiowa.edu/ftp/selfstab/main.html We ran into the client-data server composition issue in: Resettable vector clocks. A. Arora, S. Kulkarni, and M. Demirbas. 19th ACM Symposium on Principles of Distributed Computing (PODC'2000), Portland, 2000. http://www.cis.ohio-state.edu/siefast/group/publications/akd2000-rvc.pdf 3. Specification-based stabilization: Stabilization suffers from the complexity of identifying all states of a given concrete program that are legitimate with respect to a given abstract program (i.e. a specification). The idea in this direction, then, is --rather than identifying the legitimate states of the concrete program, to identify the legitimate states of the abstract program and to design stabilization of concrete program based only on the latter set of states. Experiences with a home networking project and an internet server design showed us that specification-based stabilization is effective. 4. Convergence refinement: This direction is related to the one above. Standard (e.g. Java) compilers do not preserve stabilization, Also, existing compilers/model transformations that do preserve stabilization do not yield refinement/simulation style implementations, since they allow (in the presence of faults) different visible recovery paths in the abstract and the concrete program. This has led us to study generalizations of refinements that are suitable for stabilization preserving compilers. Convergence refinement. M. Demirbas and A. Arora. (Best Paper Award). ICDCS 2002 http://www.cis.ohio-state.edu/siefast/group/publications/demirbas2001convergence-refinement.pdf 5. Preserving security despite stabilization: Gouda's notion of "protection" insists that safety is preserved during convergence. More specifically, program variables are divided into critical and noncritical, and all sequences of changes to critical variables starting from illegitimate states are shown to track corresponding changes from some legitimate state. The security of standard protocols (for authentication, nonrepudiation, privacy, integrity, etc.) has been proven using this definition. 6. Transient failure detectors: Shlomi has done some nice work in this direction. 7. Stabilization in peer to peer networks: Chord and other distributed hashing schemes are rediscovering stabilization. The necessity of providing stabilization guarantees in the presence of continuous perturbations is reinforced by this work. In the past, we've looked at how to prove stabilization in load balancing systems where the environmental perturbations were modeled in terms of flow equations. 8. Stabilization in geometric algorithms. 9. Weaker definitions of stabilization: -Stabilization of some computations from each state. -Stabilization that yields computations that are, probabilistically speaking, almost always in legitimate states. 10. Relation of stabilization to controllability in DES, and to Lyapunov stability in continuous systems. =========== In closing, I'm taking the liberty of attaching a "soft" article: a polemic in response to questions that systems folks frequently ask about stabilization. Your comments and advice would, of course, be very welcome. =========== With best wishes for an enjoyable vacation, Anish PS: In case some of my pointers have typos in them, the self-referencial papers are also available from the publications in my home page at http://www.cis.ohio-state.edu/~anish . --------------BE6B3BE9422290BF20B8AA17 Content-Type: application/postscript; name="HotNetsStabFinal.ps" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="HotNetsStabFinal.ps" %!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: HotNetsStabFinal.dvi %%Pages: 9 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%DocumentFonts: Times-Roman Courier Times-Bold Times-Italic %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips HotNetsStabFinal -o %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2002.07.14:2310 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72 mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{ landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[ matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{ statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0] N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin /FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array /BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2 array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get }B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub} B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr 1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3 1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx 0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{ rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B /chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{ /cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{ A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse} ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17 {2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{ 1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop} forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put }if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{ bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{ SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{ userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X 1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4 index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N /p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{ /Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{A length product length le{A length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot} imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M} B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{ p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end %%EndProcSet %%BeginProcSet: 8r.enc % @@psencodingfile@{ % author = "S. Rahtz, P. MacKay, Alan Jeffrey, B. Horn, K. Berry", % version = "0.6", % date = "1 July 1998", % filename = "8r.enc", % email = "tex-fonts@@tug.org", % docstring = "Encoding for TrueType or Type 1 fonts % to be used with TeX." % @} % % Idea is to have all the characters normally included in Type 1 fonts % available for typesetting. This is effectively the characters in Adobe % Standard Encoding + ISO Latin 1 + extra characters from Lucida. % % Character code assignments were made as follows: % % (1) the Windows ANSI characters are almost all in their Windows ANSI % positions, because some Windows users cannot easily reencode the % fonts, and it makes no difference on other systems. The only Windows % ANSI characters not available are those that make no sense for % typesetting -- rubout (127 decimal), nobreakspace (160), softhyphen % (173). quotesingle and grave are moved just because it's such an % irritation not having them in TeX positions. % % (2) Remaining characters are assigned arbitrarily to the lower part % of the range, avoiding 0, 10 and 13 in case we meet dumb software. % % (3) Y&Y Lucida Bright includes some extra text characters; in the % hopes that other PostScript fonts, perhaps created for public % consumption, will include them, they are included starting at 0x12. % % (4) Remaining positions left undefined are for use in (hopefully) % upward-compatible revisions, if someday more characters are generally % available. % % (5) hyphen appears twice for compatibility with both % ASCII and Windows. % /TeXBase1Encoding [ % 0x00 (encoded characters from Adobe Standard not in Windows 3.1) /.notdef /dotaccent /fi /fl /fraction /hungarumlaut /Lslash /lslash /ogonek /ring /.notdef /breve /minus /.notdef % These are the only two remaining unencoded characters, so may as % well include them. /Zcaron /zcaron % 0x10 /caron /dotlessi % (unusual TeX characters available in, e.g., Lucida Bright) /dotlessj /ff /ffi /ffl /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef % very contentious; it's so painful not having quoteleft and quoteright % at 96 and 145 that we move the things normally found there to here. /grave /quotesingle % 0x20 (ASCII begins) /space /exclam /quotedbl /numbersign /dollar /percent /ampersand /quoteright /parenleft /parenright /asterisk /plus /comma /hyphen /period /slash % 0x30 /zero /one /two /three /four /five /six /seven /eight /nine /colon /semicolon /less /equal /greater /question % 0x40 /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O % 0x50 /P /Q /R /S /T /U /V /W /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore % 0x60 /quoteleft /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o % 0x70 /p /q /r /s /t /u /v /w /x /y /z /braceleft /bar /braceright /asciitilde /.notdef % rubout; ASCII ends % 0x80 /.notdef /.notdef /quotesinglbase /florin /quotedblbase /ellipsis /dagger /daggerdbl /circumflex /perthousand /Scaron /guilsinglleft /OE /.notdef /.notdef /.notdef % 0x90 /.notdef /.notdef /.notdef /quotedblleft /quotedblright /bullet /endash /emdash /tilde /trademark /scaron /guilsinglright /oe /.notdef /.notdef /Ydieresis % 0xA0 /.notdef % nobreakspace /exclamdown /cent /sterling /currency /yen /brokenbar /section /dieresis /copyright /ordfeminine /guillemotleft /logicalnot /hyphen % Y&Y (also at 45); Windows' softhyphen /registered /macron % 0xD0 /degree /plusminus /twosuperior /threesuperior /acute /mu /paragraph /periodcentered /cedilla /onesuperior /ordmasculine /guillemotright /onequarter /onehalf /threequarters /questiondown % 0xC0 /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla /Egrave /Eacute /Ecircumflex /Edieresis /Igrave /Iacute /Icircumflex /Idieresis % 0xD0 /Eth /Ntilde /Ograve /Oacute /Ocircumflex /Otilde /Odieresis /multiply /Oslash /Ugrave /Uacute /Ucircumflex /Udieresis /Yacute /Thorn /germandbls % 0xE0 /agrave /aacute /acircumflex /atilde /adieresis /aring /ae /ccedilla /egrave /eacute /ecircumflex /edieresis /igrave /iacute /icircumflex /idieresis % 0xF0 /eth /ntilde /ograve /oacute /ocircumflex /otilde /odieresis /divide /oslash /ugrave /uacute /ucircumflex /udieresis /yacute /thorn /ydieresis ] def %%EndProcSet %%BeginProcSet: texps.pro %! TeXDict begin/rf{findfont dup length 1 add dict begin{1 index/FID ne 2 index/UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics exch def dict begin Encoding{exch dup type/integertype ne{pop pop 1 sub dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def} ifelse}forall Metrics/Metrics currentdict end def[2 index currentdict end definefont 3 -1 roll makefont/setfont cvx]cvx def}def/ObliqueSlant{ dup sin S cos div neg}B/SlantFont{4 index mul add}def/ExtendFont{3 -1 roll mul exch}def/ReEncodeFont{CharStrings rcheck{/Encoding false def dup[exch{dup CharStrings exch known not{pop/.notdef/Encoding true def} if}forall Encoding{]exch pop}{cleartomark}ifelse}if/Encoding exch def} def end %%EndProcSet TeXDict begin 40258431 52099146 1000 600 600 (HotNetsStabFinal.dvi) @start %DVIPSBitmapFont: Fa cmr8 8 1 /Fa 1 52 df51 D E %EndDVIPSBitmapFont /Fb 103[55 30[55 1[55 1[55 55 55 55 1[55 55 55 55 55 55 1[55 55 2[55 55 55 55 55 38[55 55 55 3[55 1[55 55 1[55 55 55 45[{TeXBase1Encoding ReEncodeFont}29 90.9091 /Courier rf %DVIPSBitmapFont: Fc cmsy10 10.95 6 /Fc 6 95 df15 D41 D<0060EE018000F0EE03C06C1607A200781780007C160FA2003C17 00003E5EA26C163EA26C163C6D157CA2000716786D15F8A26C6C4A5AA200015E6D140390 B7FC6C5EA3017CC7EA0F80A2013C92C7FC013E5CA2011E141E011F143EA26D6C5BA20107 14786E13F8A26D6C485AA201015CECF003A201005CECF807A291387C0F80A2023C90C8FC EC3E1FA2EC1E1EEC1F3EA2EC0FFCA26E5AA36E5AA36E5A6E5A324180BE33>56 D<007FB612FEB8FCA27EC9120FB3A7001FB7FC127FA3C9120FB3A8007FB7FCB8FCA26C15 FE283F7BBE33>I<007FB81280B912C0A27ECA1203B3A232187B9F3D>I<15C04A7E4A7EA2 4A7EA34A7EA2EC1F3EA2EC3E1FA2EC3C0F027C7FA24A6C7EA249486C7EA2ECE001010380 A249486C7EA24948137CA249C77EA2011E141E013E141FA2496E7EA2496E7EA249140300 0182A248486E7EA248486E7EA2491578000F167CA248C97EA2003E82A2003C82007C1780 A248EE07C0A24816030060EE018032397BB63D>94 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fd cmr10 10.95 3 /Fd 3 59 df<1430147014E0EB01C0EB03801307EB0F00131E133E133C5B13F85B12015B 1203A2485AA2120F5BA2121F90C7FCA25AA3123E127EA6127C12FCB2127C127EA6123E12 3FA37EA27F120FA27F1207A26C7EA212017F12007F13787F133E131E7FEB07801303EB01 C0EB00E014701430145A77C323>40 D<12C07E12707E7E121E7E6C7E7F12036C7E7F1200 7F1378137CA27FA2133F7FA21480130FA214C0A3130714E0A6130314F0B214E01307A614 C0130FA31480A2131F1400A25B133EA25BA2137813F85B12015B485A12075B48C7FC121E 121C5A5A5A5A145A7BC323>I<121EEA7F80A2EAFFC0A4EA7F80A2EA1E00C7FCB3121EEA 7F80A2EAFFC0A4EA7F80A2EA1E000A2779A619>58 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe cmmi10 10.95 14 /Fe 14 119 df<121EEA7F80A2EAFFC0A4EA7F80A2EA1E000A0A798919>58 D<121EEA7F8012FF13C0A213E0A3127FEA1E601200A413E013C0A312011380120313005A 120E5A1218123812300B1C798919>I97 D100 DI<143C14FEA21301A314FCEB00701400AD13 7E3801FF803803C7C0EA0703000F13E0120E121C13071238A2EA780F007013C0A2EAF01F 14801200133F14005B137EA213FE5BA212015B0003130E13F0A20007131EEBE01CA2143C EBC0381478147014E013C13803E3C03801FF00EA007C173E7EBC1F>105 DI108 D111 DI114 D<147014FC1301A25CA21303A25CA21307A25CA2130FA25CA2007FB512F0B6FC15E03900 1F8000133FA291C7FCA25BA2137EA213FEA25BA21201A25BA21203A25BA21207EC01C013 E01403000F1480A2EBC0071500140E141E5C000713385C3803E1E03801FF80D8003EC7FC 1C3A7EB821>116 D<137C48B4EC03802603C7C0EB0FC0EA0703000F7F000E151F121C01 0715801238163FEA780F0070491400A2D8F01F5C5C0000157E133F91C712FEA2495C137E 150113FE495CA215030001161C4914F0A21507173CEEE038150F031F1378000016706D13 3F017C017313F0017E01E313E0903A3F03C1F1C0903A0FFF007F80D901FCEB1F002E297E A734>I<017E147848B4EB01FC2603C7C013FED807031303000F13E0120E121C01071301 00381400167ED8780F143E00705B161EEAF01F4A131C1200133F91C7123C16385B137E16 7801FE14705B16F016E0120149EB01C0A2ED0380A2ED0700A20000140E5D6D133C017C5B 6D5B90381F03C0903807FF80D901FCC7FC27297EA72C>I E %EndDVIPSBitmapFont /Ff 134[37 1[54 1[37 21 29 25 1[37 37 37 58 21 37 1[21 37 37 25 33 37 33 37 33 11[54 46 42 50 1[42 54 54 66 6[42 1[54 50 1[54 7[37 37 37 37 37 1[37 37 37 37 1[19 25 19 8[37 35[{TeXBase1Encoding ReEncodeFont}46 74.7198 /Times-Roman rf %DVIPSBitmapFont: Fg cmsy6 6 1 /Fg 1 4 df<136013701360A20040132000E0137038F861F0387E67E0381FFF803807FE 00EA00F0EA07FE381FFF80387E67E038F861F038E060700040132000001300A213701360 14157B9620>3 D E %EndDVIPSBitmapFont /Fh 107[45 45 24[40 45 45 66 45 51 30 35 40 1[51 45 51 76 25 51 1[25 51 45 30 40 51 40 51 45 9[91 1[66 1[51 66 1[56 3[61 6[61 66 66 1[66 1[45 4[30 4[45 45 45 45 45 2[23 30 3[30 30 37[51 2[{TeXBase1Encoding ReEncodeFont}48 90.9091 /Times-Bold rf /Fi 105[45 1[40 40 24[40 45 45 66 45 45 25 35 30 45 45 45 45 71 25 45 25 25 45 45 30 40 45 40 45 40 30 2[30 1[30 56 66 66 86 66 66 56 51 61 1[51 66 66 81 56 66 35 30 66 66 51 56 66 61 61 66 1[40 3[25 25 45 45 45 45 45 45 45 45 45 45 25 23 30 23 2[30 30 30 71 34[51 51 2[{TeXBase1Encoding ReEncodeFont}80 90.9091 /Times-Roman rf /Fj 133[35 40 1[61 40 45 25 35 35 45 45 45 45 66 25 40 1[25 45 45 25 40 45 40 45 45 8[56 76 1[66 51 45 56 1[56 66 61 76 51 1[40 30 66 1[56 56 66 61 1[56 6[30 45 2[45 1[45 45 45 45 45 1[23 30 23 2[30 30 40[{TeXBase1Encoding ReEncodeFont}56 90.9091 /Times-Italic rf /Fk 133[53 2[86 60 66 40 47 53 1[66 60 66 100 33 1[40 33 66 60 40 53 66 53 66 60 11[86 80 66 86 1[73 2[113 4[93 1[73 1[86 86 1[86 10[60 60 60 60 60 60 1[33 47[{TeXBase1Encoding ReEncodeFont}40 119.552 /Times-Bold rf /Fl 134[50 1[50 1[50 50 50 50 2[50 50 50 3[50 50 50 50 50 50 50 1[50 32[50 17[50 50 45[{ TeXBase1Encoding ReEncodeFont}20 83.022 /Courier rf /Fm 134[50 2[50 50 28 39 33 2[50 50 78 28 2[28 50 50 33 44 50 44 50 44 7[72 1[94 1[72 1[55 66 2[72 1[89 4[72 4[66 1[72 19[33 25 44[{TeXBase1Encoding ReEncodeFont}31 99.6264 /Times-Roman rf %DVIPSBitmapFont: Fn cmsy10 12 1 /Fn 1 4 df<147014F8A81470007815F0007C1401B4EC07F8D87F80EB0FF0D83FE0EB3F E0D80FF0EB7F80D803F8EBFE003900FE73F890383F77E090380FFF80D903FEC7FCEB00F8 EB03FE90380FFF8090383F77E09038FE73F83903F870FED80FF0EB7F80D83FE0EB3FE0D8 7F80EB0FF0D8FF00EB07F8007CEC01F000781400C7140014F8A81470252B7AAD32>3 D E %EndDVIPSBitmapFont /Fo 133[64 72 1[104 1[72 40 56 48 1[72 72 72 112 40 72 1[40 1[72 48 64 72 64 72 64 11[104 88 80 2[80 1[104 7[80 24[48 45[{TeXBase1Encoding ReEncodeFont}28 143.462 /Times-Roman rf end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%EndSetup %%Page: 1 1 1 0 bop 116 -27 a Fo(Practical)34 b(Self-Stabilization)e(for)j(T)-11 b(olerating)33 b(Unanticipated)g(F)n(aults)1246 155 y(in)j(Netw)o(ork)o (ed)c(Systems)2579 103 y Fn(\003)1003 408 y Fm(Anish)24 b(Arora)818 524 y(Ohio)g(State)i(Uni)n(v)o(ersity)950 641 y(Columb)n(us,)e(OH)653 757 y Fl(anish@cis.ohio-state.edu)2400 408 y Fm(Y)-5 b(i-Min)23 b(W)-8 b(ang)2282 524 y(Microsoft)24 b(Research)2378 641 y(Redmond,)h(W)-12 b(A)2176 757 y Fl(ymwang@microsoft.com)-150 1119 y Fk(Abstract)-150 1326 y Fj(It)18 b(is)g(our)h(position)h(that)f(the)g(pr)l(operty)h(of)e (stabilization)23 b(is)18 b(de-)-150 1439 y(sir)o(able)25 b(for)e(distrib)n(uted,)k(network)o(ed)e(systems)f(to)f(deal)h(with) -150 1552 y(unanticipated)29 b(faults.)k(In)24 b(this)h(article)o(,)i (we)c(pr)l(o)o(vide)k(a)d(g)o(en-)-150 1665 y(tle)c(intr)l(oduction)k (to)c(the)g(concept)i(of)e(stabilization,)k(r)m(espond)-150 1778 y(to)d(various)h(criticisms)h(and)e(misconceptions)j(about)e(its)f (use)o(,)-150 1890 y(and)j(sug)o(g)o(est)i(pr)o(actical)f(appr)l(oac)o (hes)i(for)d(its)f(design.)-150 2148 y Fk(1)119 b(Moti)o(v)o(ation)29 b(f)m(or)h(Stabilization)-150 2319 y Fi(Stabilization)35 b(is)c(the)h(branch)h(of)f(computing)i(that)e(focuses)-150 2432 y(on)39 b(ho)n(w)f(systems)h(deal)h(with)e(arbitrary)j(state)e (corruption)-150 2545 y([14)q(,)26 b(20)q(,)g(12)q(].)38 b(Strictly)27 b(speaking,)j(a)d(stabilizing)j(system)d(is)-150 2658 y(such)d(that)h(e)n(v)o(ery)f(computation)i(of)d(the)h(system,)g (upon)h(start-)-150 2771 y(ing)30 b(from)g(an)g(arbitrary)h(state,)h(e) n(v)o(entually)g(reaches)g(a)d(state)-150 2884 y(from)24 b(which)h(the)g(computation)i(is)d(\223correct\224,)j(i.e.,)d (satis\002es)-150 2997 y(its)g(speci\002cation.)-150 3187 y Fh(Wh)o(y)j(arbitrary)j(state)f(corruption?)98 b Fi(More)28 b(often)h(than)-150 3300 y(not,)35 b(the)d(moti)n(v)n (ation)j(for)d(considering)k(arbitrary)f(states)e(is)-150 3413 y(to)c(account)i(for)f(the)f(ef)n(fects)i(of)e(f)o(aults.)47 b(This)29 b(is)g(especially)-150 3526 y(true)g(when)f(the)g(f)o(aults)h (are)f(transient,)j(originating)h(in)c(en)l(vi-)-150 3639 y(ronmental)i(ef)n(fects,)h(in)d(Heisenb)n(ugs)j(in)d(hardw)o(are) i(or)e(soft-)-150 3752 y(w)o(are,)41 b(in)c(incorrect)j(interactions)h (between)e(components,)-150 3865 y(etc.)27 b(Characterizing)22 b(the)c(ef)n(fects)h(of)f(transient)j(f)o(aults)e(specif-)-150 3977 y(ically)29 b(is)f(hard,)i(hence)f(the)f(assumption)j(that)d(the)h (resulting)-150 4090 y(state)24 b(is)g(arbitrary)-6 b(.)-50 4203 y(That)30 b(said,)k(other)d(f)o(aults\226be)j(the)o(y)d(transient) i(or)e(perma-)-150 4316 y(nent)c(f)o(aults;)h(detectable)h(or)d (undetectable)j(f)o(aults;)g(commu-)-150 4429 y(nication)38 b(or)e(computation)j(f)o(aults,)h(crash)d(or)f(omission)i(or)-150 4542 y(timing)28 b(or)g(Byzantine)h(f)o(aults\226can)i(each)d(be)f (accounted)k(for)-150 4655 y(in)i(terms)g(of)f(their)i(ef)n(fect)g(on)f (the)g(system)g(state)h(and)f(dealt)p -150 4716 788 4 v -51 4770 a Fg(\003)-16 4802 y Ff(This)46 b(w)o(ork)h(w)o(as)g (partially)f(sponsored)i(by)f(D)m(ARP)-7 b(A)45 b(contract)-150 4893 y(OSU-RF)17 b(#F33615-01-C-1901,)22 b(NSF)17 b(grant)i (NSF-CCR-9972368,)g(an)-150 4985 y(Ameritech)e(F)o(aculty)f(Fello)n (wship,)h(and)g(tw)o(o)g(grants)g(from)g(Microsoft)g(Re-)-150 5076 y(search.)2006 1119 y Fi(with)31 b(in)f(a)g(stabilizing)j(manner)f ([3].)49 b(Indeed,)34 b(we)c(observ)o(e)2006 1232 y(that)e(for)g(an)o (y)f(gi)n(v)o(en)h(f)o(ault)g(class)h(there)f(e)o(xists)g(a)f (computing)2006 1345 y(problem)37 b(that)f(admits)g(a)f(stabilizing)k (solution)f(that)e(toler)n(-)2006 1458 y(ates)23 b(that)g(f)o(ault)g (class.)29 b(Still,)22 b(one)h(might)g(ar)n(gue)g(that)g(for)f(par)n(-) 2006 1571 y(ticular)l(,)34 b(well)c(kno)n(wn)h(f)o(ault)g(classes)i (the)d(net)h(ef)n(fect)g(on)g(the)2006 1683 y(system)j(state)g(of)g(e)o (x)o(ecuting)h(the)e(system)h(in)f(the)h(presence)2006 1796 y(of)e(f)o(aults)i(can)e(be)g(characterized)k(precisely)-6 b(,)36 b(so)c(why)f(con-)2006 1909 y(sider)26 b(arbitrary)h(states?)34 b(In)25 b(some)g(cases,)h(this)f(is)g(done)g(sim-)2006 2022 y(ply)20 b(because)i(the)d(process)j(of)d(characterizing)24 b(the)c(corrupted)2006 2135 y(states)32 b(is)e(comple)o(x.)51 b(A)30 b(stronger)i(ar)n(gument)h(for)e(netw)o(orks)2006 2248 y(is)38 b(that)g(e)n(v)o(en)g(humble)h(f)o(aults,)j(such)d(as)e (combinations)k(of)2006 2361 y(node)23 b(f)o(ailures,)g(node)f(repairs) h(\(into,)g(say)-6 b(,)22 b(prespeci\002ed)h(start)2006 2474 y(states\))i(and)e(message)i(loss,)e(can)h(dri)n(v)o(e)f(netw)o (orks)i(into)e(arbi-)2006 2587 y(trary)31 b(states)h([15)q(].)48 b(It)30 b(is)g(not)g(surprising,)k(then,)f(that)d(man)o(y)2006 2700 y(stabilizing)25 b(protocols)g(ha)n(v)o(e)e(been)g(de)n(v)o (eloped)h(for)e Fj(dynamic)2006 2813 y Fi(and/or)j Fj(ad)f(hoc)g Fi(netw)o(orking)i(problems.)2006 3003 y Fh(Wh)o(y)21 b(e)o(v)o(entual)h(satisfaction?)73 b Fi(The)21 b(moti)n(v)n(ation)j (for)d(con-)2006 3116 y(sidering)k(\223e)n(v)o(entual\224)g(satisf)o (action)h(of)c(the)h(speci\002cation)i(af-)2006 3229 y(ter)f(an)f(arbitrary)j(state)e(corruption)j(occurs)d(lies)g(in)g(the) f(dif)n(\002-)2006 3342 y(culty)d(of)f(dealing)i(with)e(f)o(aults)h(in) f(a)f(stricter)j(manner)-5 b(.)28 b(The)18 b(al-)2006 3455 y(ternati)n(v)o(e)23 b(of)e(\223al)o(w)o(ays\224)h(satisfying)i (the)d(speci\002cation)j(in)d(the)2006 3568 y(presence)29 b(of)d(f)o(aults\226in)j(other)f(w)o(ords,)g(to)e(mask)h(the)f(f)o (aults\226)2006 3680 y(is)h(sometimes)i(impossible,)h(impractical,)g (or)d(unnecessary)-6 b(.)2006 3793 y(Another)19 b(alternati)n(v)o(e)i (of)d(al)o(w)o(ays)h(preserving)i(the)d(safety)h(prop-)2006 3906 y(erties)28 b(of)e(speci\002cation,)j(b)n(ut)e(not)g(necessarily)i (the)e(li)n(v)o(eness)2006 4019 y(properties\226in)22 b(other)d(w)o(ords,)h(to)e(f)o(ailsafe)i(the)e(system\226sometimes)2006 4132 y(compromises)24 b(the)f(a)n(v)n(ailability)i(requirements)g(of)d (systems.)2006 4245 y(Thus,)e(allo)n(wing)h(f)o(aults)g(to)f(violate)h (the)f(speci\002cation,)j(albeit)2006 4358 y(temporarily)-6 b(,)25 b(in)e(the)g(presence)i(of)d(f)o(aults)i(is)f(w)o(orthy)g(of)f (con-)2006 4471 y(sideration.)2006 4661 y Fh(Example)j(of)g(a)f (stabilizing)i(netw)o(ork)e(ser)o(vice)p Fi(.)83 b(Aladdin)2006 4774 y([24)q(,)23 b(23)q(])g(is)g(a)h(system)g(for)g(dependable,)i(e)o (xtensible)g(control)2006 4887 y(of)36 b(heterogeneous)k(de)n(vices)d (via)f(an)g(in-home)h(PC)d(cluster)2006 5000 y(and)e(heterogeneous)j (netw)o(ork.)53 b(A)30 b(k)o(e)o(y)i(to)f(the)h(e)o(xtensibil-)2006 5113 y(ity)f(of)f(Aladdin)h(is)g(its)f Fj(Lookup)h(service)p Fi(.)51 b(This)30 b(service)i(re-)p eop %%Page: 2 2 2 1 bop -150 -29 a Fi(sponds)32 b(to)e(tw)o(o)f(types)i(of)f(queries:) 44 b(\(i\))30 b(an)g(attrib)n(ute)j(based)-150 84 y(query)27 b(which)e(returns)i(a)e(list)h(of)g(unique)h(names)f(that)g(match)-150 197 y(the)32 b(attrib)n(utes,)37 b(and)32 b(\(ii\))g(a)f(name)h(based)i (query)f(which)f(re-)-150 310 y(turns)d(the)f(address)i(of)d(an)h (object)h(gi)n(v)o(en)g(the)f(unique)h(name.)-150 423 y(The)38 b(lookup)i(service)g(maintains)g(information)h(re)o(garding) -150 536 y(addressing,)i(location,)f(and)37 b(status)h(of)f(the)g(v)n (arious)i(types)-150 649 y(of)23 b(objects)j(in)d(the)h(home)g(netw)o (ork,)g(including)j(sensors,)e(de-)-150 762 y(vices,)f(and)g (controllers.)-50 875 y(Objects)30 b(typically)i(join)e(and)h(lea)n(v)o (e)f(the)g(netw)o(ork)h(spon-)-150 988 y(taneously)-6 b(.)39 b(T)-7 b(o)25 b(automate)i(the)f(disco)o(v)o(ery)i(process,)g (objects)-150 1100 y(periodically)36 b(\223refresh\224)f(their)e (status)h(and)f(location)h(in)f(the)-150 1213 y(lookup)k(service,)i(at) c(a)f(frequenc)o(y)j(of)e(their)h(choice.)64 b(This)-150 1326 y(frequenc)o(y)23 b(is)d(chosen)j(based)e(on)g(a)f(number)i(of)e (f)o(actors,)j(e.g.,)-150 1439 y(ho)n(w)18 b(often)h(their)g(status)g (changes,)i(ho)n(w)c(much)i(netw)o(ork)g(band-)-150 1552 y(width)27 b(is)f(a)n(v)n(ailable,)j(and)e(ho)n(w)e(much)i(po)n(wer)f (conserv)n(ation)-150 1665 y(is)h(of)f(concern.)40 b(Depending)29 b(upon)f(the)f(frequenc)o(y)i(chosen,)-150 1778 y(refreshes)35 b(are)d(classi\002ed)i(as)f(being)g(either)h Fj(low-fr)m(equency)-150 1891 y Fi(or)23 b Fj(high-fr)m(equency)p Fi(.)-50 2004 y(The)i(speci\002cation)j(of)d(the)h(lookup)h(service)h(is)d(stated)i (in-)-150 2117 y(formally)f(as:)31 b(\223each)26 b(query)f(to)g(the)g (lookup)h(service)g(returns)-150 2230 y(a)i(unique)i(up-to-date)i (response\224.)46 b(F)o(or)28 b(dependability)-6 b(,)34 b(we)-150 2342 y(replicate)26 b(the)e(service)h(on)f(an)f(in-home)i(PC) d(cluster)-5 b(.)31 b(W)-7 b(e)23 b(as-)-150 2455 y(sume)28 b(that)h(refresh)h(messages)f(and)g(queries)h(are)e(broadcast)-150 2568 y(to)23 b(all)h(the)g(replicas.)-50 2681 y(W)-7 b(e)17 b(implemented)j(a)d(stabilizing)22 b(lookup)d(service,)i(as)d (fol-)-150 2794 y(lo)n(ws)33 b([6)q(].)59 b(In)33 b(all)h(correct)h (lookup)h(beha)n(viors,)j(we)32 b(postu-)-150 2907 y(late)e(there)h(al) o(w)o(ays)f(e)o(xists)h(a)e(unique)j(serv)o(er)e(that)h(responds)-150 3020 y(to)37 b(queries,)42 b(and)37 b(this)g(serv)o(er)n(\226which)j (we)c(refer)i(to)f(as)g(the)-150 3133 y(leader)n(\226has)26 b(up-to-date)f(status)f(of)e(the)h(objects.)30 b(Let)22 b Fe(i)g Fi(range)-150 3246 y(o)o(v)o(er)32 b(the)g(replicas;)37 b(the)32 b(boolean)i(model)e(v)n(ariable)h Fe(al)r(iv)s(e:i)-150 3359 y Fi(denotes)k(that)e(node)g Fe(i)g Fi(is)f(running)j(a)d (functioning)k(replica;)-150 3472 y Fe(l)r(eader)m(:i)25 b Fi(denotes)h(that)e(replica)i Fe(i)d Fi(belie)n(v)o(es)j(it)d(is)h (the)g(leader;)-150 3584 y(and)j Fe(uptodate:i)g Fi(denotes)h(that)g (replica)g Fe(i)e Fi(has)h(the)g(most)g(re-)-150 3697 y(cent)33 b(information.)57 b(Then,)34 b(the)f(follo)n(wing)h(logical)f (condi-)-150 3810 y(tions)f(\226Acti)n(vity)-6 b(,)35 b(Unicity)-6 b(,)34 b(and)e(Recenc)o(y\226are)i(in)l(v)n(ariantly)-150 3923 y(true)24 b(of)g(all)f(states)i(in)e(correct)i(lookup)h(beha)n (viors.)-150 4122 y(Acti)n(vity)e(:)29 b Fd(\(\()p Fc(9)p Fe(i)d Fd(:)f Fe(al)r(iv)s(e:i)p Fd(\))d Fc(^)e Fd(\()p Fc(8)p Fe(i)26 b Fd(:)f Fe(l)r(eader)m(:i)i Fc(\))e Fe(al)r(iv)s(e:i)p Fd(\)\))-150 4234 y Fi(Unicity)47 b(:)29 b Fd(\(\()p Fc(9)p Fe(i)d Fd(:)f Fe(l)r(eader)m(:i)p Fd(\))e Fc(^)d(:)p Fd(\()p Fc(9)p Fe(i;)15 b(j)31 b Fd(:)25 b Fe(l)r(eader)m(:i)d Fc(^)e Fe(l)r(eader)m(:j)5 b Fd(\)\))-150 4347 y Fi(Recenc)o(y)j(:)23 b Fd(\()p Fc(8)p Fe(i)j Fd(:)f Fe(l)r(eader)m(:i)j Fc(\))d Fe(uptodate:i)p Fd(\))-50 4591 y Fi(Stabilization)30 b(w)o(as)e(achie)n(v)o(ed)h(by)f(enforcement)i(of)e(each)-150 4704 y(of)38 b(these)g(three)h(state)f(predicates.)74 b(Our)37 b(implementation)-150 4817 y(essentially)e(\(re\)satis\002es)f (each)f(predicate)h(upon)f(its)f(viola-)-150 4930 y(tion.)68 b(The)36 b(corrector)i(for)f Fj(Activity)g Fi(runs)g(a)f(protocol)i (that)-150 5043 y(diagnoses)i(and)d(repairs)i(f)o(ailed)g(replicas.)71 b(The)37 b(corrector)-150 5156 y(for)c Fj(Uniqueness)i Fi(implements)f(a)e(\223weak)i(leader)g(election\224)2006 -29 y(protocol;)26 b(in)d(this)h(protocol,)i(only)e(a)f(unique)i (replica)g(kno)n(ws)2006 84 y(it)33 b(is)h(the)f(leader)i(\(the)f(term) f('weak')h(is)f(used)h(in)f(the)h(sense)2006 197 y(that)28 b(the)f(other)g(nodes)h(need)g(not)f(kno)n(w)g(the)g(identity)h(of)f (the)2006 310 y(leader\).)38 b(Only)26 b(the)g(leader)h(responds)i(to)c (queries.)38 b Fj(Recency)2006 423 y Fi(is)c(automatically)i(corrected) g(in)e(part)g(by)g(the)f(periodic)j(re-)2006 536 y(freshes)25 b(that)f(are)f(recei)n(v)o(ed)i(from)e(the)h(v)n(arious)g(objects.)31 b(The)2006 649 y(refreshes)40 b(serv)o(e)d(to)g(repopulate)j(the)d (lookup)i(database)g(at)2006 762 y(the)29 b(replicas)h(once)f(the)o(y)f (ha)n(v)o(e)h(been)g(repaired.)45 b(While)29 b(this)2006 875 y(is)g(adequate)j(for)d(high-frequenc)o(y)34 b(refreshes,)f(for)c (the)h(case)2006 988 y(of)h(lo)n(w-frequenc)o(y)i(refreshes)h(the)d (replica)h(might)f(respond)2006 1100 y(to)f(queries)h(with)f (out-of-date)j(information)f(for)e(a)f(long)i(in-)2006 1213 y(terv)n(al.)54 b(Therefore,)35 b(as)c(part)h(of)g(the)g (diagnosis)i(and)e(repair)2006 1326 y(protocol,)23 b(the)d(information) j(corresponding)h(to)c(the)g(lo)n(w)g(fre-)2006 1439 y(quenc)o(y)g(refreshes)g(is)e(streamed)h(to)f(the)h(ne)n(wly)f (repaired)i(serv)o(ers)2006 1552 y(to)k(ensure)h Fj(Recency)f Fi(for)g(lo)n(w-frequenc)o(y)i(objects.)2006 1809 y Fk(2)120 b(Ho)o(w)29 b(Stabilization)j(Deals)d(with)2186 1959 y(Unanticipated)i(F)m(aults)2006 2130 y Fi(As)18 b(the)g(comple)o(xity) i(of)e(netw)o(ork)o(ed)i(systems)f(increases,)j(their)2006 2243 y(lik)o(elihood)29 b(of)c(e)o(xperiencing)k(unanticipated)h(f)o (aults)d(sooner)2006 2356 y(or)j(later)i(also)f(gro)n(ws.)49 b(By)29 b(unanticipated)35 b(netw)o(ork)c(f)o(aults,)2006 2469 y(we)20 b(mean)g(not)h(only)g(\(a\))f(occurrence)j(of)e(ne)n(w)e (types)j(of)e(f)o(aults)2006 2582 y(that)k(were)e(not)h(e)o(xplicitly)i (planned)g(for)e(in)g(netw)o(ork)h(design,)2006 2695 y(b)n(ut)30 b(also)g(\(b\))g(occurrence)i(of)d(well)g(kno)n(wn)h(types) h(of)e(f)o(aults)2006 2808 y(b)n(ut)k(at)f(frequencies)j(or)d(in)g (combinations)k(that)c(are)h(abnor)n(-)2006 2921 y(mal.)28 b(Standard)d(netw)o(ork)f(protocol)h(designs)g(are)e(optimized)2006 3034 y(for)33 b(common-case)i(of)e(well-kno)n(wn)h(f)o(aults)g(\(for)f (instance,)2006 3146 y(a)38 b(bounded)i(numbers)f(of)f(node)h(crashes)h (or)e(link)g(crashes)2006 3259 y(or)32 b(message)i(f)o(ailures)g (occurrences)i(o)o(v)o(er)c(some)h(period)g(of)2006 3372 y(time\).)64 b(Exception)37 b(handlers)h(are)d(used)i(to)e(deal)h(with) f(the)2006 3485 y(common-case)22 b(f)o(ault)e(scenarios)i(by)d (detecting)j(speci\002c)f(log-)2006 3598 y(ical)40 b(conditions)i(that) e(arise)g(in)g(these)g(scenarios.)79 b(In)39 b(the)2006 3711 y(rare-case,)f(ho)n(we)n(v)o(er)l(,)f(a)c(ne)n(w)g(type)h(of)f(f)o (ault)i(or)e(a)h(b)n(urst)g(of)2006 3824 y(well)d(kno)n(wn)h(f)o(aults) h(may)e(occur)i(that)f(violates)h(those)g(spe-)2006 3937 y(ci\002c)24 b(conditions.)2106 4050 y(In)18 b(some)g(traditional)j(f)o (ault-tolerance)h(techniques,)g(unan-)2006 4163 y(ticipated)k(f)o (aults)e(of)g(sort)f(\(b\))h(are)f(o)o(v)o(ercome)i(by)e(calculating) 2006 4276 y(the)d(weak)o(er)h(conditions)i(that)e(hold)f(in)g(the)g (presence)i(of)e(mul-)2006 4388 y(tiple)i(f)o(ault)g(occurrences.)31 b(But,)21 b(as)g(mentioned)i(before,)f(such)2006 4501 y(a)29 b(calculation)k(can)c(be)h(comple)o(x;)j(routing)e(is)e(a)g (classic)i(e)o(x-)2006 4614 y(ample)23 b(where)g(calculating)j(the)d (ille)o(gitimate)h(states)g(that)f(are)2006 4727 y(reachable)h(in)d (the)g(presence)i(of)f(multiple)g(f)o(ault)g(occurrences)2006 4840 y(quickly)i(becomes)g(comple)o(x.)29 b(Also,)22 b(man)o(y)g(e)o(xception)i(han-)2006 4953 y(dlers)35 b(may)e(result,)k(yielding)f(designs)f(that)f(are)g(subject)h(to)2006 5066 y(softw)o(are)28 b(engineering)h(concerns)g(about)e(the)f(lack)h (of)f(qual-)2006 5179 y(ity)g(testing)h(of)e(e)o(xception)i(handlers,)h (as)d(well)g(as)g(the)h(poten-)1890 5439 y(2)p eop %%Page: 3 3 3 2 bop -150 -29 a Fi(tial)35 b(for)h(the)f(handlers)i(to)e(interfere)i (with)e(one)g(another)i(or)-150 84 y(with)20 b(the)g(underlying)j (protocol)g(methods,)e(as)f(e)n(videnced)j(by)-150 197 y(the)h(A)-10 b(T&T)21 b(netw)o(ork)k(disaster)g(of)f(1990)g([1)q(].) -150 388 y Fh(Lazy)18 b(conf)n(ormance)h(to)f(corr)n(ect)i(netw)o(ork)e (beha)n(vior)-9 b(.)44 b Fi(Sta-)-150 500 y(bilization)24 b(pro)o(vides)g(one)e(alternati)n(v)o(e)h(that)f(a)n(v)n(oids)i (case-by-)-150 613 y(case)36 b(handling)i(of)e(unanticipated)j(f)o (aults)e(of)f(sort)g(\(b\))f(and)-150 726 y(can)24 b(deal)h(with)f(f)o (aults)h(of)f(sort)g(\(a\).)30 b(W)-7 b(e)23 b(illustrate)j(this)f (point)-150 839 y(with)20 b(an)g(abstract)h(e)o(xplanation)i(of)d (stabilization:)31 b(Stabiliza-)-150 952 y(tion)37 b(in)l(v)n(olv)o(es) i(de\002ning)f(\223correct\224)h(beha)n(vior)g(of)e(the)f(net-)-150 1065 y(w)o(ork)41 b(and)g(by)f(continually)k(checking)f(whether)f(the)e (net-)-150 1178 y(w)o(ork)21 b(is)f(presently)j(conforming)g(to)e(this) g(beha)n(vior)-5 b(.)30 b(In)21 b(other)-150 1291 y(w)o(ords,)37 b(instead)f(of)e(de\002ning)i(speci\002c)f(patterns)h(of)e(incor)n(-) -150 1404 y(rect)k(beha)n(vior)l(,)44 b(stabilization)d(checks)f(for)d (occurrence)k(of)-150 1517 y(an)o(y)21 b(anomalous)i(beha)n(vior)-5 b(.)30 b(Should)22 b(incorrect)i(beha)n(vior)f(be)-150 1630 y(detected,)k(stabilization)h(promises)f(to)d(restore)j(the)e (netw)o(ork)-150 1742 y(beha)n(vior)h(so)e(that)g(e)n(v)o(entually)h (it)f(is)f(correct.)-150 1933 y Fh(Pr)n(e)o(v)o(enting)h(state)g (corruption)g(fr)n(om)g(spr)n(eading)o(.)52 b Fi(There)-150 2046 y(are,)24 b(of)g(course,)i(man)o(y)e(dif)n(ferent)i(w)o(ays)e(to)g (restore)i(netw)o(ork)-150 2159 y(beha)n(vior)l(,)h(the)d(simplest)i (of)e(which)g(is)g(to)g(reset)h(the)g(netw)o(ork)-150 2272 y(to)i(a)f(prespeci\002ed)k(\(or)d(checkpointed)k(or)26 b(otherwise)j(le)o(giti-)-150 2384 y(mate\))20 b(state.)28 b(Resets)21 b(alone)g(do)e(pro)o(vide)j(tolerance)g(to)e(unan-)-150 2497 y(ticipated)38 b(f)o(aults)e(whose)g(net)g(ef)n(fect)g(is)f (transient,)41 b(b)n(ut)36 b(not)-150 2610 y(necessarily)24 b(for)e(other)g(types)g(of)f(unanticipated)k(f)o(aults.)k(The)-150 2723 y(k)o(e)o(y)34 b(intuition,)39 b(then,)e(in)e(designing)h (stabilization)i(to)c(deal)-150 2836 y(with)28 b(a)f(rich)h(class)h(of) f(unanticipated)j(f)o(aults)e(is)f(to)g(partition)-150 2949 y(the)f(protocol)i(into)e(components)i(that)e(are)g(each)h (capable)g(of)-150 3062 y(\(i\))g(correcting)j(their)e(o)n(wn)f(state,) i(when)f(non-conformance)-150 3175 y(to)d(correct)i(beha)n(vior)h(is)e (locally)h(detected,)h(and)e(\(ii\))f(detect-)-150 3288 y(ing)31 b(upon)h(demand)g(\(directly)i(or)d(otherwise\))i(whether)f (the)-150 3401 y(communications)37 b(the)o(y)d(recei)n(v)o(e)g(contain) h(corrupted)i(data,)-150 3514 y(and)23 b(a)n(v)n(oiding/compensa)q(tin) q(g)28 b(for)23 b(the)g(corrupted)i(ones)f([7)q(].)-150 3626 y(The)30 b(latter)i(pre)n(v)o(ents)g(persistent)i(spreading)f(of)e (corruption)-150 3739 y(from)23 b(permanently)k(f)o(ault-af)n(fected)g (components.)-150 3930 y Fh(Lookup)f(ser)o(vice)k(example)e (\(continued\))82 b Fi(During)29 b(a)f(de-)-150 4043 y(plo)o(yment)33 b(period)f(of)f(14)f(days)i(without)g(an)o(y)f (restart,)i(on)e(a)-150 4156 y(cluster)26 b(of)f(four)g (machines\226Jasmine,)k(MagicCarpet,)d(Ab)n(u,)-150 4269 y(and)19 b(Genie\226an)g(unidenti\002ed)i(`glitch')f(caused)f (unanticipated)-150 4381 y(netw)o(ork)36 b(partitioning)j(on)c(a)f (number)i(of)f(occasions.)66 b(W)-7 b(e)-150 4494 y(brie\003y)23 b(describe)h(one)f(such)g(occurrence)j(\(which)d(in)f(f)o(act)h(re-) -150 4607 y(curred)38 b(se)n(v)o(eral)f(times\):)55 b(MagicCarpet)38 b(became)f(isolated)-150 4720 y(from)31 b(the)h(rest)f(of)g(the)h (nodes;)k(Jasmine)c(lost)g(contact)h(with)-150 4833 y(Genie;)40 b(and,)e(Ab)n(u)c(lost)h(contact)h(with)e(both)h(Jasmine)g(and)-150 4946 y(Genie.)47 b(As)29 b(a)g(result)h(of)g(the)g(partitioning,)k (more)29 b(than)h(one)-150 5059 y(node)e(assumed)h(leader)g(status.)42 b(In)27 b(all)h(cases,)h(stabilization)-150 5172 y(restored)c(the)e (system)h(to)e(ha)n(ving)j(a)d(unique)j(leader)f(and)f(sub-)2006 -29 y(sequently)j(the)e(lookup)i(speci\002cation)g(w)o(as)d (resatis\002ed.)2106 84 y(Incidentally)-6 b(,)31 b(our)c (implementation)i(not)e(only)h(tolerated)2006 197 y(certain)20 b(unanticipated)i(f)o(aults)d(via)g(stabilization,)j(it)c(also)h(pro-) 2006 310 y(vided)42 b(stricter)g(guarantees)i(for)c(anticipated)k(f)o (aults.)81 b(W)-7 b(e)2006 423 y(identi\002ed)28 b(the)f(follo)n(wing)h (f)o(aults)g(as)e(being)i(common-case:)2006 536 y(the)c(crash)g(of)f(a) f(single)j(replica)f(and)g(the)f(loss)h(of)f(a)g(single)h(re-)2006 649 y(fresh)j(message.)37 b(T)-7 b(o)25 b(handle)j(the)e(crash)h(of)f (a)f(single)j(replica)2006 762 y(ef)n(\002ciently)-6 b(,)45 b(the)40 b(stabilization)k(for)c Fj(Activity)g Fi(ensures)i(that)2006 875 y(there)34 b(are)f(al)o(w)o(ays)h(tw)o(o)e (or)h(more)g(ali)n(v)o(e)g(replicas)i(with)e(up-)2006 988 y(to-date)25 b(information.)32 b(In)23 b(case)h(the)g(leader)h(f)o (ails,)f(the)g(leader)2006 1100 y(election)40 b(protocol)g(allo)n(ws)e (one)h(of)e(the)h(remaining)i(repli-)2006 1213 y(cas)d(with)g (up-to-date)j(information)f(to)e(automatically)j(as-)2006 1326 y(sume)31 b(the)h(role)f(of)g(leader)-5 b(.)53 b(T)-7 b(o)29 b(handle)k(the)e(single)i(refresh)2006 1439 y(loss)40 b(ef)n(\002ciently)-6 b(,)45 b(we)38 b(add)i(an)f(ackno)n(wledgment)j (mecha-)2006 1552 y(nism)33 b(in)f(which)h(the)g(leader)h(is)e (required)j(to)e(ackno)n(wledge)2006 1665 y(the)j(lo)n(w-frequenc)o(y)i (refreshes.)65 b(Lo)n(w-frequenc)o(y)37 b(objects)2006 1778 y(are)27 b(e)o(xpected)i(to)e(re-transmit)i(their)e(refreshes)i (until)f(an)f(ac-)2006 1891 y(kno)n(wledgment)k(is)d(recei)n(v)o(ed.)45 b(In)29 b(case)g(of)f(high-frequenc)o(y)2006 2004 y(refreshes,)34 b(high)d(data-quality)j(is)c(achie)n(v)o(ed)i(per)f(se)f(and)h(so)2006 2117 y(we)24 b(do)g(not)h(require)h(the)f(use)g(of)f(ackno)n (wledgments.)35 b(Stabi-)2006 2230 y(lization)30 b(thus)f(did)f(not)g (come)g(at)g(the)g(e)o(xpense)h(of)f(\(or)g(inter)n(-)2006 2342 y(fere)c(with\))g(other)g(desirable)i(tolerances.)2006 2635 y Fk(3)120 b(A)23 b(Primer)f(on)h(Designing)h(Stabilization)2006 2807 y Fi(As)35 b(e)o(xplained)k(abo)o(v)o(e,)g(designing)g (stabilization)h(in)l(v)n(olv)o(es)2006 2920 y(characterization)23 b(of)18 b(correct)i(netw)o(ork)f(beha)n(vior)-5 b(.)29 b(Abstractly)2006 3032 y(speaking,)d(this)e(characterization)k(in)l(v)n (olv)o(es:)2143 3185 y Fc(\017)46 b Fi(identifying)21 b(the)d(speci\002cation)j(that)e(the)f(netw)o(ork)h(pro-)2234 3298 y(tocol)24 b(is)f(satisfying,)2143 3450 y Fc(\017)46 b Fi(calculating)21 b(the)d(f)o(ault-free)j(computations)g(of)d(the)g (net-)2234 3563 y(w)o(ork)23 b(protocol,)j(and)2143 3715 y Fc(\017)46 b Fi(sho)n(wing)26 b(that)g(the)g(f)o(ault-free)i (computations)h(satisfy)2234 3828 y(the)23 b(speci\002cation.)2006 3968 y(Lik)o(e)n(wise,)42 b(sho)n(wing)e(that)f(the)g(netw)o(ork)h (beha)n(vior)g(in)f(the)2006 4081 y(presence)d(of)e(f)o(aults)h(is)f(e) n(v)o(entually)i(correct)f(implicitly)h(in-)2006 4194 y(v)n(olv)o(es)22 b(sho)n(wing)f(that)f(from)g(some)g(point)i(onw)o (ards,)f(the)g(net-)2006 4307 y(w)o(ork)33 b(beha)n(vior)j(is)d(the)h (same)f(as)g(that)g(of)g(some)h(f)o(ault-free)2006 4420 y(computation.)2106 4533 y(Clearly)-6 b(,)20 b(this)e(abstract)i (characterization)j(is)18 b(not)g(amenable)2006 4646 y(for)23 b(designing)i(stabilization.)32 b(W)-7 b(e)22 b(no)n(w)g(discuss)i(a)e(standard)2006 4759 y(tw)o(o-step)j(approach)h (for)e(stabilization)j(design.)2006 4949 y Fh(Step)37 b(1:)58 b(Design)37 b(an)h(in)l(v)o(ariant)p Fi(.)76 b(In)37 b(this)i(step,)j(correct)2006 5062 y(netw)o(ork)28 b(beha)n(vior)i(is)c(characterized)31 b(in)c(the)g(form)g(of)g(a)f(set) 2006 5175 y(of)j(le)o(gitimate)i(states,)g(called)g(an)e Fj(in)l(variant)j Fi(predicate.)48 b(As)1890 5439 y(3)p eop %%Page: 4 4 4 3 bop -150 -29 a Fi(the)24 b(name)f(suggests,)i(an)e(in)l(v)n(ariant) j(is)d(a)g(Boolean)h(condition)-150 84 y(that)31 b(is)f(al)o(w)o(ays)h (true)g(\(in)g(all)f(states)h(of)g(all)f(f)o(ault-free)j(com-)-150 197 y(putations)k(of)d(the)h(netw)o(ork)g(protocols\).)64 b(That)35 b(is,)h(the)f(set)-150 310 y(of)24 b(states)i(denoted)h(by)d (an)h(in)l(v)n(ariant)i(is)d(closed)i(under)g(f)o(ault-)-150 423 y(free)33 b(netw)o(ork)g(e)o(x)o(ecution.)57 b(It)32 b(is)g(important)i(to)e(appreciate)-150 536 y(that)d(man)o(y)f(state)h (predicates)j(\(i.e.)43 b(sets)29 b(of)f(states\))i(that)f(are)-150 649 y(closed)35 b(under)f(f)o(ault-free)i(netw)o(ork)e(e)o(x)o (ecution,)j(e.g.)58 b Fj(true)p Fi(,)-150 762 y Fj(false)p Fi(,)23 b(etc.,)g(are)f(not)h(in)l(v)n(ariants)i(by)d(themselv)o(es.)31 b(An)21 b(in)l(v)n(ari-)-150 875 y(ant)31 b(must)g(contain)i(enough)g (information)g(so)f(that)f(one)h(can)-150 988 y(sho)n(w)25 b(that)i(\223starting)g(from)f Fj(any)g Fi(state)g(in)g(the)g(in)l(v)n (ariant,)i Fj(e)o(v-)-150 1100 y(ery)21 b Fi(f)o(ault-free)j (computation)g(of)d(the)h(netw)o(ork)g(protocol)h(sat-)-150 1213 y(is\002es)h(the)g(speci\002cation\224.)32 b(The)23 b(set)h(of)g(all)g(reachable)i(states)-150 1326 y(in)20 b(all)h(f)o(ault-free)i(computations)h(of)c(a)g(netw)o(ork)i(protocol)h (of-)-150 1439 y(ten)36 b(comprises)h(an)f(in)l(v)n(ariant.)68 b(Or)l(,)38 b(designers)g(can)e(guess)-150 1552 y(predicates)30 b(weak)o(er)d(than)h(the)f(set)g(of)f(reachable)j(states)f(that)-150 1665 y(suf)n(\002ce)c(for)g(correctness)i(reasoning.)-50 1778 y(\(W)-7 b(e)34 b(remark)i(that)g(the)g(demand)g(that)g(the)g(in)l (v)n(ariant)i(be)-150 1891 y(\223complete\224\226in)21 b(the)e(sense)g(that)g(it)e(contains)k(all)d(f)o(acts)h(needed)-150 2004 y(to)26 b(pro)o(v)o(e)h(correctness)j(with)c(respect)i(to)e(the)h (speci\002cation\226)-150 2117 y(is)21 b(nonstandard)k(as)c(well)g(as)g (nontri)n(vial.)31 b(That)21 b(it)g(is)g(nonstan-)-150 2230 y(dard)29 b(has)h(caused)g(confusion,)i(b)n(ut)e(is)e(not)h (serious.)47 b(That)28 b(it)-150 2342 y(is)i(nontri)n(vial)j(is)d(more) g(serious,)k(and)c(we)g(will)g(further)h(dis-)-150 2455 y(cuss)g(this)g(point)h(later)f(on.)49 b(F)o(or)30 b(no)n(w)-6 b(,)31 b(we)f(note)h(that)g(fortu-)-150 2568 y(nately)f(in)l(v)n (ariant-based)j(proofs)e(are)d(often)i(temporally)h(lo-)-150 2681 y(cal:)36 b(safety)28 b(and)f(li)n(v)o(eness)h(properties)i(of)c (the)h(speci\002cation)-150 2794 y(are)e(v)o(eri\002ed)h(by)f (reasoning)j(about)e(indi)n(vidual)i(state)d(transi-)-150 2907 y(tions)f(only)-6 b(,)23 b(thus)g(a)n(v)n(oiding)j(the)d (treacherously)j(long)d(chains)-150 3020 y(of)30 b(state)h(transitions) j(contained)f(in)d(operational)j(proofs)f(of)-150 3133 y(netw)o(ork)25 b(beha)n(vior)-5 b(.\))-150 3323 y Fh(Step)38 b(2:)59 b(Design)39 b(con)l(v)o(er)o(gence)i(to)e(in)l(v)o(ariant)p Fi(.)78 b(In)38 b(this)-150 3436 y(step,)20 b(protocol)g(computations)h (starting)f(from)e(arbitrary)i(states)-150 3549 y(are)30 b(sho)n(wn)h(to)f(con)l(v)o(er)n(ge)j(to)d(some)g(in)l(v)n(ariant)j (state.)50 b(Since)-150 3662 y(the)18 b(in)l(v)n(ariant)j(is)d(closed,) i(once)f(an)f(in)l(v)n(ariant)j(state)e(is)f(reached,)-150 3775 y(protocol)36 b(computations)h(beha)n(v)o(e)e(as)f(f)o(ault-free)i (computa-)-150 3888 y(tions.)f(And)25 b(since)h(an)o(y)g(computation)i (starting)f(from)e(an)h(in-)-150 4001 y(v)n(ariant)32 b(state)g(satis\002es)g(the)g(speci\002cation,)j(it)c(follo)n(ws)g (that)-150 4114 y(correct)i(netw)o(ork)f(beha)n(vior)i(is)d(e)n(v)o (entually)i(restored)h(in)d(all)-150 4226 y(computations)c(starting)e (from)f(arbitrary)h(states.)-50 4339 y(Con)l(v)o(er)n(gence)f(is)d (typically)j(achie)n(v)o(ed)e(by)g(separately)i(de-)-150 4452 y(signing)33 b Fj(detector)o(s)h Fi(\(that)e(establish)i(whether)e (the)g(netw)o(ork)-150 4565 y(is)23 b(in)h(a)e(state)j(where)e(its)h (in)l(v)n(ariant)i(is)d(violated\))j(and)e Fj(corr)m(ec-)-150 4678 y(tor)o(s)30 b Fi(\(that)g(restore)g(the)f(state)h(so)f(as)g(to)g (resatisfy)i(in)l(v)n(ariant\))-150 4791 y([8)q(].)40 b(As)26 b(noted)j(in)e(the)h(pre)n(vious)i(section,)f(during)g(the)f (con-)-150 4904 y(v)o(er)n(gence)22 b(process)g(spreading)h(of)c (corrupted)k(data)e(from)e(one)-150 5017 y(component)28 b(to)d(the)h(other)g(needs)h(to)e(be)g(circumv)o(ented;)30 b(de-)-150 5130 y(tectors)25 b(and)f(correctors)i(suf)n(\002ce)e(for)g (this)g(purpose.)2006 -29 y Fk(4)120 b(Major)29 b (Criticisms/Misconceptions)2186 121 y(About)h(Stabilization)2006 292 y Fi(Computer)19 b(netw)o(orking)i(already)e(has)g(se)n(v)o(eral)g (protocols)i(that)2006 405 y(we)k(re)o(gard)h(as)f(being)i (stabilizing.)37 b(Soon)25 b(after)i(Dijkstra)f(re-)2006 518 y(ported)e(his)f(stabilizing)j(tok)o(en)e(ring)f(protocol)i(in)d (1973)i([10)q(],)2006 631 y(for)d(instance,)i(he)e(became)h(a)o(w)o (are)f(of)g(its)g(implementation)i(in)2006 744 y(a)28 b(Dutch)h(netw)o(ork.)44 b(As)28 b(other)h(e)o(xamples,)h(stateless)h (proto-)2006 857 y(cols)f(such)h(as)e(IP)f(are)i(stabilizing)i(by)e (de\002nition.)48 b(RIP)28 b(and)2006 970 y(OSPF)k(are)j(based)h(on)e (stabilizing)k(protocols;)43 b(the)35 b(former)2006 1083 y(relies)26 b(on)e(Bellman-F)o(ord)h(which)g(is)f(per)g(se)g (stabilizing)k(and)2006 1196 y(the)20 b(latter)h(simply)f(discards)i (its)e(routes)h(periodically)i(and)d(re-)2006 1309 y(computes)26 b(based)f(on)f(fresh)i(state.)31 b(Also,)24 b(se)n(v)o(eral)h (soft-state)2006 1421 y(protocols)33 b(such)e(as)f(ARP/RARP)d(are)j (inherently)j(stabiliz-)2006 1534 y(ing.)2106 1647 y(A)d(seasoned)k (critic)e(might)g(reasonably)j(ar)n(gue)e(that)f(sta-)2006 1760 y(bilization)j(is)c(merely)i(a)e(serendipitous)36 b(property)e(of)d(these)2006 1873 y(protocols,)j(since)d(man)o(y)e (netw)o(orking)j(e)o(xperts)f(are)f(not)g(e)o(x-)2006 1986 y(plicitly)35 b(a)o(w)o(are)d(that)h(these)h(protocols)h(are)e (stabilizing.)59 b(In)2006 2099 y(f)o(act,)20 b(our)g(critic)g(will)e (raise)i(a)e(v)n(ariety)j(of)d(objections)k(to)d(ques-)2006 2212 y(tion)34 b(whether)h(stabilization)i(is,)f(practically)g (speaking,)i(of)2006 2325 y(an)o(y)24 b(v)n(alue)g(to)g(netw)o(orking.) 2006 2551 y Fh(1.)j(What)19 b(good)h(is)f(e)o(v)o(entual)g (satisfaction?)68 b Fi(Stabilization)2006 2663 y(guarantees)38 b(only)e(that)f(after)g(a)g(f)o(ault)g(occurs\226and)j(assum-)2006 2776 y(ing)22 b(no)g(further)h(f)o(aults)g(occur)n(\226the)i(netw)o (ork)d(will)g Fj(e)o(ventually)2006 2889 y Fi(reach)e(a)e(state)i(from) f(where)g(correct)h(operation)h(will)e(resume.)2006 3002 y(Gi)n(v)o(en)33 b(that)h(in)f(an)o(y)g(signi\002cantly)j(sized)f(netw) o(ork,)h(at)d(an)o(y)2006 3115 y(time,)c(some)g(part)f(or)h(the)f (other)h(of)f(the)h(netw)o(ork)g(is)f(subject)2006 3228 y(to)c(a)g(f)o(ault,)h(our)f(critic)h(w)o(ould)g(object)g(that)g(the)f (\223e)n(v)o(entually\224)2006 3341 y(guarantee)i(is)e(too)g(weak)f(to) h(be)f(practical.)2006 3567 y Fh(2.)29 b(Stabilization)c(is)e(not)g(an) g(\223easy\224)i(pr)n(operty)-6 b(.)76 b Fi(The)23 b(sta-)2006 3680 y(bilization)31 b(literature)e(is)f(peppered)i(with)d(enough)j (sophisti-)2006 3793 y(cated,)21 b(comple)o(x)f(algorithms)i(that)e(it) f(is)g(no)n(w)f(a)h(knee-jerk)j(re-)2006 3905 y(action)h(to)e(rele)o (gate)h(judgment)h(of)e(correctness)j(of)e(a)e(freshly-)2006 4018 y(minted)32 b(stabilizing)i(algorithm)e(to)f(a)f(stabilization)k (e)o(xpert.)2006 4131 y(Indeed,)27 b(man)o(y)f(incorrect)h(solutions)h (ha)n(v)o(e)e(been)g(submitted)2006 4244 y(for)34 b(public)h(vie)n(w)-6 b(.)59 b(As)33 b(can)h(be)f(e)o(xpected,)38 b(man)o(y)c(of)f(these)2006 4357 y(contained)24 b(incorrect)g(proofs)e(of)g(con)l(v)o(er)n(gence.) 32 b(What)21 b(is)g(in-)2006 4470 y(teresting,)34 b(then,)e(is)d(that)i (in)f(our)g(e)o(xperience)i(just)f(as)e(man)o(y)2006 4583 y(erroneous)38 b(proofs)f(were)e(due)h(to)f(incorrectly)j (identifying)2006 4696 y(the)28 b(in)l(v)n(ariant)h(or)e(in)g (incorrectly)j(sho)n(wing)e(that)g(the)g(in)l(v)n(ari-)2006 4809 y(ant)37 b(itself)g(w)o(as)f(closed)h(under)h(protocol)g(e)o(x)o (ecution.)69 b(Our)2006 4922 y(critic)27 b(w)o(ould)g(surmise)g(that)g (all)f(this)g(suggests)j(that)d(design-)2006 5035 y(ing)21 b(sound)h(and)g(complete)g(in)l(v)n(ariants)h(of)e(protocols)i(is)e (hard,)2006 5147 y(and)33 b(most)f(protocol)j(designers)g(w)o(ould)e (not)g(\002nd)f(this)h(task)1890 5439 y(4)p eop %%Page: 5 5 5 4 bop -150 -29 a Fi(appealing,)22 b Fj(especially)e(when)f(pr)l (otocols)h(become)f(lar)m(g)o(e)p Fi(.)28 b(Note)-150 84 y(that)k(the)f(designer')-5 b(s)34 b(task)d(increases)j(linearly)f (in)e(the)g(code)-150 197 y(size,)c(at)f(the)g(v)o(ery)g(least,)i(e.g.) 35 b(for)27 b(checking)h(the)e(closure)i(of)-150 310 y(the)c(in)l(v)n(ariant.)-150 536 y Fh(3.)j(Stabilization)22 b(is)f(not)f(a)h(local)g(pr)n(operty)-6 b(.)69 b Fi(While)21 b(stabi-)-150 649 y(lization)k(deals)g(well)e(with)g(arbitrary)j(state) e(perturbations,)j(it)-150 762 y(is)20 b(not)h(al)o(w)o(ays)g(clear)g (ho)n(w)f(well)g(it)g(deals)i(with)e(only)h(\223minor\224)-150 875 y(state)34 b(perturbations.)62 b(Consider)34 b(the)g(problem)g(of)f (routing)-150 988 y(\(or)l(,)41 b(more)c(abstractly)-6 b(,)44 b(spanning)c(tree)d(maintenance\))k(for)-150 1100 y(e)o(xample.)60 b(If)33 b(a)g(root)h(node)h(of)e(a)g(\(sub\)tree)j(f)o (ails,)h(the)c(fol-)-150 1213 y(lo)n(wing)24 b(scenarios)i(are)e (concei)n(v)n(able:)-14 1390 y Fc(\017)46 b Fi(Instead)39 b(of)f(just)f(\002xing)h(the)g(root)g(from)f(among)h(its)77 1503 y(nearby)20 b(nodes,)g(a)e(stabilizing)j(algorithm)f(may)d(choose) 77 1616 y(a)22 b(replacement)j(root)e(that)g(is)f(f)o(ar)h(a)o(w)o(ay) -6 b(,)22 b(and)h(substan-)77 1729 y(tially)30 b(tear)f(do)n(wn)f(the)h (tree)g(so)f(as)g(to)h(reb)n(uild)h(it)e(with)77 1842 y(respect)d(to)f(the)g(ne)n(w)-6 b(,)22 b(distant)k(root.)-14 2006 y Fc(\017)46 b Fi(Unless)21 b(a)g(child)g(of)f(the)h(f)o(ailed)h (root)f(informs)h(all)e(of)h(its)77 2119 y(do)n(wnstream)38 b(nodes)h(before)f(it)e(changes)j(its)e(route,)77 2232 y(a)k(\(potentially)j(long\))d(c)o(ycle)h(in)e(the)h(route)h(can)f(be) 77 2345 y(formed.)i(This)28 b(is)f(because)j(if)e(a)f(distant)j (descendant)77 2458 y(of)19 b(the)h(child)g(is)f(not)h(a)o(w)o(are)f (of)g(the)g(f)o(ailure)i(of)e(the)h(root,)77 2571 y(it)32 b(may)h(of)n(fer)g(to)f(the)h(child)g(an)g(alternati)n(v)o(e)h(\(b)n (ut)g(in-)77 2684 y(correct\))h(route)g(to)e(the)g(root.)59 b(If)33 b(the)h(descendant)i(is)77 2796 y(not)24 b(made)f(a)o(w)o(are)g (of)h(the)f(f)o(ailed)i(root,)e(the)h(child)g(may)77 2909 y(point)d(to)f(the)h(descendant)i(which)d(\(indirectly\))j(points) 77 3022 y(to)h(the)g(child,)g(thereby)h(yielding)h(a)d(c)o(ycle.)-50 3140 y(In)29 b(each)i(of)e(these)i(scenarios,)i(a)d(spatially)i(local)e (pertur)n(-)-150 3253 y(bation)20 b(causes)g(spatially)g(non-local)h (checking)g(or)d(non-local)-150 3366 y(healing.)50 b(Similar)30 b(ar)n(guments)j(could)e(ha)n(v)o(e)g(been)g(made)f(in)-150 3479 y(temporal)d(or)f(ener)n(gy)i(domains.)38 b(In)26 b(other)h(w)o(ords,)g(e)n(v)o(en)f(for)-150 3592 y(a)38 b(minor)h(f)o(ault,)j(which)d(if)f(anticipated)k(could)d(ha)n(v)o(e)g (been)-150 3705 y(dealt)29 b(with)f(via)g(a)f(lo)n(w-cost)i(e)o (xception)i(handler)l(,)f(stabiliza-)-150 3818 y(tion)20 b(yield)h(a)e(high-cost)k(response.)29 b(Our)20 b(critic)g(w)o(ould)h (there-)-150 3931 y(fore)f(ar)n(gue)h(that)f(stabilization)j(is)c(an)h (\223e)o(xpensi)n(v)o(e\224)i(property)-6 b(,)-150 4044 y(since)39 b(it)f(tends)i(to)e(a)n(v)n(oid)i(distinguishing)i (particular)f(per)n(-)-150 4157 y(turbed)25 b(states.)-150 4382 y Fh(4.)46 b(Stabilization)30 b(is)f(not)g(a)g(composable)h(pr)n (operty)-6 b(.)103 b Fi(In)-150 4495 y(contrast)36 b(to)f (stabilization,)40 b(masking)c(of)e(f)o(aults)h(of)n(fers)h(the)-150 4608 y(attracti)n(v)o(e)g(feature)h(of)d(being)i(composable.)65 b(That)34 b(is,)j(if)d(a)-150 4721 y(component)27 b(is)d(wrapped)i(to)e (mask)h(certain)h(f)o(aults,)f(then)h(the)-150 4834 y(wrapped)35 b(v)o(ersion)f(of)g(the)f(component)j(can)e(be)f(\(hot/cold\))-150 4947 y(sw)o(apped)e(with)e(the)h(unwrapped)h(v)o(ersion,)h(without)f (af)n(fect-)-150 5060 y(ing)41 b(the)g(correctness)j(of)c(the)h(o)o(v)o (erall)h(system.)80 b(In)41 b(other)-150 5173 y(w)o(ords,)f(when)d(a)f (component)j(is)d(masking)i(f)o(ault-tolerant,)2006 -29 y(other)29 b(components)i(do)d(not)h(ha)n(v)o(e)g(to)f(deal)h(with)f (an)o(y)g(unan-)2006 84 y(ticipated)i(communications)h(with)c(it,)h (and)h(hence)f(the)g(orig-)2006 197 y(inal)i(reasoning)j(that)d (applied)h(to)f(the)f(system)i(components)2006 310 y(in)25 b(the)h(absence)h(of)e(f)o(aults)h(also)g(applies)h(in)e(the)g (presence)i(of)2006 423 y(f)o(aults.)51 b(In)30 b(general,)k(this)d(is) f(not)h(true)g(of)g(stabilizing)i(com-)2006 536 y(ponents.)45 b(While)28 b(there)h(is)f(e)o(xisting)i(research)g(on)e(compos-)2006 649 y(ing)39 b(stabilizing)j(components)f(in)e(layers,)44 b(in)38 b(serial)i(man-)2006 762 y(ner)l(,)k(and)39 b(in)g(parallel,)45 b(the)39 b(composition)j(techniques)g(are)2006 875 y(ar)n(guably)33 b(limited.)49 b(Components)32 b(in)e(general)i(ha)n(v)o(e)f(to)f(ac-) 2006 988 y(count)24 b(for)f(\223arbitrary\224)i(communications)h(with)d (other)g(com-)2006 1100 y(ponents,)h(and)e(inde\002nite)g(propagation)j (of)c(corruption)j(from)2006 1213 y(the)k(one)g(component)i(to)d (another)i(has)f(to)f(be)h(a)n(v)n(oided.)43 b(Our)2006 1326 y(critic)e(w)o(ould)e(therefore)j(ar)n(gue)f(that)f(stabilization) j(is)c(not)2006 1439 y(readily)25 b(useful)g(for)f(CO)l(TS)e(based)i (systems.)2006 1665 y Fh(5.)46 b(Stabilization)31 b(is)e(not)g(a)g(r)n (e\002nable)g(pr)n(operty)-6 b(.)104 b Fi(Most)2006 1778 y(design)42 b(of)e(stabilization)k(is)c(performed)i(using)g(linguistic) 2006 1891 y(notations)21 b(suitable)f(for)e(abstract)i(protocols,)i (such)d(as)f(guarded)2006 2004 y(commands,)i(communicating)h(\002nite)d (state)h(machines,)i(high-)2006 2117 y(atomicity)j (message-passing/share)q(d)j(memory)22 b(languages.)2006 2230 y(Do)h(the)g(proofs)i(of)e(stabilization)j(continue)g(to)d(remain) g(v)n(alid)2006 2342 y(when)i(the)f(abstract)i(protocol)h(is)d (re\002ned)h(into)g(a)f(C)f(program)2006 2455 y(that)c(uses)g(TCP/UDP)c (sock)o(ets?)29 b(W)-7 b(orse,)19 b(can)g(standard)h(com-)2006 2568 y(pilers)34 b(tak)o(e)f(a)f(stabilizing)j(C-program)f(as)e(input)i (and)f(pro-)2006 2681 y(duce)38 b(object)g(code)f(that)h(violates)g (the)f(property)i(of)e(stabi-)2006 2794 y(lization?)31 b(Our)23 b(critic)g(w)o(ould)h(therefore)h(ar)n(gue)f(that)g(it)e(is)h (un-)2006 2907 y(clear)34 b(that)f(the)g(con\002dence)h(gained)g(by)e (formal)i(reasoning)2006 3020 y(about)29 b(in)l(v)n(ariants)h(and)f (con)l(v)o(er)n(gences)i(at)d(an)f(abstract)j(le)n(v)o(el)2006 3133 y(remains)19 b(once)g(the)g(abstract)h(protocols)g(are)f (re\002ned/compiled)2006 3246 y(into)24 b(their)h(\002nal)e(concrete)j (form.)2006 3538 y Fk(5)120 b(Redr)n(essing)30 b(The)g(Criticisms)2006 3710 y Fi(In)22 b(this)h(section,)h(we)d(respond)k(to)d(each)h(of)f (the)g(objections)j(of)2006 3823 y(our)e(seasoned)i(critic)e(from)f (the)h(v)n(antage)h(point)f(of)f(the)h(state-)2006 3936 y(of-the-art)j(in)e(stabilization)j(research.)2006 4162 y Fh(Response)f(to)g(Criticism)g(1.)35 b Fi(W)-7 b(e)25 b(claim)h(that)g(\223e)n(v)o(entually\224)2006 4274 y(is)35 b(merely)g(a)f(con)l(v)o(enient)k(generalization)h(of)34 b(\223not)i(imme-)2006 4387 y(diately\224.)62 b(Stabilization)36 b(necessarily)h(relies)e(on)f(\223not)h(im-)2006 4500 y(mediately\224)25 b(since)e(otherwise)h(systems)g(must)e(check)h(all)g (the)2006 4613 y(time)h(for)f(unanticipated)28 b(state/beha)n(vior)-5 b(.)33 b(In)23 b(se)n(v)o(eral)h(cases,)2006 4726 y(stabilization)35 b(is)c(indeed)h(achie)n(v)o(ed)h(in)d(constant)j(time,)g(e.g.)2006 4839 y(as)24 b(a)f(constant)i(function)h(of)d(the)h(time)f(periods)j (used)e(in)f(soft-)2006 4952 y(state)31 b(protocols.)52 b(In)30 b(most)g(other)i(cases,)g(it)e(is)g(achie)n(v)o(ed)i(in)2006 5065 y(time)c(that)g(is)g(bounded)i(by)e(a)f(function)j(of)e(certain)h (netw)o(ork)2006 5178 y(parameters,)j(such)d(as)f(de)o(gree,)i (diameter)l(,)h(current)f(number)1890 5439 y(5)p eop %%Page: 6 6 6 5 bop -150 -29 a Fi(of)25 b(nodes,)i(etc.)34 b(Indeed,)27 b(a)d(lot)i(of)f(research)i(in)e(stabilization)-150 84 y(has)g(focused)i(on)e(achie)n(ving)i(stabilization)i(in)24 b(optimal)i(time)-150 197 y(and)e(state)g([11)r(].)-50 310 y(That)18 b(the)g(de\002nition)i(of)e(stabilization)j(has)e(not)f (been)h(amended)-150 423 y(to)24 b(demand)i(bounded)g(con)l(v)o(er)n (gence)i(is)c(simply)h(a)f(matter)h(of)-150 536 y(taste.)55 b(F)o(or)31 b(one,)k(stabilization)g(researchers)g(prefer)f(not)e(to) -150 649 y(o)o(v)o(erspecify)g(the)e(models)h(in)f(which)g(the)o(y)g (sho)n(w)f(stabiliza-)-150 762 y(tion;)35 b(as)c(a)f(result,)k(the)d (property)h(of)f(stabilization)j(is)d(more)-150 875 y(readily)23 b(portable)g(from)e(one)h(model)f(to)g(another)-5 b(.)30 b(By)20 b(w)o(ay)h(of)-150 988 y(contrast,)k(con)l(v)o(er)n(gence)i (bounds)d(are)g(not)f(as)g(readily)h(ported)-150 1100 y(from)c(one)h(model)f(to)g(another)l(,)j(e.g.)k(from)20 b(a)g(shared)i(memory)-150 1213 y(model)27 b(to)g(a)f(bounded-time)k (message)e(passing)h(model.)39 b(As)-150 1326 y(another)20 b(reason,)g(e)n(v)o(en)f(when)f(stabilization)j(time)d(is)g(bounded,) -150 1439 y(simply)27 b(by)f(w)o(aiting)i(for)e(that)h(bounded)h (amount)g(of)e(time,)g(a)-150 1552 y(netw)o(ork)35 b(process)h(cannot)g (deduce)g(that)f(the)f(netw)o(ork)i(has)-150 1665 y(resumed)26 b(correct)g(operation.)34 b(An)24 b(undetectable)k(f)o(ault)d(may)-150 1778 y(ha)n(v)o(e)35 b(occurred)h(during)g(the)f(w)o(ait)f(itself,)k (and)c(all)h(that)g(the)-150 1891 y(process)i(kno)n(ws)e(is)g(that)g (correct)i(operation)g(has)f(resumed)-150 2004 y(only)24 b(if)g(no)f(ne)n(w)g(f)o(aults)i(ha)n(v)o(e)f(occurred.)-150 2230 y Fh(Response)31 b(to)h(Criticism)g(2.)52 b Fi(It)31 b(has)h(no)n(w)f(been)h(well)f(rec-)-150 2342 y(ognized)40 b(that)e(v)o(erifying)i(stabilization)h(is)d(a)f(special)i(case)-150 2455 y(of)30 b(v)o(erifying)i(correctness.)51 b(Indeed,)33 b(closure)f(and)e(con)l(v)o(er)n(-)-150 2568 y(gence)k(are)e(easily)i (captured)h(in)d(v)n(arious)i(temporal)g(logics,)-150 2681 y(such)k(as)e(Chandy)i(and)f(Misra')-5 b(s)38 b(UNITY)d(and)i (Lamport')-5 b(s)-150 2794 y(TLA.)19 b(Lamport)i(and)h(others)g(ha)n(v) o(e)g(sho)n(wn)f(mechanical)j(v)o(er)n(-)-150 2907 y(i\002cations)35 b(of)f(stabilizing)j(protocols,)i(and)34 b(in)g(the)g(process)-150 3020 y(also)22 b(sho)n(wn)g(that)g(no)g(ne)n(w)e(techniques)25 b(are)d(in)l(v)n(olv)o(ed.)30 b(Thus,)-150 3133 y(we)h(can)i(at)e (least)i(observ)o(e)h(that)e(v)o(erifying)i(stabilization)i(is)-150 3246 y(no)24 b(harder)h(than)f(v)o(erifying)h(protocol)h(correctness.) -50 3359 y(W)-7 b(e)19 b(no)n(w)h(turn)h(to)f(the)h(practicality)j(of)c (including)j(correct-)-150 3472 y(ness)e(properties)i(in)d(the)g (design)i(task,)f(in)f(particular)l(,)j(the)d(cal-)-150 3584 y(culation)k(of)e(an)g(in)l(v)n(ariant)j(and)d(the)h(proof)g(of)f (closure)i(of)d(and)-150 3697 y(con)l(v)o(er)n(gence)41 b(to)36 b(the)h(in)l(v)n(ariant.)71 b(Recent)37 b(w)o(ork)g(in)g (stabi-)-150 3810 y(lization)h(has)f(focused)h(on)f(simplifying)h(this) f(task)g(in)g(se)n(v-)-150 3923 y(eral)e(dimensions:)54 b(\(i\))35 b(Con)l(v)o(er)n(gence)j(of)c Fj(e)o(very)h Fi(computa-)-150 4036 y(tion)g(from)f Fj(e)o(very)g Fi(state)h(is)f (weak)o(ened)i(to)e(con)l(v)o(er)n(gence)k(of)-150 4149 y Fj(some)d Fi(computations)j(from)e Fj(some)f Fi(states)h([13)q(].)64 b(The)34 b(\002rst)-150 4262 y(weak)o(ening)d(still)f(suf)n(\002ces)g (to)f(sho)n(w)g(that)h(con)l(v)o(er)n(gence)j(oc-)-150 4375 y(curs)e(with)f(high)i(probability)h(and)e(the)g(second)h(weak)o (ening)-150 4488 y(a)n(v)n(oids)25 b(consideration)i(of)d(highly)g (unlik)o(ely)i(states.)k(\(ii\))23 b(The)-150 4601 y(in)l(v)n(ariant)38 b(is)e(calculated)i(based)f(not)f(on)g(the)g(protocol)i(b)n(ut)-150 4714 y(based)e(on)f(the)g(speci\002cation)j(that)e(the)f(protocol)i (satis\002es,)-150 4826 y(under)32 b(the)f(assumption)j(that)d(the)h (speci\002cation)h(is)e(signi\002-)-150 4939 y(cantly)h(smaller)f(than) g(the)f(protocol)j([6].)49 b(This)30 b(weak)o(ening)-150 5052 y(is)37 b(sound)h(in)f(the)g(sense)h(that)f(the)g(speci\002cation) i(in)l(v)n(ariant)-150 5165 y(must)34 b(be)f(satis\002ed)i(by)e(the)h (protocol,)k(albeit)d(the)f(protocol)2006 -29 y(might)29 b(satisfy)i(some)e(additional)i(state)f(predicates)i(as)c(well)2006 84 y(in)i(its)g(le)o(gitimate)i(states.)50 b(\(iii\))30 b(F)o(or)f(similar)i(reasons,)i(con-)2006 197 y(v)o(er)n(gence)i(to)e (an)g(in)l(v)n(ariant)i(is)d(weak)o(ened)j(to)d(con)l(v)o(er)n(gence) 2006 310 y(to)h(a)e(partial)j(in)l(v)n(ariant,)j(in)32 b(which)h(only)g(some)f(b)n(ut)h(not)g(all)2006 423 y(aspects)c(of)d (netw)o(ork)i(state)g(that)f(are)g(necessary)j(for)d(correct)2006 536 y(beha)n(vior)f(are)e(guaranteed)j(to)c(be)h(satis\002ed.)2006 762 y Fh(Response)32 b(to)g(Criticism)g(3.)54 b Fi(Recent)32 b(research)i(has)e(care-)2006 875 y(fully)e(in)l(v)o(estigated)h(the)e (e)o(xtent)g(to)f(which)h(problems)h(admit)2006 988 y(local)25 b(\223containment\224.)34 b(By)24 b(maximizing)h(the)g(de)o(gree)g(of)f (lo-)2006 1100 y(cal)h(containment,)i(it)d(is)g(possible)i(to)f(\(a\))f (limit)g(the)h(e)o(xtent)g(to)2006 1213 y(which)32 b(a)f(local)h (perturbation)j(af)n(fects)d(the)g(rest)g(of)f(the)h(net-)2006 1326 y(w)o(ork)e(and)g(\(b\))f(limit)h(the)f(amount)h(of)g(w)o(ork)f (that)h(has)g(to)f(be)2006 1439 y(done)24 b(to)f(stabilize)i(the)e (netw)o(ork)h(once)g(a)f(local)h(perturbation)2006 1552 y(occurs)h([19)q(].)2106 1665 y(By)31 b(w)o(ay)g(of)h(e)o(xample,)j (consider)f(f)o(air)e(resource)i(alloca-)2006 1778 y(tion,)20 b(a)d(problem)j(which)e(can)h(be)f(solv)o(ed)h(using)g(dining)h (philoso-)2006 1891 y(phers.)62 b(This)33 b(problem)j(admits)e(a)g (stabilizing)j(solution)f(in)2006 2004 y(which)26 b(e)n(v)o(ery)g(node) g(depends)h(only)f(on)g(nodes)g(in)f(its)h(neigh-)2006 2117 y(borhood)31 b(that)e(are)f(at)g(a)g(distance)i(of)f(at)f(most)g (2)g(hops)h(from)2006 2230 y(it.)72 b(Thus,)42 b(it)37 b(can)i(be)f(sho)n(wn)g([19)q(],)j(in)d(the)g(spirit)h(of)f(\(a\),)2006 2342 y(that)24 b(a)f(misbeha)n(ving)k(node)d(\(e)n(v)o(en)g(a)f (Byzantine)j(node\))f(can-)2006 2455 y(not)j(af)n(fect)f(nodes)i(that)e (are)g(more)g(than)h(2)f(hops)h(a)o(w)o(ay)e(from)2006 2568 y(it.)49 b(Moreo)o(v)o(er)l(,)33 b(in)d(the)h(spirit)g(of)g (\(b\),)h(that)f(if)f(a)g(node)h(is)f(lo-)2006 2681 y(cally)e (perturbed)h(into)f(an)e(incorrect)j(state,)g(then)e(as)g(long)g(as) 2006 2794 y(it)32 b(has)g(no)g(misbeha)n(ving)i(nodes)f(at)f(a)f (distance)j(of)e(at)f(most)2006 2907 y(2)j(hops)i(from)e(it,)j(the)d (node)i(e)n(v)o(entually)g(con)l(v)o(er)n(ges)i(to)c(lo-)2006 3020 y(cally)23 b(correct)g(beha)n(vior)-5 b(.)30 b(This)22 b(e)o(xample)g(is)f(remarkable)j(be-)2006 3133 y(cause)i(node)f (stabilization)k(is)24 b(achie)n(v)o(ed)i(in)f(the)g(presence)h(of)2006 3246 y(Byzantine)f(f)o(aults)f(on)e(nodes.)30 b(\(W)-7 b(e)22 b(mak)o(e)h(this)g(point)h(to)f(dis-)2006 3359 y(pel)c(the)f(myth)g(that)h(masking)g(tolerance\226and)j(not)d (stabilization\226)2006 3472 y(is)h(the)h(only)g(rele)n(v)n(ant)h (tolerance)g(with)e(respect)i(to)e(Byzantine)2006 3584 y(f)o(aults.\))2106 3697 y(F)o(or)39 b(problems)i(that)f(are)g (inherently)i(non-local,)k(other)2006 3810 y(research)39 b([25)q(])d(has)h(alternati)n(v)o(ely)j(considered)g(\(i\))d(chang-) 2006 3923 y(ing)31 b(the)g(netw)o(ork)h(model)f(so)f(that)i(local)f (solutions)i(are)e(ad-)2006 4036 y(mitted)26 b(and)g(\(ii\))g (approximating)i(the)e(problems)h(so)e(that)h(lo-)2006 4149 y(cal)i(solutions)j(are)d(admitted.)44 b(By)27 b(w)o(ay)h(of)g(e)o (xample)h(of)e(\(i\),)2006 4262 y(by)j(assuming)i(that)f(wireless)g (communication)i(is)d(possible)2006 4375 y(\(whereby)j(all)e(neighbors) i(of)e(a)g(node)g(can)h(recei)n(v)o(e)g(a)e(com-)2006 4488 y(munication)f(from)c(it)h(at)g(about)h(the)f(same)g(time\))g(or)g (that)h(the)2006 4601 y(density)c(of)d(neighbors)k(in)c(the)h(netw)o (ork)h(is)f(high,)g(it)g(becomes)2006 4714 y(possible)32 b(to)d(achie)n(v)o(e)i(local)f(stabilization)j(for)d(routing)h(tree) 2006 4826 y(maintenance,)h(despite)e(the)e(dif)n(\002culties)j (mentioned)f(in)e(the)2006 4939 y(pre)n(vious)39 b(section.)69 b(As)36 b(an)h(e)o(xample)g(of)g(\(ii\),)i(in)e(the)g(dis-)2006 5052 y(trib)n(uted)28 b(node)f(cluster)g(formation)h(problem,)f(where)f (nodes)2006 5165 y(locally)c(group)g(themselv)o(es)g(into)f(internally) i(connected)g(and)1890 5439 y(6)p eop %%Page: 7 7 7 6 bop -150 -29 a Fi(mutually)28 b(disjoint)h(clusters,)g(demanding)g (that)f(e)n(v)o(ery)f(clus-)-150 84 y(ter)j(has)g(some)g(constant)i (number)f(of)f(nodes)h(or)f(some)g(con-)-150 197 y(stant)g(radius)h (yields)f(only)g(non-local)i(solutions;)j(ho)n(we)n(v)o(er)l(,)-150 310 y(if)d(we)f(weak)o(en)i(the)f(number/radius)j(to)d(some)g (appropriate)-150 423 y(interv)n(al,)25 b(local)f(solutions)i(are)e (achie)n(v)n(able.)-150 649 y Fh(Response)c(to)g(Criticism)g(4.)27 b Fi(W)-7 b(e)20 b(note)g(that)h(recent)g(research)-150 762 y(is)30 b(e)o(xtending)i(composition)g(methods)f(be)o(yond)g(the)f (princi-)-150 875 y(ples)35 b(of)f(layering,)39 b(sequential/phased)h (con)l(v)o(er)n(gence,)g(and)-150 988 y(parallel)c(con)l(v)o(er)n (gence.)66 b(The)34 b(basic)h(idea)g(is)g(to)f(deal)h(with)-150 1100 y(spreading)h(of)d(corruptions)j(from)e(one)f(component)j(to)d (an-)-150 1213 y(other)42 b(in)e(each)h(and)g(e)n(v)o(ery)g(of)g(the)g (follo)n(wing)h(w)o(ays:)63 b(\(i\))-150 1326 y(through)28 b(method)f(in)l(v)n(ocation)i(with)d(corrupted)i(ar)n(guments,)-150 1439 y(\(ii\))21 b(through)i(recei)n(ving)g(corrupted)g(result)f(ar)n (guments)h(in)e(re-)-150 1552 y(sponses)i(to)e(method)i(in)l(v)n (ocations,)i(and)d(\(iii\))f(through)j(viola-)-150 1665 y(tion)g(of)g(component)h(rely/guarantee)j(contracts.)-50 1778 y(The)19 b(technique)k(for)d(dealing)i(with)e(the)g(spreading)j (of)d(cor)n(-)-150 1891 y(ruption)27 b(in)d(between)i(components)h(is)e (to)f(a)h(posteriori)i(wrap)-150 2004 y(components,)40 b(with)35 b(special)h(purpose)h(stabilization)i(com-)-150 2117 y(ponents)26 b(called)f(detectors)g(and)g(correctors)h([8)q(].)i (Moreo)o(v)o(er)l(,)-150 2230 y(the)18 b(speed)i(of)e(e)o(x)o(ecuting)i (detectors)g(and)f(correctors)i(is)d(tuned)-150 2342 y(with)j(respect)h(to)f(the)g(spare)h(resources)h(a)n(v)n(ailable)g(in) e(the)g(sys-)-150 2455 y(tem)38 b(and)g(in)g(proportion)k(to)c(the)g (frequenc)o(y)i(and)f(locality)-150 2568 y(of)27 b(perturbations.)44 b(Detectors)29 b(and)e(correctors)j(themselv)o(es)-150 2681 y(are)i(more)h(easily)g(de)n(v)o(eloped)h(from)e(a)g(reusable)i (library)g(of)-150 2794 y(pattern-speci\002c)22 b(component)e (templates)g([4,)d(22)q(,)g(21)q(,)g(5)q(,)g(16)q(].)-150 2907 y(In)22 b(some)g(cases,)h(the)f(ar)n(guments)j(with)d(which)g(to)g (instantiate)-150 3020 y(the)29 b(detector)i(and)e(corrector)j (templates)e(can)f(be)g(automati-)-150 3133 y(cally)24 b(synthesized)j(gi)n(v)o(en)d(component)i(speci\002cations.)-150 3359 y Fh(Response)40 b(to)g(Criticism)h(5.)79 b Fi(Recent)41 b(research)h(has)f(fo-)-150 3472 y(cused)31 b(on)f(de)n(v)o(eloping)j (re\002nement)e(techniques)i(and)d(com-)-150 3584 y(pilers)36 b(that)f(preserv)o(e)h(stabilization)i(properties)f([9)q(,)c(2)q(,)g (18)q(,)-150 3697 y(17)q(].)28 b(The)22 b(Austin)h(APC)d(compiler)l(,) 25 b(for)d(e)o(xample,)h(compiles)-150 3810 y(stabilizing)35 b(code)d(from)g(the)g(AP)e(\(Abstract)j(Protocol\))h(no-)-150 3923 y(tation)h(into)g(C-code)g(that)f(use)h(UDP)d(sock)o(et)j (communica-)-150 4036 y(tions)27 b(while)g(preserving)i(certain)f (stabilization)i(properties.)-150 4149 y(Initial)g(steps)g(are)e(being) i(made)f(to)n(w)o(ards)g(making)h(standard)-150 4262 y(compilers)22 b(stabilization)h(preserving,)g(and)e(to)n(w)o(ards)f (adding)-150 4375 y(stabilization)37 b(properties)g(to)d(operating)i (systems)f(and)f(vir)n(-)-150 4488 y(tual)39 b(machines.)75 b(In)39 b(particular)l(,)45 b(this)39 b(research)i(direction)-150 4601 y(has)28 b(led)f(to)h(consideration)j(of)c(stabilization)32 b(in)27 b(\(sequential)-150 4714 y(or)d(distrib)n(uted\))j(data)d (types,)h(in)f(contrast)h(to)f(pre)n(vious)i(w)o(ork)-150 4826 y(which)e(has)g(focused)h(more)f(on)f(distrib)n(uted)k(control.) 2006 -29 y Fk(6)120 b(Practical)30 b(Stabilization)2006 143 y Fi(While)25 b(research)i(on)d(stabilization)k(is)d(progressing)j (well)c(to-)2006 256 y(w)o(ards)e(simplifying)j(its)c(use)i(and)f (increasing)i(its)e(applicabil-)2006 369 y(ity)-6 b(,)33 b(netw)o(ork)o(ed)f(system)f(designers)j(can)c(already)j(le)n(v)o (erage)2006 482 y(most)e(of)f(the)g(bene\002ts)i(of)e(stabilization)k (through)e(practical)2006 595 y(approximations.)59 b(W)-7 b(e)32 b(summarize)h(here)g(techniques)j(that)2006 707 y(are)27 b(inspired)h(by)e(stabilization,)31 b(which)26 b(the)h(interested)i(net-)2006 820 y(w)o(ork)24 b(system)g(designer)i (should)f(consider)-5 b(.)2006 1046 y Fh(1.)37 b(Ensur)n(e)26 b(con)l(v)o(er)o(gence)j(to)d(partial)h(in)l(v)o(ariants.)127 b Fi(Not)2006 1159 y(all)18 b(parts)h(of)f(the)h(in)l(v)n(ariant)h(are) f(equally)h(important)f(for)g(achie)n(v-)2006 1272 y(ing)28 b(rob)n(ustness)j(of)c(a)g(netw)o(ork)i(protocol.)43 b(In)27 b(dealing)i(with)2006 1385 y(unanticipated)k(f)o(aults,)f(it)d (is)g(therefore)i(more)e(important)i(or)2006 1498 y(more)26 b(ef)n(\002cient)h(to)e(deal)i(with)e(just)h(the)g(central)i(parts)e (of)g(the)2006 1611 y(in)l(v)n(ariant.)36 b(So,)24 b(ensuring)k(con)l (v)o(er)n(gence)h(just)c(to)g(these)h(parts)2006 1724 y(should)20 b(be)e(v)n(aluable.)29 b(Design)19 b(ef)n(fort)g(should)h (be)e(spent)h(more)2006 1837 y(on)29 b(ensuring)h(that)f(the)g(chosen)h (parts)f(are)g(sound)h(\(i.e.)43 b(the)o(y)2006 1949 y(are)27 b(closed)h(under)g(netw)o(ork)f(e)o(x)o(ecution\))i(than)e(on) g(ensuring)2006 2062 y(that)d(the)g(chosen)h(in)l(v)n(ariant)h(is)e (complete.)2006 2288 y Fh(2.)60 b(Use)34 b(model-based)g(or)g (speci\002cation-based)i(in)l(v)o(ari-)2006 2401 y(ants.)98 b Fi(As)22 b(a)f(heuristic,)k(the)d(central)i(parts)e(of)g(the)h(in)l (v)n(ariant)2006 2514 y(are)c(lik)o(ely)i(to)e(be)g(predicates)j(that)d (can)h(be)f(deduced)i(from)e(ab-)2006 2627 y(stract)27 b(models)f(of)g(the)g(protocol)i(or)d(from)h(its)g(speci\002cation.) 2006 2740 y(In)j(other)h(w)o(ords,)g(these)g(parts)f(may)g(not)g(be)g (speci\002c)g(to)g(the)2006 2853 y(details)i(of)d(the)h(protocol)i (implementation.)47 b(Since)29 b(models)2006 2966 y(and)22 b(speci\002cations)j(can)d(be)g(signi\002cantly)i(smaller)f(than)f(the) 2006 3079 y(protocol)35 b(code,)h(deducing)f(partial)g(in)l(v)n (ariants)g(from)e(them)2006 3191 y(should)25 b(be)f(used)g(when)g (possible.)2006 3417 y Fh(3.)40 b(Ensur)n(e)27 b(weak)f(f)n(orms)i(of)f (con)l(v)o(er)o(gence.)96 b Fi(Just)28 b(as)f(not)2006 3530 y(all)35 b(states)g(\(predicates\))j(are)c(equally)i(lik)o(ely)g (to)e(occur)i(un-)2006 3643 y(der)e(corruption,)40 b(not)34 b(all)g(protocol)i(computations)h(from)d(a)2006 3756 y(gi)n(v)o(en)25 b(state)f(are)h(equally)g(lik)o(ely)h(either)-5 b(.)31 b(Thus)24 b(stabilization)2006 3869 y(should)34 b(be)f(enforced)i(\002rst)d(with)g(respect)i(to)f(\223reasonable\224) 2006 3982 y(computations.)73 b(F)o(or)37 b(e)o(xample,)k(in)c (computations)k(which)2006 4095 y(are)32 b(taking)g(too)g(long)g(to)f (con)l(v)o(er)n(gence,)37 b(it)31 b(may)g(be)h(appro-)2006 4208 y(priate)e(to)f(abandon)i(the)e(attempt)h(to)f(stabilize.)47 b(Often,)30 b(this)2006 4321 y(may)23 b(be)h(justi\002ed)g(by)g(taking) h(into)f(account)h(the)f(probability)2006 4433 y(of)g(that)g (computation.)2006 4659 y Fh(4.)64 b(Design)35 b(lo)o(w-cost)h (stabilization.)134 b Fi(Since)36 b(unantici-)2006 4772 y(pated)28 b(f)o(aults)f(should)h(be)e(the)h(e)o(xception)h(and)f(not)g (the)f(norm)2006 4885 y(in)k(an)o(y)h(netw)o(ork)o(ed)h(system,)g (stabilization)i(should)e(not)e(in-)2006 4998 y(v)n(olv)o(e)35 b(high-cost)i(support.)62 b(Only)34 b(non-critical)j(resources)2006 5111 y(should)i(be)f(allocated)i(to)e(stabilization,)44 b(whereas)39 b(critical)1890 5439 y(7)p eop %%Page: 8 8 8 7 bop -150 -29 a Fi(resources)27 b(may)d(be)h(allocated)i(to)d(deal)h (with)g(common-case)-150 84 y(anticipated)f(f)o(aults.)29 b(More)21 b(generally)-6 b(,)23 b(stabilization)h(should)-150 197 y(not)e(interfere)i(with)e(support)i(for)e(anticipated)j(f)o (aults,)f(as)d(dis-)-150 310 y(cussed)30 b(in)f([6)q(],)g(which)g (described)i(a)d(technique)k(that)d(stabi-)-150 423 y(lizes)g(to)f(a)g (weak)o(er)h(in)l(v)n(ariant)h(that)f(includes)h(the)f(ef)n(fects)g(of) -150 536 y(e)o(x)o(ecuting)c(the)f(common-case)i(f)o(aults.)-150 762 y Fh(5.)36 b(Use)26 b(patter)o(n-speci\002c)g(templates)h(f)n(or)f (designing)g(sta-)-150 875 y(bilization.)173 b Fi(T)-7 b(o)31 b(increase)j(the)e(con\002dence)j(in)d(the)g(cor)n(-)-150 988 y(rectness)f(of)d(the)h(detectors/correctors)34 b(used)c(for)e (stabiliza-)-150 1100 y(tion,)44 b(standard)d(patterns)h(should)f(be)f (used)g(where)g(possi-)-150 1213 y(ble.)63 b(Man)o(y)34 b(such)i(patterns)h(ha)n(v)o(e)e(been)h(discussed)h(in)e(the)-150 1326 y(literature,)e(e.g.)45 b(for)30 b(global)g(snapshot,)j(for)c (distrib)n(uted)k(re-)-150 1439 y(set,)d(for)g(constraint-based)k (satisf)o(action)f(of)c(in)l(v)n(ariants,)k(for)-150 1552 y(distrib)n(uted)h(cleaning,)h(etc.)51 b(Assuming)32 b(that)f(stabilization)-150 1665 y(is)f(attempted)i(with)e(lo)n(w)f (frequenc)o(y)-6 b(,)34 b(a)c(slight)i(loss)e(of)h(ef)n(\002-)-150 1778 y(cienc)o(y)d(that)f(may)g(result)h(as)f(compared)i(with)d (hand-crafted)-150 1891 y(detectors/corrector)q(s)j(might)24 b(still)g(be)f(w)o(orthwhile.)-150 2117 y Fh(Ackno)o(wledgements)p Fi(.)132 b(Man)o(y)35 b(colleagues)j(ha)n(v)o(e)e(in\003u-)-150 2230 y(enced)22 b(the)f(vie)n(ws)g(re\003ected)h(in)f(this)g(position)i (paper)-5 b(.)29 b(In)21 b(par)n(-)-150 2342 y(ticular)l(,)34 b(we)29 b(thank)j(Marvin)f(Theimer)l(,)h(Mohamed)g(Gouda,)-150 2455 y(and)24 b(T)-6 b(ed)23 b(Herman.)-150 2748 y Fk(Refer)n(ences) -105 2955 y Fi([1])47 b(A)-10 b(T&T)45 b(f)o(ailure)k(of)e(January)j (15,)j(1990.)111 b Fb(http:)47 3068 y(//www.cs.berkel)o(ey)o(.e)o(du)o (/\230)o(nik)o(it)o(ab)o(/)47 3181 y(courses/cs294-)t(8)o(/h)o(w1)o (.ht)o(ml)o Fi(.)-105 3368 y([2])47 b(A.)g(Arora,)55 b(M.)47 b(Demirbas,)55 b(and)49 b(S.)e(S.)g(K)o(ulkarni.)47 3481 y(Graybox)28 b(stabilization.)49 b Fj(Pr)l(oceedings)29 b(of)e(the)h(Inter)n(-)47 3594 y(national)23 b(Confer)m(ence)f(on)f (Dependable)i(Systems)e(and)47 3707 y(Networks)p Fi(,)j(pages)h (389\226398,)g(July)f(2001.)-105 3895 y([3])47 b(A.)33 b(Arora)i(and)h(M.)d(G.)h(Gouda.)70 b(Closure)36 b(and)f(con-)47 4008 y(v)o(er)n(gence:)30 b(A)21 b(foundation)j(of)d(f)o(ault-tolerant) 26 b(comput-)47 4121 y(ing.)65 b Fj(IEEE)32 b(T)-5 b(r)o(ansactions)36 b(on)d(Softwar)m(e)i(Engineer)n(-)47 4233 y(ing)p Fi(,)24 b(19\(11\):1015\2261027,)29 b(1993.)-105 4421 y([4])47 b(A.)34 b(Arora)i(and)g(M.)f(G.)f(Gouda.)73 b(Distrib)n(uted)38 b(reset.)47 4534 y Fj(IEEE)c(T)-5 b(r)o(ansactions)39 b(on)e(Computer)o(s)p Fi(,)j(43\(9\):1026\226)47 4647 y(1038,)24 b(1994.)-105 4835 y([5])47 b(A.)26 b(Arora,)j(M.)d(G.)g (Gouda,)j(and)f(G.)f(V)-10 b(ar)n(ghese.)48 b(Con-)47 4947 y(straint)32 b(satisf)o(action)i(as)c(a)g(basis)h(for)g(designing) i(non-)47 5060 y(masking)d(f)o(ault-tolerance.)55 b Fj(J)n(ournal)30 b(of)f(High)g(Speed)47 5173 y(Networks)p Fi(,)24 b(5\(3\):293\226306,)j (1996.)2052 -29 y([6])46 b(A.)55 b(Arora,)65 b(R.)54 b(Jagannathan,)68 b(and)57 b(Y)-12 b(.)55 b(M.W)-7 b(ang.)2203 84 y(Model-based)60 b(design)f(of)e(dependability)k(in)d(dis-)2203 197 y(trib)n(uted)35 b(systems.)63 b Fj(Pr)l(oceedings)35 b(of)d(the)h(W)-8 b(orkshop)2203 310 y(on)42 b(Concurr)m(ency)i(in)e (Distrib)n(uted)i(Systems)p Fi(,)j(pages)2203 423 y(61\22668,)25 b(2001.)2052 611 y([7])46 b(A.)28 b(Arora)h(and)g(S.)e(S.)g(K)o (ulkarni.)52 b(Component)30 b(based)2203 723 y(design)42 b(of)f(multitolerant)i(systems.)88 b Fj(IEEE)39 b(T)-5 b(r)o(ans-)2203 836 y(actions)40 b(on)f(Softwar)m(e)g(Engineering)p Fi(,)45 b(24\(1\):63\22678,)2203 949 y(January)26 b(1998.)2052 1137 y([8])46 b(A.)25 b(Arora)i(and)h(S.)d(S.)g(K)o(ulkarni.)45 b(Detectors)28 b(and)f(cor)n(-)2203 1250 y(rectors:)36 b(A)25 b(theory)i(of)f(f)o(ault-tolerance)31 b(components.)2203 1363 y Fj(International)48 b(Confer)m(ence)d(on)f(Distrib)n(uted)i (Com-)2203 1476 y(puting)25 b(Systems)p Fi(,)g(pages)f(436\226443,)i (May)d(1998.)2052 1663 y([9])46 b(M.)40 b(Demirbas)h(and)g(A.)e(Arora.) 88 b(Con)l(v)o(er)n(gence)44 b(re-)2203 1776 y(\002nement.)146 b Fj(Pr)l(oceedings)62 b(of)c(the)h(International)2203 1889 y(Confer)m(ence)43 b(on)e(Distrib)n(uted)j(Computing)e(Systems) 2203 2002 y(\(ICDCS\))p Fi(,)23 b(July)h(2002.)2006 2190 y([10])47 b(E.)28 b(W)-8 b(.)27 b(Dijkstra.)52 b(Self-stabilizing)33 b(systems)d(in)f(spite)2203 2303 y(of)38 b(distrib)n(uted)k(control.)83 b Fj(Communications)41 b(of)d(the)2203 2415 y(A)m(CM)p Fi(,)22 b(17\(11\),)j(1974.)2006 2603 y([11])47 b(S.)28 b(Dole)n(v)-6 b(.)54 b Fj(Self-Stabilization)p Fi(.)59 b(MIT)29 b(Press,)i(March)2203 2716 y(2000.)j(ISBN)22 b(0-262-04178-2.)2006 2904 y([12])47 b(M.)36 b(Flatebo,)41 b(A.)35 b(K.)h(Datta,)k(and)d(S.)f(Ghosh.)76 b(Self-)2203 3017 y(stabilization)47 b(in)c(distrib)n(uted)k(systems.)98 b(In)43 b Fj(Read-)2203 3129 y(ings)i(in)f(Distrib)n(uted)i(Computing)f (Systems)p Fi(,)50 b(chap-)2203 3242 y(ter)38 b(2,)j(pages)e (100\226114.)h(IEEE)c(Computer)j(Society)2203 3355 y(Press,)23 b(1994.)31 b(TL)21 b(Casa)n(v)n(ant)j(and)f(M)e(Singal,)i(Editors.)2006 3543 y([13])47 b(M.G.)29 b(Gouda.)57 b(The)31 b(theory)h(of)f(weak)g (stabilization.)2203 3656 y(In)c Fj(WSS01)g(Pr)l(oceedings)i(of)d(the)h (F)l(ifth)f(International)2203 3769 y(W)-8 b(orkshop)36 b(on)f(Self-Stabilizing)k(Systems,)f(Spring)o(er)2203 3882 y(LNCS:2194)p Fi(,)24 b(pages)h(114\226123,)g(2001.)2006 4069 y([14])47 b(T)-7 b(.)60 b(Herman.)154 b(Self-stabilization)66 b(bibliography:)2203 4182 y(Access)39 b(guide.)81 b(Chicago)40 b(Journal)g(of)e(Theoretical)2203 4295 y(Computer)44 b(Science,)k(W)-7 b(orking)44 b(P)o(aper)f(WP-1,)k(ini-)2203 4408 y(tiated)20 b(No)o(v)o(ember)g(1996,)g(last)g(re)n(vised)g (January)h(2001.)2203 4521 y(http://www)-6 b(.cs.uio)n(w)o (a.edu/ftp/selfs)q(tab)q(/b)q(ibl)q(iog)q(rap)q(hy/)q(.)2006 4709 y([15])47 b(M.)24 b(Jayaram)i(and)f(G.)f(V)-10 b(ar)n(ghese.)39 b(Crash)25 b(f)o(ailures)i(can)2203 4821 y(dri)n(v)o(e)20 b(protocols)j(to)d(arbitrary)i(states.)27 b Fj(Pr)l(oceedings)22 b(of)2203 4934 y(the)g(F)l(ifteenth)g(Annual)g(A)m(CM)e(Symposium)i(on) f(Princi-)2203 5047 y(ples)35 b(of)e(Distrib)n(uted)k(Computing)p Fi(,)g(pages)e(247\226256,)2203 5160 y(1996.)1890 5439 y(8)p eop %%Page: 9 9 9 8 bop -150 -29 a Fi([16])47 b(S.)31 b(Katz)i(and)g(K.)e(J.)h(Perry)-6 b(.)63 b(Self-stabilizing)37 b(e)o(xten-)47 84 y(sions)32 b(for)e(message-passing)35 b(systems.)57 b Fj(Distrib)n(uted)47 197 y(Computing)p Fi(,)24 b(7:17\22626,)i(1993.)-150 385 y([17])47 b(T)-7 b(.M.)76 b(McGuire)i(and)h(M.G.)d(Gouda.)208 b(Cor)n(-)47 498 y(rect)136 b(implementation)j(of)d(netw)o(ork)h(pro-) 47 611 y(tocols)195 b(from)e(abstract)i(speci\002cations.)47 723 y(http://www)-6 b(.cs.ute)o(xas.edu/users/)q(mcgu)q(ire)q(/res)q (ea)q(rch)q(/.)-150 911 y([18])47 b(M.)h(Nesterenk)o(o)k(and)e(A.)e (Arora.)117 b(Stabilization-)47 1024 y(preserving)53 b(atomicity)e(re\002nement.)119 b(In)50 b Fj(DISC99)47 1137 y(Distrib)n(uted)36 b(Computing)f(13th)g(International)j(Sym-)47 1250 y(posium,)46 b(Spring)o(er)d(LNCS:1693)p Fi(,)j(pages)c (254\226268,)47 1363 y(1999.)-150 1550 y([19])47 b(M.)36 b(Nesterenk)o(o)k(and)e(A.)e(Arora.)78 b(Local)38 b(tolerance)47 1663 y(to)33 b(unbounded)k(byzantine)e(f)o(aults.)66 b(In)33 b Fj(Pr)l(oceedings)47 1776 y(of)40 b(the)h(21st)g(IEEE)d (Symposium)k(on)f(Reliable)g(Dis-)47 1889 y(trib)n(uted)26 b(Systems)e(\(SRDS\))p Fi(,)f(2002.)-150 2077 y([20])47 b(M.)25 b(Schneider)-5 b(.)45 b(Self-stabilization.)i Fj(A)m(CM)25 b(Comput-)47 2190 y(ing)f(Surve)m(ys)p Fi(,)h (25:45\22667,)h(1993.)-150 2377 y([21])47 b(G.)22 b(V)-10 b(ar)n(ghese.)36 b Fj(Self-stabilization)29 b(by)24 b(local)h(c)o(hec)n (king)47 2490 y(and)33 b(corr)m(ection)p Fi(.)63 b(PhD)31 b(thesis,)k(MIT/LCS/TR-583,)47 2603 y(1993.)-150 2791 y([22])47 b(G.)24 b(V)-10 b(ar)n(ghese.)41 b(Self-stabilization)30 b(by)25 b(counter)j(\003ush-)47 2904 y(ing.)58 b(In)30 b Fj(PODC94)g(Pr)l(oceedings)k(of)d(the)g(Thirteenth)47 3017 y(Annual)37 b(A)m(CM)e(Symposium)j(on)e(Principles)j(of)d(Dis-)47 3129 y(trib)n(uted)26 b(Computing)p Fi(,)e(pages)h(244\226253,)h(1994.) -150 3317 y([23])47 b(Y)-12 b(.)22 b(M.)g(W)-7 b(ang,)23 b(W)-8 b(.)21 b(Russell,)j(and)g(A.)e(Arora.)32 b(A)22 b(toolkit)47 3430 y(for)d(b)n(uilding)i(dependable)i(and)c(e)o (xtensible)i(home)e(net-)47 3543 y(w)o(orking)36 b(applications.)73 b Fj(Pr)l(oc.)34 b(USENIX)f(W)-5 b(indows)47 3656 y(Systems)24 b(Symposium)p Fi(,)h(pages)g(101\226112,)g(2000.)-150 3843 y([24])47 b(Y)-12 b(.-M.)34 b(W)-7 b(ang,)39 b(W)-8 b(.)34 b(Russell,)40 b(A.)34 b(Arora,)39 b(J.)c(Xu,)i(and)47 3956 y(R.)26 b(Jagannathan.)49 b(T)-7 b(o)n(w)o(ards)27 b(dependable)k(home)c(net-)47 4069 y(w)o(orking:)62 b(An)39 b(e)o(xperience)j(report.)86 b Fj(International)47 4182 y(Confer)m(ence)52 b(on)e(Dependable)i(Systems)f(and)f(Net-)47 4295 y(works)24 b(\(ICDSN\))p Fi(,)e(2000.)-150 4483 y([25])47 b(H.)40 b(Zhang)j(and)f(A.)e(Arora.)93 b(Gs)1179 4450 y Fa(3)1218 4483 y Fi(:)65 b(Scalable)43 b(self-)47 4596 y(con\002guration)k(and)e(self-healing)i(in)d(wireless)h(net-)47 4709 y(w)o(orks.)67 b(In)34 b Fj(21st)h(A)m(CM)e(Symposium)i(on)f (Principles)47 4821 y(of)23 b(Distrib)n(uted)j(Computing)p Fi(,)f(July)f(2002.)1890 5439 y(9)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF --------------BE6B3BE9422290BF20B8AA17--