Search

Self-stabilization is an excellent approach for adding fault tolerance to a distributed multi-agent system. However, two properties of self-stabilization theory, closure and convergence, may not be satisfied if agents are selfish. To guarantee closure in the presence of selfish agents, we propose fault-containment as a method to constrain legitimate configurations of the self-stabilizing system to be Nash equilibria. To guarantee convergence, we introduce probabilistic self-stabilization to set the probabilities of rules such that agents’ self-interests are satisfied. We also assume selfish agents as capable of performing unauthorized actions at any time, which threatens both properties, and present a stepwise solution to handle it. As a case study, we consider the problem of distributed clustering and propose self-stabilizing algorithms for forming clusters. Simulation results show that our algorithms react correctly to rule deviations and outperform comparable schemes in terms of fairness and stabilization time.

Introduced by Emek and Wattenhofer (PODC 2013), the \emph{stone age (SA)} model provides an abstraction for network algorithms distributed over randomized finite state machines. This model, designed to resemble the dynamics of biological processes in cellular networks, assumes a weak communication scheme that is built upon the nodes' ability to sense their vicinity in an asynchronous manner. Recent works demonstrate that the weak computation and communication capabilities of the SA model suffice for efficient solutions to some core tasks in distributed computing, but they do so under the (somewhat less realistic) assumption of fault free computations. In this paper, we initiate the study of \emph{self-stabilizing} SA algorithms that are guaranteed to recover from any combination of transient faults. Specifically, we develop efficient self-stabilizing SA algorithms for the \emph{leader election} and \emph{maximal independent set} tasks in bounded diameter graphs subject to an asynchronous scheduler. These algorithms rely on a novel efficient self-stabilizing \emph{asynchronous unison (AU)} algorithm that is "thin" in terms of its state space: the number of states used by the AU algorithm is linear in the graph's diameter bound, irrespective of the number of nodes.

In this paper, we evaluate and compare the performance of two approaches, namely self-stabilization and rollback, to handling consistency violating faults (cυf) that occur when a self-stabilizing distributed graph-based program is executed on an eventually consistent key-value store. Consistency violating faults are caused by reading wrong values due to weaker level of consistency provided by the key-value store. One way to deal with these faults is to utilize rollback whereas another way is to rely on the property of self-stabilization that is expected to provide recovery from arbitrary states. We evaluate both these approaches in different case studies -planar graph coloring, arbitrary graph coloring, and maximal matching-as well as for different problem dimensions such as input data characteristics, workload partition, and network latency. We also consider the effect of executing non-stabilizing algorithm with rollback with a similar stabilizing algorithm that does not utilize rollback.

For the problem of computing the connected components of a graph, this paper considers the design of algorithms that are resilient to transient hardware faults, like bit flips. More specifically, it applies the technique of \emph{self-stabilization}. A system is self-stabilizing if, when starting from a valid or invalid state, it is guaranteed to reach a valid state after a finite number of steps. Therefore on a machine subject to a transient fault, a self-stabilizing algorithm could recover if that fault caused the system to enter an invalid state. We give a comprehensive analysis of the valid and invalid states during label propagation and derive algorithms to verify and correct the invalid state. The self-stabilizing label-propagation algorithm performs $\bigo{V \log V}$ additional computation and requires $\bigo{V}$ additional storage over its conventional counterpart (and, as such, does not increase asymptotic complexity over conventional \labelprop). When run against a battery of simulated fault injection tests, the self-stabilizing label propagation algorithm exhibits more resilient behavior than a triple modular redundancy (TMR) based fault-tolerant algorithm in $80\%$ of cases. From a performance perspective, it also outperforms TMR as it requires fewer iterations in total. Beyond the fault-tolerance properties of self-stabilizing label-propagation, we believe, they are useful from the theoretical perspective; and may have other use-cases.

Self-stabilizing algorithms recover from sever faults, such as inconsistent initialization. Traditionally, when designing a self-stabilizing message-passing algorithm, the main goal was to reduce the time until stabilization. The message cost was neglected. In this work, we strive to reduce the number of messages sent on the average per time period. As a tool, we present a stabilizing module that can message-efficiently determine when a task (from a wide family of tasks) is terminated. False positive detection is possible, but only when faults occurred. This module can then be used in the transformation of non self-stabilizing algorithms into self-stabilizing ones.

