Self-stabilization by local checking and correction

The first self-stabilizing end-to-end communication protocol and the most efficient known self-stabilizing network reset protocol are introduced. A simple method of local checking and correction, by which distributed protocols can be made self-stabilizing without the use of unbounded counters, is used. The self-stabilization model distinguishes between catastrophic faults that abstract arbitrary corruption of global state, and other restricted kinds of anticipated faults. It is assumed that after the execution starts there are no further catastrophic faults, but the anticipated faults may continue to occur.<<ETX>>

• Publication year

  1991

• Venue

  [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science

• Publication date

  1991-09-01

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1109/SFCS.1991.185378
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Uniform self-stabilizing leader election

  1993cited by this paper
• Closure and Convergence: A Foundation of Fault-Tolerant Computing

  1993cited by this paper
• Distributed program checking: a paradigm for building self-stabilizing distributed protocols

  1991cited by this paper
• Bootstrap network resynchronization (extended abstract)

  1991cited by this paper
• Stabilizing Communication Protocols

  1991cited by this paper
• Decomposing graphs into regions of small diameter

  1991cited by this paper
• Self-Stabilization By Local Checking and Correction (Extended Abstract)

  1991cited by this paper
• Resource bounds for self stabilizing message driven protocols

  1991cited by this paper
• Using mappings to prove timing properties

  1990cited by this paper
• Sparse partitions

  1990cited by this paper
• Self-stabilization of dynamic systems assuming only read/write atomicity

  1990cited by this paper
• A dining philosophers algorithm with polynomial response time

  1990cited by this paper
• Token management schemes and random walks yield self-stabilizing mutual exclusion

  1990cited by this paper
• Shortest paths and loop-free routing in dynamic networks

  1990cited by this paper
• Self-stabilizing extensions for message-passing systems

  1990cited by this paper
• Distributed Reset (Extended Abstract)

  1990cited by this paper
• Network decomposition and locality in distributed computation

  1989cited by this paper
• Completing the Temporal Picture

  1989cited by this paper
• An Introduction to Input/Output Automata

  1989cited by this paper
• A unified approach to loop-free routing using distance vectors or link states

  1989cited by this paper
• Efficient dispersal of information for security, load balancing, and fault tolerance

  1989cited by this paper
• Self-stabilization of the alternating-bit protocol

  1989cited by this paper
• Network layer protocols with Byzantine robustness

  1988cited by this paper
• Dynamic networks are as fast as static networks

  1988cited by this paper
• On the effects of feedback in dynamic network protocols

  1988cited by this paper
• Uniform self-stabilizing rings

  1988cited by this paper
• End-to-end communication in unreliable networks

  1988cited by this paper
• Reliable communication on data links

  1988cited by this paper
• Parallel symmetry-breaking in sparse graphs

  1987cited by this paper
• Applying static network protocols to dynamic networks

  1987cited by this paper
• Broadcasting Topology Information in Computer Networks

  1987cited by this paper
• A new approach to the maximum flow problem

  1986cited by this paper
• Reliable broadcast protocols in unreliable networks

  1986cited by this paper
• Complexity of network synchronization

  1985cited by this paper
• An algorithm for distributed computation of a spanningtree in an extended LAN

  1985cited by this paper
• Solved problems, unsolved problems and non-problems in concurrency

  1985cited by this paper
• A Distributed Algorithm for Minimum-Weight Spanning Trees

  1983cited by this paper
• Fault-Tolerant Broadcast of Routing Information

  1983cited by this paper
• Specifying Concurrent Program Modules

  1983cited by this paper
• The Byzantine Generals Problem

  1982cited by this paper
• Proving Liveness Properties of Concurrent Programs

  1982cited by this paper
• Vulnerabilities of network control protocols: an example

  1981cited by this paper
• On the advantages of free choice: a symmetric and fully distributed solution to the dining philosophers problem

  1981cited by this paper
• The New Routing Algorithm for the ARPANET

  1980cited by this paper
• Resynch Procedures and a Fail-Safe Network Protocol

  1979cited by this paper
• The Theory of Error-Correcting Codes

  1977cited by this paper
• Self stabilization in spite of distributed control

  1974cited by this paper
• Self-stabilizing systems in spite of distributed control

  1974cited by this paper
• A note on reliable full-duplex transmission over half-duplex links

  1969cited by this paper
• EXTENDED ABSTRACT Abstract

  year unknowncited by this paper

• Being Efficient in Time, Space, and Workload: a Self-Stabilizing Unison and Its Consequences

  2025cites this paper
• Asynchronous Self-stabilization Made Fast, Simple, and Energy-efficient

  2024cites this paper
• Fully Local Succinct Distributed Arguments

  2024cites this paper
• Making local algorithms efficiently self-stabilizing in arbitrary asynchronous environments

  2023cites this paper
• Verification and Synthesis of Responsive Symmetric Uni-Rings

  2022cites this paper
• Testability and local certification of monotone properties in minor-closed classes

  2022cites this paper
• Locally Restricted Proof Labeling Schemes (Full Version)

  2022cites this paper
• Local Mending

  2021cites this paper
• Local certification of graphs on surfaces

  2021cites this paper
• A Meta-Theorem for Distributed Certification

  2021cites this paper
• Extending Lattice linearity for Self-Stabilizing Algorithms

  2021cites this paper
• A Snap-Stabilizing m-wave Algorithm for Tree Networks

  2020cites this paper
• Twenty-Two New Approximate Proof Labeling Schemes

  2020influential citation
• Stabilization, Safety, and Security of Distributed Systems: 22nd International Symposium, SSS 2020, Austin, TX, USA, November 18–21, 2020, Proceedings

  2020cites this paper
• Compact Distributed Certification of Planar Graphs

  2020cites this paper
• Reactive Pls for Distributed Decision

  2020cites this paper
• Self-Stabilizing Automatic Repeat Request Algorithms for (Bounded Capacity, Omitting, Duplicating and non-FIFO) Computer Networks

  2020cites this paper
• Distributed Quantum Proofs for Replicated Data

  2020cites this paper
• Structural Information and Communication Complexity: 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29–July 1, 2020, Proceedings

  2020cites this paper
• Invited Paper: Reactive PLS for Distributed Decision

  2020cites this paper
• Local Certification of Graphs with Bounded Genus

  2020cites this paper
• Reactive Proof Labeling Schemes for Distributed Decision

  2020cites this paper
• Distributed Testing of Distance-k Colorings

  2020cites this paper
• Efficient Self-Stabilizing Leader Election ( Full Version ) ∗

  2020cites this paper
• Introduction to Distributed Self-Stabilizing Algorithms

  2019cites this paper
• Verification and Synthesis of Symmetric Uni-Rings for Leads-To Properties

  2019cites this paper
• Reducing the Number of Messages in Self-stabilizing Protocols

  2019cites this paper
• Self-Stabilizing Distributed Cooperative Reset

  2019cites this paper
• Protocol Implementation Certification Agent Error P 0 Protocol Implementation Certification Agent Error P 1 Protocol Implementation Certification Agent Error P 3 External Input / Output Internal Messages Protocol Implementation Certification Agent Error P 2 Protocol Implementation Certification Agen

  2019cites this paper
• Chasing Minimal Inductive Validity Cores in Hardware Model Checking

  2019influential citation
• Self-stabilizing Connected Components

  2019cites this paper
• An open modal stabilizing m-wave algorithm for arbitrary networks

  2019cites this paper
• Topology-Specific Synthesis of Self-Stabilizing Parameterized Systems with Constant-Space Processes

  2019cites this paper
• Certifying Safety when Implementing Consensus

  2019cites this paper
• Local checkability, no strings attached: (A)cyclicity, reachability, loop free updates in SDNs

  2018cites this paper
• Redundancy in distributed proofs

  2018cites this paper
• Message-Efficient Self-stabilizing Transformer Using Snap-Stabilizing Quiescence Detection

  2018cites this paper
• Brief Announcement: Space-Optimal Naming in Population Protocols

  2018cites this paper
• Brief Announcement: Time Efficient Self-stabilizing Stable Marriage

  2018cites this paper
• Local certification in distributed computing: error-sensitivity, uniformity, redundancy, and interactivity. (Certification locale en calcul distribué : sensibilité aux erreurs, uniformité, redondance et interactivité)

  2018cites this paper
• Proof-Labeling Schemes: Broadcast, Unicast and in Between

  2017cites this paper
• An optimal adaptive stabilizing algorithm for two edge-disjoint paths problem

  2017cites this paper
• A Stabilizing Algorithm for Finding Two Node-Disjoint Paths in Arbitrary Networks

  2017cites this paper
• Fundamentals of Software Engineering

  2017cites this paper
• Synthesizing Parameterized Self-stabilizing Rings with Constant-Space Processes

  2017cites this paper
• Approximate Proof-Labeling Schemes

  2017cites this paper
• An adaptive stabilizing imposter detection scheme for distributed mobile wireless sensor networks

  2017cites this paper
• Shadow/Puppet Synthesis: A Stepwise Method for the Design of Self-Stabilization

  2016cites this paper
• Specification-Based Design of Self-Stabilization

  2016cites this paper
• Space-Time Tradeoffs for Distributed Verification

  2016cites this paper
• Survey of Distributed Decision

  2016cites this paper
• Local checkability, no strings attached

  2016cites this paper
• Brief Announcement: Space-Time Tradeoffs for Distributed Verification

  2016cites this paper
• Announcement : Space-Time Tradeoffs for Distributed Verification

  2016cites this paper
• On the Limits and Practice of Automatically Designing Self-Stabilization

  2016cites this paper
• An optimal inherently stabilizing routing algorithm for star P2P overlay networks

  2016cites this paper
• Ground Control to Major Faults: Towards a Fault Tolerant and Adaptive SDN Control Network

  2016cites this paper
• On the Hardness of Adding Nonmasking Fault Tolerance

  2015cites this paper
• Anonymous distributed computing: computability, randomization and checkability

  2015cites this paper
• Randomized proof-labeling schemes

  2015cites this paper
• Space-Optimal Time-Efficient Silent Self-Stabilizing Constructions of Constrained Spanning Trees

  2015cites this paper
• A Theory of Integrating Tamper Evidence with Stabilization

  2015cites this paper
• Stabilization, Safety, and Security of Distributed Systems

  2014influential citation
• SKIP+: A Self-Stabilizing Skip Graph

  2014cites this paper
• Polynomial-Time Space-Optimal Silent Self-Stabilizing Minimum-Degree Spanning Tree Construction

  2014cites this paper
• Etude de la fiabilité des algorithmes self-convergeants face aux soft-erreurs

  2014cites this paper
• Synthesizing Self-stabilization through Superposition and Backtracking

  2014cites this paper
• Snap-Stabilizing PIF on Non-oriented Trees and Message Passing Model

  2014cites this paper
• Scalable fault-containing self-stabilization in dynamic networks

  2014cites this paper
• préparée au sein du Laboratoire TIMA dans l'École Doctorale d'Électronique, Électrotechnique, Automatique, et Traitement du Signal (EEATS)

  2014cites this paper
• Principles of Distributed Computing

  2014cites this paper
• The Opinion Number of Set-Agreement

  2014cites this paper
• Towards a complexity theory for local distributed computing

  2013cites this paper
• Tight Bounds for Distributed Minimum-Weight Spanning Tree Verification

  2013cites this paper
• On the Complexity of Adding Convergence

  2013cites this paper
• Self-stabilizing silent disjunction in an anonymous network

  2013cites this paper
• Local Decision and Verification with Bounded-Size Outputs

  2013cites this paper
• Ideal stabilisation

  2013cites this paper
• Distributed Verification Using Mobile Agents

  2013cites this paper
• A compositional framework for designing self-stabilizing distributed algorithms

  2013cites this paper
• On the Impact of Identifiers on Local Decision

  2012cites this paper
• Automated design of self-stabilization

  2012influential citation
• Tiara: A self-stabilizing deterministic skip list and skip graph

  2012cites this paper
• Self-stabilizing End-to-End Communication in (Bounded Capacity, Omitting, Duplicating and non-FIFO) Dynamic Networks - (Extended Abstract)

  2012cites this paper
• Distributed transactional memory for general networks

  2012cites this paper
• Swarm Synthesis of Convergence for Symmetric Protocols

  2012cites this paper
• Randomized distributed decision

  2012cites this paper
• Local Reasoning for Global Convergence of Parameterized Rings

  2012cites this paper
• Ideal Stabilization 197 Ideal Stabilization Mikhail Nesterenko

  2012cites this paper
• Self-Stabilization in the Distributed Systems of Finite State Machines

  2012cites this paper
• Lightweight Methods for Automated Design of Self-Stabilization

  2011cites this paper
• Locality and checkability in wait-free computing

  2011cites this paper
• A self-stabilizing transformer for population protocols with covering

  2011cites this paper
• Stabilizing consensus with the power of two choices

  2011cites this paper
• Fast and compact self-stabilizing verification, computation, and fault detection of an MST

  2011influential citation
• A Lightweight Method for Automated Design of Convergence

  2011cites this paper
• Distributed Decision Problems: The Locality Angle

  2011cites this paper
• Feasibility of Stepwise Design of Multitolerant Programs

  2011cites this paper
• Reliable Self-Stabilizing Communication for Quasi Rendezvous

  2010cites this paper
• Towards an Extensible Framework for Automated Design of Self-Stabilization

  2010cites this paper