Automatically assigned DDC number: 00436

Manually assigned DDC number: 00462

Number of references: 8

Title: Self-Stabilization by Local Checking and Global Reset (Extended Abstract)

Subject: Self-Stabilization by Local Checking and Global Reset (Extended Abstract)

Description: Baruch Awerbuch 12 , Boaz Patt-Shamir 2 , George Varghese 3 and Shlomi Dolev 45 1 Dept. of Computer Science, Johns Hopkins University 2 Lab. for Computer Science, MIT 3 Dept. of Computer Science, Washington University 4 Dept. of Computer Science, Texas A&M University 5 School of Computer Science, Carleton University Abstract. We describe a method for transforming asynchronous network protocols into protocols that can sustain any transient fault, i.e., become self-stabilizing. We combine the known notion of local checking with a new notion of internal reset, and prove that given any self-stabilizing internal reset protocol, any locally-checkable protocol can be made self-stabilizing. Our proof is constructive in the sense that we provide explicit code. The method applies to many practical network problems, including spanning tree construction, topology update, and virtual circuit setup. 1 Introduction A network protocol is called self-stabilizing (or stabilizing for sho...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1996-03-07

Pubyear: 1994

Format: ps

Identifier: http://citeseer.ist.psu.edu/174409.html

Source: http://www.ccrc.wustl.edu/~varghese/PAPERS/wdag94.ps.Z

Language: en

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/124582.html"   Type="article"   CiteSeer_Book="IEEE   Transactions   on   Computers"   CiteSeer_Volume="43"   Title="Distributed   Reset,">

            <identifier   Org="ISBN:0070087113"   Paper_ID="/124582.html"   Extracted="0070087113"   DDC="621.381/52"   Normalized_DDC="62138152"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0262041782"   Paper_ID="/124582.html"   Extracted="0262041782"   DDC="005.1/4"   Normalized_DDC="00514"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0471719765"   Paper_ID="/124582.html"   Extracted="0471719765"   DDC="621.3821"   Normalized_DDC="6213821"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0818624477"   Paper_ID="/124582.html"   Extracted="0818624477"   />

            <identifier   Org="ISBN:0818628650"   Paper_ID="/124582.html"   Extracted="0818628650"   />

            <identifier   Org="ISBN:1584885645"   Paper_ID="/124582.html"   Extracted="1584885645"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:354000355X"   Paper_ID="/124582.html"   Extracted="354000355X"   DDC="004.6/5"   Normalized_DDC="00465"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540240586"   Paper_ID="/124582.html"   Extracted="3540240586"   DDC="005.3"   Normalized_DDC="0053"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540260323"   Paper_ID="/124582.html"   Extracted="3540260323"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540291636"   Paper_ID="/124582.html"   Extracted="3540291636"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540490183"   Paper_ID="/124582.html"   Extracted="3540490183"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540540997"   Paper_ID="/124582.html"   Extracted="3540540997"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540584498"   Paper_ID="/124582.html"   Extracted="3540584498"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540602747"   Paper_ID="/124582.html"   Extracted="3540602747"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540751416"   Paper_ID="/124582.html"   Extracted="3540751416"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540774432"   Paper_ID="/124582.html"   Extracted="3540774432"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540893342"   Paper_ID="/124582.html"   Extracted="3540893342"   />

            <identifier   Org="ISBN:9051992408"   Paper_ID="/124582.html"   Extracted="9051992408"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.06666666666666667"   />

      </rec>

      <rec   ID="/322105.html"   Type="inproceedings"   CiteSeer_Book="ACM   Symposium   on   Theory   of   Computing"   CiteSeer_Volume=""   Title="Time   Optimal   Self-Stabilizing   Synchronization   (Extended   Abstract),">

            <identifier   Org="ISBN:0897915917"   Paper_ID="/322105.html"   Extracted="0897915917"   />

            <identifier   Org="ISBN:3540260323"   Paper_ID="/322105.html"   Extracted="3540260323"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="1.0"   />

      </rec>

      <rec   ID="/98046.html"   Type="inproceedings"   CiteSeer_Book="IEEE   Symposium   on   Foundations   of   Computer   Science"   CiteSeer_Volume=""   Title="Self-Stabilization   By   Local   Checking   and   Correction   (Extended   Abstract),">

            <identifier   Org="ISBN:0818624477"   Paper_ID="/98046.html"   Extracted="0818624477"   />

            <identifier   Org="ISBN:3540287000"   Paper_ID="/98046.html"   Extracted="3540287000"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.5"   />

            <identifier   Org="ISBN:3540490183"   Paper_ID="/98046.html"   Extracted="3540490183"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.5"   />

            <identifier   Org="ISBN:3540922946"   Paper_ID="/98046.html"   Extracted="3540922946"   />

      </rec>

      <rec   ID="/362183.html"   Type="inproceedings"   CiteSeer_Book="Symposium   on   Principles   of   Distributed   Computing"   CiteSeer_Volume=""   Title="Memory-Efficient   and   Self-Stabilizing   Network   {RESET}   (Extended   Abstract),"   />

      <rec   ID="/341686.html"   Type="inproceedings"   CiteSeer_Book="Symposium   on   Principles   of   Distributed   Computing"   CiteSeer_Volume=""   Title="Resource   Bounds   for   Self   Stabilizing   Message   Driven   Protocols,">

            <identifier   Org="ISBN:0262024128"   Paper_ID="/341686.html"   Extracted="0262024128"   DDC="005.2"   Normalized_DDC="0052"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0262041782"   Paper_ID="/341686.html"   Extracted="0262041782"   DDC="005.1/4"   Normalized_DDC="00514"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0818624477"   Paper_ID="/341686.html"   Extracted="0818624477"   />

            <identifier   Org="ISBN:0897914392"   Paper_ID="/341686.html"   Extracted="0897914392"   DDC="004.36"   Normalized_DDC="00436"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0897915119"   Paper_ID="/341686.html"   Extracted="0897915119"   />

            <identifier   Org="ISBN:0897916131"   Paper_ID="/341686.html"   Extracted="0897916131"   DDC="004.36"   Normalized_DDC="00436"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0897918002"   Paper_ID="/341686.html"   Extracted="0897918002"   DDC="004.36"   Normalized_DDC="00436"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:1594543968"   Paper_ID="/341686.html"   Extracted="1594543968"   DDC="621.382/1"   Normalized_DDC="6213821"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540000739"   Paper_ID="/341686.html"   Extracted="3540000739"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540572716"   Paper_ID="/341686.html"   Extracted="3540572716"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:354058434X"   Paper_ID="/341686.html"   Extracted="354058434X"   DDC="511.8"   Normalized_DDC="5118"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540584498"   Paper_ID="/341686.html"   Extracted="3540584498"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540751416"   Paper_ID="/341686.html"   Extracted="3540751416"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.09090909090909091"   />

      </rec>

      <rec   ID="/110177.html"   Type="inproceedings"   CiteSeer_Book="CONCUR   2nd   International   Conference   on   Concurrency   Theory"   CiteSeer_Volume=""   Title="Time-Constrained   Automata,">

            <identifier   Org="ISBN:0780318552"   Paper_ID="/110177.html"   Extracted="0780318552"   />

            <identifier   Org="ISBN:0780338014"   Paper_ID="/110177.html"   Extracted="0780338014"   />

            <identifier   Org="ISBN:0792391675"   Paper_ID="/110177.html"   Extracted="0792391675"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0818631953"   Paper_ID="/110177.html"   Extracted="0818631953"   />

            <identifier   Org="ISBN:0818666005"   Paper_ID="/110177.html"   Extracted="0818666005"   />

            <identifier   Org="ISBN:0818674482"   Paper_ID="/110177.html"   Extracted="0818674482"   DDC="004/.33"   Normalized_DDC="00433"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:140207025X"   Paper_ID="/110177.html"   Extracted="140207025X"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540309462"   Paper_ID="/110177.html"   Extracted="3540309462"   DDC="003/.3"   Normalized_DDC="0033"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:354044307X"   Paper_ID="/110177.html"   Extracted="354044307X"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540558225"   Paper_ID="/110177.html"   Extracted="3540558225"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540561889"   Paper_ID="/110177.html"   Extracted="3540561889"   DDC="004/.36/015118"   Normalized_DDC="00436015118"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540581790"   Paper_ID="/110177.html"   Extracted="3540581790"   DDC="004.2/4/015113"   Normalized_DDC="00424015113"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540582010"   Paper_ID="/110177.html"   Extracted="3540582010"   DDC="001.64"   Normalized_DDC="00164"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:354062600X"   Paper_ID="/110177.html"   Extracted="354062600X"   DDC="004.1/9"   Normalized_DDC="00419"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540662022"   Paper_ID="/110177.html"   Extracted="3540662022"   DDC="004.24"   Normalized_DDC="00424"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:354085360X"   Paper_ID="/110177.html"   Extracted="354085360X"   DDC="681"   Normalized_DDC="681"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:8173194904"   Paper_ID="/110177.html"   Extracted="8173194904"   />

      </rec>

      <rec   ID="/520491.html"   Type="inproceedings"   CiteSeer_Book="Proceedings   of   13th   ACM   Symposium   on   Operating   Systems   Principles"   CiteSeer_Volume=""   Title="Automatic   reconfiguration   in   {Autonet},">

            <identifier   Org="ISBN:0201624273"   Paper_ID="/520491.html"   Extracted="0201624273"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:0769501435"   Paper_ID="/520491.html"   Extracted="0769501435"   />

            <identifier   Org="ISBN:0780372417"   Paper_ID="/520491.html"   Extracted="0780372417"   />

            <identifier   Org="ISBN:0780379748"   Paper_ID="/520491.html"   Extracted="0780379748"   />

            <identifier   Org="ISBN:0792377117"   Paper_ID="/520491.html"   Extracted="0792377117"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:0818637706"   Paper_ID="/520491.html"   Extracted="0818637706"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:0818671238"   Paper_ID="/520491.html"   Extracted="0818671238"   />

            <identifier   Org="ISBN:0818677430"   Paper_ID="/520491.html"   Extracted="0818677430"   />

            <identifier   Org="ISBN:0818678348"   Paper_ID="/520491.html"   Extracted="0818678348"   DDC="005.4/3"   Normalized_DDC="00543"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:0897914953"   Paper_ID="/520491.html"   Extracted="0897914953"   />

            <identifier   Org="ISBN:0897918908"   Paper_ID="/520491.html"   Extracted="0897918908"   />

            <identifier   Org="ISBN:1880446669"   Paper_ID="/520491.html"   Extracted="1880446669"   />

            <identifier   Org="ISBN:1880446677"   Paper_ID="/520491.html"   Extracted="1880446677"   />

            <identifier   Org="ISBN:3540241299"   Paper_ID="/520491.html"   Extracted="3540241299"   DDC="004.1/1"   Normalized_DDC="00411"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540678794"   Paper_ID="/520491.html"   Extracted="3540678794"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:8126509627"   Paper_ID="/520491.html"   Extracted="8126509627"   />

      </rec>

      <rec   ID="/181129.html"   Type="inproceedings"   CiteSeer_Book="Symposium   on   Principles   of   Distributed   Computing"   CiteSeer_Volume=""   Title="Self-Stabilization   by   Counter   Flushing,">

            <identifier   Org="ISBN:0262041782"   Paper_ID="/181129.html"   Extracted="0262041782"   DDC="005.1/4"   Normalized_DDC="00514"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0769507409"   Paper_ID="/181129.html"   Extracted="0769507409"   />

            <identifier   Org="ISBN:0780320182"   Paper_ID="/181129.html"   Extracted="0780320182"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0780332563"   Paper_ID="/181129.html"   Extracted="0780332563"   />

            <identifier   Org="ISBN:078033874X"   Paper_ID="/181129.html"   Extracted="078033874X"   />

            <identifier   Org="ISBN:0818655720"   Paper_ID="/181129.html"   Extracted="0818655720"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0897918002"   Paper_ID="/181129.html"   Extracted="0897918002"   DDC="004.36"   Normalized_DDC="00436"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:1581135874"   Paper_ID="/181129.html"   Extracted="1581135874"   DDC="004.165"   Normalized_DDC="004165"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:1581137087"   Paper_ID="/181129.html"   Extracted="1581137087"   />

            <identifier   Org="ISBN:3540241280"   Paper_ID="/181129.html"   Extracted="3540241280"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540260323"   Paper_ID="/181129.html"   Extracted="3540260323"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540426051"   Paper_ID="/181129.html"   Extracted="3540426051"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540440496"   Paper_ID="/181129.html"   Extracted="3540440496"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540584498"   Paper_ID="/181129.html"   Extracted="3540584498"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540602747"   Paper_ID="/181129.html"   Extracted="3540602747"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.09090909090909091"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Self-Stabilization   by   Local   Checking   and   Global   Reset   (Extended   Abstract)">

            <identifier   Org="ISBN:3540584498"   Paper_ID="SELF"   Extracted="3540584498"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="1.0"   />

      </rec>

</references_metadata>