The vision of automated driving promises to have safer and more cost-efficient transport systems. Automated driving systems have to demonstrate high levels of dependability and affordability. Recent advances of new communication technologies, e.g., 5G, allow significant cost reduction of timely shared sensory information. However, the design of fault-tolerant automated driving systems remains an open challenge. This work considers the design of automated driving systems through the lenses of self-stabilization—a very strong notion of fault-tolerance. Our self-stabilizing algorithms guarantee, within a bounded period, recovery from a broad fault model and arbitrary state corruption. After this recovery period, our algorithms provide safe maneuver execution despite the presence of failures, such as unbounded periods of packet loss and timing failures as well as inaccurate sensory information and malicious behavior. We evaluate the proposed algorithms through a rigorous correctness proof and a worst-case analysis as well as a prototype that focuses on an intersection crossing protocol. We validate our prototype via computer simulations and a testbed implementation. Our preliminary results show a reduction in the number of vehicle collisions and dangerous situations.

This paper considers the Byzantine consensus problem for nodes with binary inputs. The nodes are interconnected by a network represented as an undirected graph, and the system is assumed to be synchronous. Under the classical point-to-point communication model, it is well-known [7] that the following two conditions are both necessary and sufficient to achieve Byzantine consensus among $n$ nodes in the presence of up to $f$ Byzantine faulty nodes: $n \ge 3f+1$ and vertex connectivity at least $2f+1$. In the classical point-to-point communication model, it is possible for a faulty node to equivocate, i.e., transmit conflicting information to different neighbors. Such equivocation is possible because messages sent by a node to one of its neighbors are not overheard by other neighbors. This paper considers the local broadcast model. In contrast to the point-to-point communication model, in the local broadcast model, messages sent by a node are received identically by all of its neighbors. Thus, under the local broadcast model, attempts by a node to send conflicting information can be detected by its neighbors. Under this model, we show that the following two conditions are both necessary and sufficient for Byzantine consensus: vertex connectivity at least $\lfloor 3f/2 \rfloor + 1$ and minimum node degree at least $2f$. Observe that the local broadcast model results in a lower requirement for connectivity and the number of nodes $n$, as compared to the point-to-point communication model. We extend the above results to a hybrid model that allows some of the Byzantine faulty nodes to equivocate. The hybrid model bridges the gap between the point-to-point and local broadcast models, and helps to precisely characterize the trade-off between equivocation and network requirements.

EgeUn###, A self-stabilizing distributed system can initially start at any state and regain a legal state in a finite time without any external intervention. Self-stabilizing systems can automatically recover from faults and they are popular fault tolerant systems. Simulating self-stabilizing systems is a vital task in case of fault-tolerant distributed networks where node and edge updates can be frequent. A discrete-event simulation is a method of simulating the behavior and performance of an algorithm running on a distributed system. To the best of our knowledge, there are few simulators for self-stabilizing distributed algorithms in literature where these simulators are generally outdated and hard to use. In this paper we propose a novel distributed self-stabilizing discrete-event simulator (SELFSIM). SELFSIM is written in C# programming language on.NET Framework and supports up-to-date principles of software development techniques such as separation of concerns. We give the design and implementation of the proposed simulator and compare SELFSIM with its counterparts by considering various parameters such as supported node count (scalability), topological features, daemon (scheduler) types, etc., and show the superiority of our simulator. © 2018 IEEE., National Council for Scientific Research: 215E115, ACKNOWLEDGMENT The authors would like to thank the TUBITAK (Scientific and Technical Research Council of Turkey) for financial support of the project 215E115 which this work belongs to it.

By introducing programmability, automated verification, and innovative debugging tools, Software-Defined Networks (SDNs) are poised to meet the increasingly stringent dependability requirements of today's communication networks. However, the design of fault-tolerant SDNs remains an open challenge. This paper considers the design of dependable SDNs through the lenses of self-stabilization – a very strong notion of fault-tolerance. In particular, we develop algorithms for an in-band and distributed control plane for SDNs, called Renaissance, which tolerates a wide range of (concurrent) controller, link, and communication failures. Our self-stabilizing algorithms ensure that after the occurrence of an arbitrary combination of failures, (i) every non-faulty SDN controller can eventually reach any switch in the network within a bounded communication delay (in the presence of a bounded number of concurrent failures) and (ii) every switch is managed by at least one non-faulty controller. We evaluate Renaissance through a rigorous worst-case analysis as well as a prototype implementation (based on OVS and Floodlight), and we report on our experiments using Mininet.

