Catálogo de publicaciones - libros

Hardware and software components are suggested for enabling the creation of a self-stabilizing on top of an off-the-shelf, non-self-stabilizing processor. Simple “watchdog” hardware called periodic reset monitor () provides a basic solution. The solution is extended to a stabilization enabling hardware () which removes any real time requirement from the . A stabilization enabling system that extends the with some software components provides the user (the designer) with a self-stabilizing processor abstraction. Adapting the current code to be self-stabilizing is supported using a mechanism for enforcing the software configuration.

An indulgent algorithm is a distributed algorithm that, besides tolerating process failures, also tolerates arbitrarily long periods of instability, with an unbounded number of timing and scheduling failures. In particular, no process can take any irrevocable action based on the operational status, correct or failed, of other processes. This paper presents an intuitive and general characterization of indulgence. The characterization can be viewed as a simple application of Murphy’s law to partial runs of a distributed algorithm, in a computing model that encompasses various communication and resilience schemes. We use our characterization to establish several results about the inherent power and limitations of indulgent algorithms.

Connectivity and sensing coverage are two fundamental concepts in the design of wireless sensor networks (WSNs). In this paper, we investigate the relationship between coverage and connectivity for (CWSN), where every point in a field of interest is covered by at least sensors. Furthermore, we compute the connectivity of CWSN based on the degree of sensing coverage. We also propose measures of fault tolerance for CWSN based on network connectivity and sensing coverage. Random distributions of the sensors in a field have been widely used in most of sensor networking protocols, in spite of the fact that these deployment techniques do not always provide complete, void-free coverage. On the contrary, we consider both deterministic and random sensor deployment strategies to meet coverage degree requirements of sensing applications. Using our (AET) model, we prove that if the sensing coverage degree is and ≥ 2× , the network connectivity is higher than . Precisely, our analysis of the geometric properties of deterministic sensor deployment strategies, demonstrates that sensing -coverage and yield CWSN connectivity that is higher than . These findings are of practical use for network designers to build up sensing applications with prescribed degrees of sensing coverage, network connectivity and fault tolerance.

Power management is an important problem in battery powered sensor networks as the sensors are required to operate for a long time (usually, several weeks to several months). One of the challenges in developing power management protocols for sensor networks is prototyping. Specifically, existing programming platforms for sensor networks (e.g., nesC/TinyOS) use an event-driven programming model and, hence, require the designers to be responsible for stack management, buffer management, flow control, etc. Therefore, the designers simplify prototyping their solutions either by implementing their own discrete event simulators or by modeling them in specialized simulators. To enable the designers to prototype power management protocols in target platform (e.g., nesC/TinyOS), in this paper, we use , a programming tool for sensor networks. ProSe enables the designers to specify their programs in simple abstract models while hiding low-level challenges of sensor networks and programming-level challenges. As a case study, in this paper, we specify a power management protocol with ProSe, automatically generate the corresponding nesC/TinyOS code, and evaluate its performance. Based on the performance results, we expect that ProSe enables the designers to rapidly prototype, quickly deploy, and easily evaluate their protocols.

This paper combines various self-stabilization techniques within a replication protocol that ensures eventual consistency in large-scale distributed systems subject to network partitions and asynchrony. A simulation study shows that the resulting protocol is scalable and achieves high throughput under load.

Our protocol does not rely on any form of consensus, which would lead to block the replicas in case of partitions and asynchrony. Our protocol instead ensures that (1) updates are continuously applied to the replicas and (2) no two updates are ever performed in a different order. Gaps might occur during periods of unreliable communication. They are filled whenever connectivity is provided, and consistency is then eventually ensured, but without any conscious commitment. That is, there is no point in the computation when replicas know that consistency is achieved. This unconsciousness is the key to tolerating perpetual asynchrony with no consensus support.

We reduce the problem of proving the convergence of a randomized self-stabilizing algorithm under k-bounded policies to the convergence of the same algorithm under a specific policy. As a consequence, all -bounded schedules are equivalent: a given algorithm is self-stabilizing under one of them if and only if it is self-stabilizing under any of them.

In this paper we study k-strong self-stabilizing systems, which satisfy the properties of strong confinement and of k-linear time adaptivity. Strong confinement means that a non faulty processor has the same behavior with or without the presence of faults elsewhere in the system (in other words faults are confined). k-linear time adaptivity means that after k or less faults hitting the system in a correct state, the recovery takes a number of rounds linear in k.

We show, under some conditions, how an asynchronous self-stabilizing system can be automatically transformed into an equivalent synchronous 1-strong self-stabilizing system where the recovery takes at most 3 rounds. We present in detail the transformer as well as a 1-strong synchronous unison algorithm. We also discuss how the construction can be extended to the k-strong case, for an arbitrary k.

We consider the complexity of algorithms in message-driven models, i.e., models of distributed computations where events can only be caused by message receptions but not by the passage of time. Hutle and Widder (2005) have shown that there is no self-stabilizing implementation of the eventually strong failure detector, and thus the eventual leader oracle Ω in such models under certain assumptions. Under stronger assumptions it was shown that even the eventually perfect failure detector can be implemented in systems consisting of at least + 2 processes — being the upper bound on the number of processes that crash during an execution.

In this paper we show that + 2 is in fact a lower bound in message-driven systems, even if non stabilizing algorithms are considered. This contrasts time-driven models where + 1 is sufficient for failure detector implementations. After that, we provide an efficient message-driven implementation of Ω. Our algorithm is efficient in the sense that not all processes have to send messages forever, which is an improvement to previous message-driven failure detector implementations.

In this paper, we focus on the problem of automated addition of fault-tolerance to an existing fault-intolerant program. We consider three levels of fault-tolerance, namely , , and , based on safety and liveness properties satisfied in the presence of faults. More specifically, a nonmasking (respectively, failsafe, masking) program satisfies liveness (respectively, safety, both safety and liveness) in the presence of faults. For failsafe and masking fault-tolerance, we consider two additional levels, and , based on satisfaction of timing constraints in the presence of faults. We present a polynomial time algorithm (in the size of the input program’s region graph) that adds from an arbitrary given set of states to another arbitrary set of states. Using this algorithm, we propose a sound and complete synthesis algorithm that transforms a fault-intolerant real-time program into a nonmasking fault-tolerant program. Furthermore, we introduce sound and complete algorithms for adding soft/hard-failsafe fault-tolerance. For reasons of space, our results on addition of soft/hard-masking fault-tolerance are presented in a technical report.

We address the self-stabilizing unison problem in tree networks. We propose two self-stabilizing unison protocols without any reset correcting system. The first one, called Protocol _, being scheduled by a synchronous daemon, is self-stabilizing to synchronous unison in at most steps, where is the diameter of the network. The second one, Protocol _, being scheduled by an asynchronous daemon, is self-stabilizing to asynchronous unison in at most rounds. Moreover, both are optimal in space. The amount of required space is independent of any local or global information on the tree. Furthermore, they work on dynamic trees networks, in which the topology may change during the execution.