Catálogo de publicaciones - libros

Writing a perfectly correct code is a challenging and a nearly impossible task. In this work we suggest the paradigm in order to cope with eventual Byzantine programs. The program specification composer enforces the program specifications (both the safety and the liveness properties) in run time using predicates over input and output variables. The component programmer will use these variables in the program implementation. We suggest using the “sand-box” approach in which every instruction of the program that changes a specification variable, is executed first with temporary variables and that is in order to avoid execution of an instruction that violates the specifications. In addition, external monitoring is used for coping with transient faults and for ensuring convergence to a legal state. The implementation of these ideas includes the definition of new instructions in the programming language with the purpose of allowing addition of predicates and recovery actions. We suggest a design for a tool that extends the Java programming language. In addition to that, we provide a correctness proof scheme for proving that the code combined with the predicates and the recovery actions is self-stabilizing and, under the restartability assumption, eventually fulfills its specifications.

A wireless sensor network is a collection of tiny and cheap devices deployed over a physical surface and able to gather and process in a collaborative way some information about a specified phenomenon occuring in their surroundings. Particularly, in tracking applications, the end-user is interested in the statistics of mobile targets crossing the region monitored by the network (i.e. trajectory forecast, speed, etc.). Those statistics share the common need for causally and temporally correlated data. In this paper, we evaluate the energetics cost of TRAC, a high level tracking architecture designed to respond to the requirements of tracking applications. We compare TRAC to a basic flooding-based mechanism, which does not offer any guarantee on the correlation of the disseminated data. Via theoritical analysis and simulations we show that the complexity of TRAC is O(2) while the complexity of the flooding-based solution is O() (where is the number of nodes in the network). These results emphasize the extra cost of high level properties. We conjecture that a careful aggregation of the data managed by TRAC drops its complexity to O() and we provide some hints to implement these optimizations.

The complexity of today’s distributed computing environments is such that the presence of bugs and security holes is statistically unavoidable. A very promising approach to this issue is to implement a self-protected system, similarly to a natural immune system which has the ability to detect the intrusion of foreign elements and react while it is still in progress.

This paper describes an approach relying on component-based software engineering to ease the protection of distributed systems. The knowledge of the application architecture is used to detect foreign activities and to trigger counter measures. We focus on a mean to recognize known and unknown attacks independently from legacy software and avoiding false positives. Hence, the scope of the detected attacks is, for the moment, limited to the detection of illegal communications. We describe how this approach can be applied to provide self-protection for clustered 2ee applications with a very low overhead.

A protocol, starting from any configuration, always behaves according to its specification. In this paper, we propose a light semi-automatic method allowing to snap-stabilize self-stabilizing wave protocols for arbitrary networks with a unique initiator. To that goal, we consider such a self-stabilizing protocol . We then slightly update to obtain a protocol that can be automatically transformed, using a black box protocol, into a snap-stabilizing protocol. is easy to obtain from compared to the design of a snap-stabilizing protocol.

We generalize the classic dining philosophers problem to separate the conflict and communication neighbors of each process. Communication neighbors may directly exchange information while conflict neighbors compete for the access to the exclusive critical section of code. This generalization is motivated by a number of practical problems in distributed systems including problems in wireless sensor networks. We present a self-stabilizing deterministic algorithm — that solves a restricted version of the generalized problem where the conflict set for each process is limited to its -hop neighborhood. Our algorithm is terminating. We formally prove correct and evaluate its performance. We then extend to handle fully generalized problem. We further extend it to handle a similarly generalized drinking philosophers problem. We describe how can be implemented in wireless sensor networks and demonstrate that this implementation does not jeopardize its correctness or termination properties.

Stabilizing distributed systems expect all the component processes to run predefined programs that are externally mandated. In Internet scale systems, this is unrealistic, since each process may have selfish interests and motives related to maximizing its own payoff. This paper formulates the problem of selfish stabilization that shows how competition blends with cooperation in a stabilizing environment.

Self-stabilizing systems are often only evaluated in terms of worst-case time and space complexities for the recovery from arbitrary state disruptions. In this paper, we interpret and formalize well-known fault tolerance measures for masking fault-tolerant systems, namely reliabilty, instantaneous availability, and limiting availability in the context of self-stabilizing systems. This allows to additionally evaluate selfstabilizing systems by these well-accepted measures. The calculation is challenging due to a large (and possibly infinite) state space. We present an analysis procedure that comprises a suitable state abstraction thereby making the calculation tractable. Exemplarily, we apply the procedure to a system that constructs a depth-first search spanning tree showing that our approach is feasible and yields meaningful results.

The Circle Formation Problem (CFP) consists in the design of a protocol insuring that starting from an initial arbitrary configuration, robots eventually form a regular -gon. In this paper, we present the first protocol which deterministically solves CFP in finite time for any number of robots, provided that ∉ {4,6,8}. The proposed protocol works in the semi-synchronous model introduced in [1]. The robots are assumed to be uniform, anonymous, oblivious, and they share no kind of coordinate system nor common sense of direction.

This work presents approaches for designing the input-output device management components of self-stabilizing operating systems. As an example, we demonstrate the non-stability of the standard protocol for storage devices. We state the requirements that an operating system and devices should satisfy in order to become self-stabilizing. Then we suggest two solutions to satisfy these requirements. The first uses leases in order to guarantee progress from the device side. The second assumes stabilization of the device, and uses snapshots to perform consistency checks. By supplying an infrastructure for practical self-stabilizing systems, robust and dependable systems can be achieved.

We consider repeated communication sessions between a sender (e.g., Radio Frequency Identification, RFID, reader) and a receiver (RFID). A proactive information security scheme is proposed. The scheme is based on the assumption that the information exchanged during at least one of every successive communication sessions is not exposed to an adversary. Then a computational secure scheme based on the information secure scheme is used to ensure that even in the case that the adversary listens to all the information exchanges, the communication between the sender and the receiver is secure. In particular, the scheme can be used in the domain of remote controls (e.g., for cars).