Research in system stabilization has traditionally relied on the availability of a complete system implementation. As such, it would appear that the scalability and reusability of stabilization is limited in practice. To redress this perception, in this paper, we show for the first time that system stabilization may be designed knowing only the system specification but not the system implementation. We refer to stabilization designed thus as specification-based design of stabilization and identify “local everywhere specifications” and “convergence refinements” as being amenable to the specification-based design of stabilization. Using our approach, we present the design of Dijkstra’s four-state stabilizing token-ring system starting from an abstract fault-intolerant token-ring system. We also present an illustration of automated design of specification-based stabilization on a three-state token-ring system.

Self stabilization is an important paradigm for the autonomous recovery of a distributed system from transient failures such as energy depletion of nodes and disrupted connections. It has been used in wireless sensor networks (WSN) as these networks are expected to automatically recover from a transient fault without human intervention. Graph matching is fundamental a graph theory problem which has a broad application range in WSNs and it has been studied extensively in self-stabilizing settings. In this work, we build a simulation model and perform tests to evaluate the fault tolerance properties of self-stabilizing matching algorithms. To the best of our knowledge, this is the first practical evaluation of these algorithms. Considering WSNs, we assume distributed fair and synchronous schedulers. Simulation results have shown that there is a tradeoff between stabilization time of algorithms and the quality of their results. The improvement algorithms which has better lower bounds give better matchings at the cost of longer durations of instability.

In this paper, we focus on the implementation of distributed programs in using a key-value store where the state of the nodes is stored in a replicated and partitioned data store to improve performance and reliability. Applications of such algorithms occur in weather monitoring, social media, etc. We argue that these applications should be designed to be stabilizing so that they recover from an arbitrary state to a legitimate state. Specifically, if we use a stabilizing algorithm then we can work with more efficient implementations that provide eventual consistency rather than sequential consistency where the data store behaves as if there is just one copy of the data. We find that, although the use of eventual consistency results in consistency violation faults (cvf) where some node executes its action incorrectly because it relies on an older version of the data, the overall performance of the resulting protocol is better. We use experimental analysis to evaluate the expected improvement. We also identify other variations of stabilization that can provide additional guarantees in the presence of eventual consistency.Finally, we note that if the underlying algorithm is not stabilizing, even a single \cvf may cause the algorithm to fail completely thereby making it impossible to benefit from this approach., Comment: submission to ICDCN 2018

Vertex cover (VC) is one of the most fundamental graph-theoretical problems and has been widely used in wireless sensor networks (WSNs), particularly for the link monitoring problem. It is well known that a solution to the independent set problem (IS), which is another fundamental graph-theoretical problem, is complement of a VC. Self- stabilization is an important concept for designing fault tolerance systems. There have been many self-stabilizing VC and IS algorithms in the field. Even though a self-stabilizing IS algorithm can provide VC solutions, it does not give a theoretical guarantee on approximation ratio. In this work, we focus on practical fault tolerance performance of self- stabilizing IS algorithms in case of a vertex cover problem, particularly link monitoring in WSNs. We implement all existing self-stabilizing VC and IS algorithms and make simulations assuming a WSN in which nodes run synchronously. Results show that self-stabilizing IS algorithms in general are able to find better covers than VC algorithms, as they provide roughly 15% smaller solution sets. Furthermore, IS algorithms that run under distributed scheduler converges to a desired configuration in considerably less number of rounds than VC algorithms.

