Self-stabilization
communication networkslegal tasklocalitymessage passingprocessorsqueuessafe configurationsself-stabilizationshared memorytransientsTuring machines
Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Deterministic network models in operations research (90B10) Communication networks in operations research (90B18) Queues and service in operations research (90B22) Reliability, availability, maintenance, inspection in operations research (90B25) Research exposition (monographs, survey articles) pertaining to systems and control theory (93-02) Control/observation systems involving computers (process control, etc.) (93C83) Stabilization of systems by feedback (93D15)
This book considers algorithms operating on (possibly distributed) communication networks. A set of processors which can communicate between each other is such that delivery is asynchronous and associated queues have to be added to the model, leading to a configuration with states of processors and associated queues. Computational steps are applied to the configuration. The analogy to the equilibrium point of a dynamical system is the set of ``safe configurations with respect to a legal task, meaning that an algorithm applied to the configuration corresponds to a legal execution. An algorithm will be self-stabilizing for a legal task if every fair execution of the algorithm reaches a safe configuration with respect to the legal task. Self-stabilization is motivated by the occurrence of errors and crashes as a way to recover from them.NEWLINENEWLINENEWLINEThe issue of algorithm conversion between different contexts is analysed (between shared memory and message passing or between a centralized and decentralized configuration for instance). The problem of converting nonstabilizing algorithms to self-stabilizing ones is studied. More conservative situations are analyzed, like when a processor fights against other processors so that they cannot reach their goal. In some cases the nefarious influence cannot be eliminated, but if it occurs in a transitory way then things look better. Locality is an important aspect for a good self-stabilizing algorithm: if a limited number of faults occurs, the repair mechanism should not be global. A chapter focuses on computation for Turing machines.
- Empire of colonies: Self-stabilizing and self-organizing distributed algorithm
- Rapid almost-complete broadcasting in faulty networks
- A geometric approach to deploying robot swarms
- Quasi-self-stabilization of a distributed system assuming read/write atomicity
- Stabilizing mobile philosophers
- A belated proof of self-stabilization
- On the costs of self-stabilization
- An exercise in proving self-stabilization with a variant function
- Binary self-stabilization in distributed systems
- Self-stabilizing extensions for message-passing systems
- Self-stabilization over unreliable communication media
- The local detection paradigm and its applications to self-stabilization
- Stability of long-lived consensus.
- Self-stabilization of circular arrays of automata
- Elements of security: Closure, convergence, and protection
- Available stabilizing heaps
- A silent self-stabilizing algorithm for the generalized minimal k-dominating set problem
- A self-stabilizing algorithm for b-matching
- Limiting behavior of 3-color excitable media on arbitrary graphs
- Practically-self-stabilizing virtual synchrony
- Compact routing messages in self-healing trees
- Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
- Optimal self-stabilizing synchronous mobile Byzantine-tolerant atomic register
- Gradual stabilization under \(\tau \)-dynamics
- Self-stabilizing repeated balls-into-bins
- Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative
- A state-based model of sensor protocols
- Coordination without communication: the case of the flocking problem
- A self-stabilizing algorithm for the center-finding problem assuming read/write separate atomicity
- Self-stabilization with path algebra
- Self-stabilizing timestamps
- Probabilistic verification of Herman's self-stabilisation algorithm
- Three tokens in Herman's algorithm
- Stabilizing data-link over non-FIFO channels with optimal fault-resilience
- Coupling and self-stabilization
- Parallel composition for time-to-fault adaptive stabilization
- Transient fault detectors
- Fault-containing self-stabilizing distributed protocols
- HyperTree for self-stabilizing peer-to-peer systems
- When consensus meets self-stabilization
- Studies on algorithms for self-stabilizing communication protocols
- From distributed coordination to field calculus and aggregate computing
- Constructing self-stabilizing oscillators in population protocols
- Self-stabilization through the lens of game theory
- Optimized silent self-stabilizing scheme for tree-based constructions
- Distributed backup placement
- Local mending
- Optimal self-stabilizing mobile Byzantine-tolerant regular register with bounded timestamps
- The epigenetic consensus problem
- A divide \& conquer approach to conditional stable model checking
- Synthesizing optimal bias in randomized self-stabilization
- \textit{Renaissance}: a self-stabilizing distributed SDN control plane using in-band communications
- Self-stabilizing gathering of mobile robots under crash or Byzantine faults
- A note on the parallel runtime of self-stabilizing graph linearization
- Practically stabilizing SWMR atomic memory in message-passing systems
- Ascending runs in dependent uniformly distributed random variables: application to wireless networks
- The first fully polynomial stabilizing algorithm for BFS tree construction
- Computing fault-containment times of self-stabilizing algorithms using lumped Markov chains
- Safe and stabilizing distributed multi-path cellular flows
- Distributed agreement in dynamic peer-to-peer networks
- A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs
- Synchronization of finite-state pulse-coupled oscillators
- Self-stabilizing smoothing and balancing networks
- Distributed edge coloration for bipartite networks
- The Theta-Model: achieving synchrony without clocks
- A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks
- Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler
- An anonymous self-stabilizing algorithm for 1-maximal independent set in trees
- The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs
- A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives
- A self-stabilizing algorithm for finding weighted centroid in trees
- Efficient self-stabilizing algorithms for minimal total \(k\)-dominating sets in graphs
- Explorative anytime local search for distributed constraint optimization
- Self-stabilizing defeat status computation: dealing with conflict management in multi-agent systems
- A self-stabilizing algorithm for the shortest path problem assuming read/write atomicity
- Competitive self-stabilizing \(k\)-clustering
- Certification of an exact worst-case self-stabilization time
- Location functions for self-stabilizing Byzantine tolerant swarms
- Self-stabilizing and private distributed shared atomic memory in seldomly fair message passing networks
- scientific article; zbMATH DE number 1696640 (Why is no real title available?)
- scientific article; zbMATH DE number 1696676 (Why is no real title available?)
- Stability of multi-valued continuous consensus
- Magnifying computing gaps. Establishing encrypted communication over unidirectional channels
- Lost in self-stabilization
- Weak vs. self vs. probabilistic stabilization
- On the complexity of adding convergence
- Effective search for a naval mine with application to distributed failure detection
- The optimal strategy for the average long-lived consensus
- On stabilization in Herman's algorithm
- Oblivious Collaboration
- Self-stabilizing computation of 3-edge-connected components
- Global synchronization of pulse-coupled oscillators on trees
- Self-Stabilizing Domination Algorithms
- A mathematical modeling framework for software reliability testing†
- Type-based self-stabilisation for computational fields
- A self-stabilizing algorithm for the st-order problem
- On the Performance of Beauquier and Debas’ Self-stabilizing Algorithm for Mutual Exclusion
- Quiescence of Self-stabilizing Gossiping among Mobile Agents in Graphs
- A Self-stabilizing Algorithm with Tight Bounds for Mutual Exclusion on a Ring
- Constant-Space Localized Byzantine Consensus
This page was built for publication: Self-stabilization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2782251)