Failure of a single element or of a communication medium between more than one elements of a distributed system result in undesired activities toward the common goal of the network. As a nature of distributed algorithms, since the processing elements only have limited (local) information and are independent from each other with respect to the computational powers, these failures are difficult to detect and resolve. Fault tolerant mechanisms which aim at masking the failure so that the fault is not observable to the users of the system are costly in terms of computational resources. On the other hand, the masking constraint can be relaxed in such systems where an undesired behavior of the system is tolerable for a limited time, given that the system is guaranteed to reach a non-faulty and desired state in a foreseeable time. Self stabilization is an important non-masking fault tolerant concept. A self-stabilizing algorithm is a set of rules which are activated and executed in case of an adversarial configuration of the system in such a way that the system eventually reaches a desired configuration in which none of the rules are activated, i.e., system is stabilized. This thesis is a collection of new self-stabilizing algorithms for some of the classical graph theoretical problems. We focus on the capacitated versions of these problems which have not attracted the attention they deserve from the fault tolerance field, even though their real world applications generally come with their own capacity restrictions. We particularly deal with and propose novel self-stabilizing algorithms for capacitated matching (b-matching), capacitated minimum spanning tree (CMST) and capacitated k-way graph partitioning problems. We give formal proofs for the correctness, convergence and closure of this algorithms., Bir dağıtık sistemi oluşturan birimlerden birinde ya da bu birimlerin birbirleriyle iletişim kurdukları bağlantıda bir hatanın meydana gelmesi, sistemin çalışmasında istenmeyen etkiler oluşturabilir. Dağıtık algoritmaların doğası gereği işlem birimlerinin sınırlı (yerel) bilgiye sahip olmaları ve hesaplama kuvveti yönünden birbirlerinden bağımsız olmaları, söz konusu hataların tespit edilip çözülmesini zorlaştırır. Hatayı sistemin kullanıcısının gözlemlemesini önleyecek şekilde örtmeyi hedefleyen hata-toleranslı mekanizmalar hesaplama kaynakları yönünden oldukça masraflıdır. Öte yandan, birimlerin istenmeyen davranışının belirli bir süre için kabul edilebildiği sistemlerde, sistemin öngörülebilir bir süre içinde hatasız ve istenen bir konfigürasyona ulaşması garanti ediliyorsa, hatayı gizleme koşulu esnetilebilir. Öz-kararlılık, önemli bir maskelemesiz hata toleransı kavramıdır. Bir özkararlı algoritma, sistemin istenmeyen bir konfigürasyonda bulunması halinde etkinleştirilip çalıştırılan ve nihayetinde sistemi hiçbir kuralın aktif olmadığı öz-kararlı olarak adlandırılan bir konfigürasyona ulaştıran bir dizi kuraldan oluşur. Bu tez, bazı kapasite kısıtlı çizge teorisi problemleri için geliştirilmiş olan öz-kararlı algoritmalardan oluşur. Klasik çizge teorisi problemlerinin gerçek dünya uygulamaları genelde kapasite kısıtı içermesine rağmen bu problemlerin kapasite kısıtlı versiyonları öz-kararlılık literatüründe hak ettiği kadar dikkat çekmemiştir. Biz bu çalış- mada problemlerin kapasite kısıtlı versiyonlarına odaklanıyoruz. Özellikle kapasite kısıtlı eşleme (b-eşleme), kapasite kısıtlı en küçük kapsayan ağaç ve kapasite kısıtlı çizge bölme problemleriyle ilgilenip bu problemler için özgün öz-kararlı algoritmalar öneriyoruz. Ayrıca bu algoritmaların doğruluk, kapalılık ve yakınsama özelliklerini ispatlıyoruz.

International audience; We study theoretical and practical aspects of five of the most well-known self-stabilizing dining philosophers algorithms. We theoretically prove that three of them are incorrect. For practical evaluation, we simulate these five algorithms as well as two classic non-self-stabilizing algorithms and evaluate their fault-tolerance, latency and throughput of critical section access. We present a new combined algorithm that achieves the best throughput of the two remaining correct self-stabilizing algorithms by determining the system load and switching between these basic algorithms. We prove the combined algorithm correct, simulate it and study its performance characteristics.

Fault tolerance measures of distributed systems can be calculated precisely by state space analysis of the Markov chain corresponding to the product of the system components. The power of such an approach is inherently confined by the state space explosion, i.e. the exponential growth of the Markov chain in the size of the underlying system. We propose a decompositional method to alleviate this limitation. Lumping is a well-known reduction technique facilitating computation of the relevant measures on the quotient of the Markov chain under lumping equivalence. In order to avoid computation of lumping equivalences on intractably large Markov chains, we propose a system decomposition supporting local lumping on the considerably smaller Markov chains of the subsystems. Recomposing the lumped Markov chains of the subsystems constructs a lumped transition model of the whole system, thus avoiding the construction of the full product chain. An example demonstrates how the limiting window availability (i.e. a particular fault tolerance measure) can be computed for a self-stabilizing system exploiting lumping and decomposition.

Existing approaches for verifying self-stabilization with a symbolic model checker have relied on the use of weak fairness. We point out that this approach has limited scalability. To overcome this limitation, first, we show that if self-stabilization is possible without fairness then the cost of verifying self-stabilization is substantially lower. In fact, we observe from several case studies that the cost of verification under weak fairness is more than 1000 times that of the cost without fairness. For the case where weak fairness is essential for self-stabilization, we demonstrate the feasibility of two approaches for improving scalability: (1) decomposition and (2) utilizing the weaker version of self-stabilization, namely weak stabilization. In the first approach, the designer partitions the program into components where each component satisfies its property without fairness. We show that the first approach enables us to verify Huang's mutual exclusion program for uniform rings with 31 processes (state space 10^1^3^8) whereas without this approach, it was not possible to verify the same program with 5 processes (state space 10^1^0). In the second approach, a weaker version of self-stabilization is verified. For Hoepman's ring-orientation program on odd-length ring, we show that it is possible to verify weak stabilization for 301 processes (state space 10^1^8^1) whereas self-stabilization could not be verified for 9 processes (state space 10^5) under weak fairness. Furthermore, one can utilize transformation algorithms to convert weak stabilizing programs to probabilistically stabilizing programs. Hence, for the case where it is not possible to verify deterministic self-stabilization, one can obtain the assurance provided by probabilistic self-stabilization at a significantly reduced cost. Finally, we also present 5 case studies to illustrate the scalability of stabilization with techniques suggested in this paper.

Current reconfiguration techniques are based on starting the system in a consistent configuration, in which all participating entities are in their initial state. Starting from that state, the system must preserve consistency as long as a predefined churn rate of processors joins and leaves is not violated, and unbounded storage is available. Many working systems cannot control this churn rate and do not have access to unbounded storage. System designers that neglect the outcome of violating the above assumptions may doom the system to exhibit illegal behaviors. We present the first automatically recovering reconfiguration scheme that recovers from transient faults, such as temporal violations of the above assumptions. Our self-stabilizing solutions regain safety automatically by assuming temporal access to reliable failure detectors. Once safety is re-established, the failure detector reliability is no longer needed. Still, liveness is conditioned by the failure detector's unreliable signals. We show that our self-stabilizing reconfiguration techniques can serve as the basis for the implementation of several dynamic services over message passing systems. Examples include self-stabilizing reconfigurable virtual synchrony, which, in turn, can be used for implementing a self-stabilizing reconfigurable state-machine replication and self-stabilizing reconfigurable emulation of shared memory.

The foraging problem, which evolved from ants finding food and delivering them to the nest, is for a swarm of robots to transport objects from a source to a destination. To avoid collision of robots or congestions, object transportation is generally conducted in a pipelining manner. Existing solutions towards the foraging problem either have performance problems or cannot tolerate failures. We present a self-stabilizing solution for the swarm robotic system to form a pipeline structure to transport objects and achieve the foraging task. In this paper, we first define the stable state for the swarm, which includes two requirements: (1) the robots operate in non-overlapping regions, i.e., transport objects in a pipeline structure and (2) the transportation rate of the system is optimal. Then, we introduce our self-stabilizing algorithm for the foraging problem and prove its convergence and the correctness of its convergence properties. Due to the self-stabilization nature, our solution is decentralized and fault tolerant. The swarm can achieve the foraging task as long as there is at least one working robot. Due to the definition of the stable state, our swarm system, when converged, can achieve optimal performance. We conduct simulations to evaluate the effectiveness of our algorithm, and the experimental results show that from any state, our algorithm can converge very quickly to reach the stable state and provide optimal performance for object transportation.

The erratic behavior of wireless channels is still a major hurdle in the implementation of robust applications in wireless networks. In the past it has been argued that self-stabilization is a remedy to provide the needed robustness. This assumption has not been verified to the extent necessary to convince engineers implementing such applications. A major reason is that the time in which a self-stabilizing system returns to a valid state is unpredictable and potentially unbound. Failure rates typically depend on physical phenomena and in self-stabilizing systems each node tries to react to failures in an inherently adaptive fashion by the cyclic observation of its neighbors' states. When the frequency of state changes is too high, the system may never reach a state sufficiently stable for a specific task. In this paper we substantiate the conditions under which self-stabilization leads to fault tolerance in wireless networks and look at the myths about the power of self-stabilization as a particular instance of self-organization. We investigate the influences of the error rate and the neighbor state exchange rate on the stability and the convergence time on topology information acquired in real network experiments.

We present a new fault-tolerant algorithm for the problem of computing the connected components of a graph. Our algorithm derives from a highly parallel but non-resilient algorithm, which is based on the technique of label propagation (LP). To make the (LP) algorithm resilient to transient soft faults, we apply an algorithmic design principle that we refer to as self-correction. Briefly, a self-correcting algorithm detects if it has reached an invalid state given that it was previously in a known valid state; and if so, restores itself back to a valid state assuming the availability of a selective guaranteed-reliable mode. Our self-correcting algorithm, FT-LP, has relatively small storage and computation overheads: in empirical tests on a variety of input graphs, we observe execution time overheads of 10-35% in FT-LP compared to LP even at high fault rates, with the computation overhead increasing gracefully as fault rates increase.

International audience; A snap-stabilizing algorithm, regardless of the initial configuration of the system, guarantees that it always behaves according to its specification. We consider here the locally shared memory model. In this model, we propose the first snap-stabilizing Propagation of Information with Feedback (PIF) algorithm for rooted networks of arbitrary connected topology which is proven assuming the distributed unfair daemon. Then, we use the proposed PIF algorithm as a key module in designing snap-stabilizing solutions for some fundamental problems in distributed systems, such as Leader Election, Reset, Snapshot, and Termination Detection. Finally, we show that in the locally shared memory model, snap-stabilization is as expressive as self-stabilization by designing a universal transformer to provide a snap-stabilizing version of any algorithm that can be self-stabilized with the transformer of Katz and Perry (Distributed Computing, 1993). Since by definition a snap-stabilizing algorithm is also self-stabilizing, self-and snap-stabilization have the same expressiveness in the locally shared memory model.

In self-stabilization, each node has a local view of the distributed network system, in a finite amount of time the system converges to a global setup with desired property, in this case establishing a 2-packing set. Using a graph G=(V,E) to represent the network, a subset [email protected]?V is a 2-packing if @[email protected]?V:|N[i]@?S|=

This paper presents a new transformation which adds fault-containment properties to silent self-stabilizing algorithms. The transformation features a constant slow-down factor and the fault-gap—that is the minimal time between two containable faults—is also constant. The transformation scales well to arbitrarily large systems and avoids global synchronization. The presented transformation is the first with a constant fault-gap and requires no knowledge of the system size.

Topology embedding enables one to execute a protocol designed for a specific (virtual) topology on another (real) topology by embedding the virtual topology on the real topology. In this paper, we propose a self-stabilizing emulation technique that provides reliable communication on a virtual topology in the presence of transient faults in real topology. The proposed protocol improves the execution slowdown of previous two protocols [19, 20] and provides adaptive message delivery delay on the emulated channels, which is a new type of adaptability against transient faults.

International audience; Distributed fault-tolerance can mask the effect of a limited number of permanent faults, while self-stabilization provides forward recovery after an arbitrary number of transient faults hit the system. FTSS (Fault-Tolerant Self-Stabilizing) protocols combine the best of both worlds since they tolerate simultaneously transient and (permanent) crash faults. To date, deterministic FTSS solutions either consider static (i.e. fixed point) tasks, or assume synchronous scheduling of the system components.In this paper, we present the first study of deterministic FTSS solutions for dynamic tasks in asynchronous systems, considering the unison problem as a benchmark. Unison can be seen as a local clock synchronization problem as neighbors must maintain digital clocks at most one time unit away from each other, and increment their own clock value infinitely often. We present several impossibility results for this difficult problem and propose an FTSS solution (when the problem is solvable) for the state model that exhibits optimal fault-containment.

This work presents a general and complete method to protect a system against possible malicious programs. We provide concepts for building a system that can automatically recover from an arbitrary state including even one in which a Byzantine execution of one or more programs repeatedly attempts to corrupt the system state. Preservation of a guest execution is guaranteed as long as the guest respects a predefined contract, while efficiency is improved by using stabilizing reputation. We augment a provable self-stabilizing host operating system implementation with a contract-enforcement framework example.

We initiate the study of error confinement in distributed applications, where the goal is that only nodes that were directly hit by a fault may deviate from their correct external behavior, and only temporarily. The external behavior of all other nodes must remain impeccable, even though their internal state may be affected. Error confinement is impossible if an adversary is allowed to inflict arbitrary transient faults on the system, since the faults might completely wipe out input values. We introduce a new fault tolerance measure we call agility, which quantifies the strength of an algorithm that disseminate information, against state corrupting faults.We study the basic problem of broadcast, and propose algorithms that guarantee error confinement with optimal agility to within a constant factor, even in asynchronous networks when the topology is unknown. These algorithms can serve as building blocks in more general reactive systems. Previous results in exploring locality in reactive systems were not error confined, and relied on the assumption (not used in current paper) that the errors hitting each node are probabilistic, such that a faulty node itself, or its neighbor, can detect the node faulty.The main algorithm uses the novel core bootstrapping technique, that seems inherent for voting in reactive networks; its analysis leads to an interesting combinatorial problem. The technique and the analysis may be of independent interest