Catálogo de publicaciones - libros

As a new challenge of containing the unbounded influence of Byzantine processes in self-stabilizing protocols, this paper introduces a novel concept of . The strong stabilization relaxes the requirement of so that processes beyond the containment radius are allowed to be disturbed by Byzantine processes, but only a limited number of times. A self-stabilizing protocol is (,,)-strongly stabilizing if any process more than hops away from any Byzantine process is disturbed at most times in a distributed system with at most Byzantine processes. Here denotes the and denotes the .

The possibility and the effectiveness of the strong stabilization is demonstrated using . It is known that the tree orientation has no strictly stabilizing protocol with a constant containment radius. This paper first shows that the problem has no constant bound of the containment radius in a tree with two Byzantine processes even when we allow processes beyond the containment radius to be disturbed any finite number of times. Then we consider the case of a single Byzantine process and present a (1,0,1)-strongly stabilizing protocol, which achieves optimality in both containment radius and times.

In this paper, we quantify the amount of “practical” information ( views obtained from the neighbors, colors attributed to the nodes and links) to obtain “theoretical” information ( the local topology of the network up to distance ) in anonymous networks. In more details, we show that a coloring at distance 2 + 1 is necessary and sufficient to obtain the local topology at distance that includes outgoing links. This bound drops to 2 when outgoing links are not needed. A second contribution of this paper deals with color bootstrapping (from which local topology can be obtained using the aforementioned mechanisms). On the negative side, we show that with a distributed daemon, it is impossible to achieve deterministic color bootstrap, even if the whole network topology can be instantaneously obtained, and with a central daemon, it is impossible to achieve distance when instantaneous topology knowledge is limited to − 1. On the positive side, we show that under the -central daemon, deterministic self-stabilizing bootstrap of colors up to distance is possible provided that -local topology can be instantaneously obtained, and under the distributed daemon, probabilistic self-stabilizing bootstrap is possible for any range.

We present a disk array organization that adapts itself to successive disk failures. When all disks are operational, all data are mirrored on two disks. Whenever a disk fails, the array reorganizes itself, by selecting a disk containing redundant data and replacing these data by their exclusive or (XOR) with the other copy of the data contained on the disk that failed. This will protect the array against any single disk failure until the failed disk gets replaced and the array can revert to its original condition. Hence data will remain protected against the successive failures of up to one half of the original number of disks, provided that no critical disk failure happens while the array is reorganizing itself. As a result, our scheme achieves the same access times as a mirrored organization under normal operational conditions while having a much lower likelihood of loosing data under abnormal conditions. In addition it tolerates much longer repair times than mirrored disk arrays.

Reaching agreement between a set of mobile robots is one of the most fundamental issues in distributed robotic systems. This problem is often illustrated by the gathering problem, where the robots must self-organize and meet at some (not predetermined) location, without a global coordinate system. While being very simple to express, this problem has the advantage of retaining the inherent difficulty of agreement, namely the question of breaking symmetry between robots. In previous works, it was proved that gathering is solvable in asynchronous model with oblivious robots and limited visibility, as long as the robots share the knowledge of some direction, as provided by a compass. However, the problem has no solution in the semi-synchronous model when robots do not share a compass and cannot detect multiplicity.

In this paper, we define a model in which compasses may be unreliable, and study the solvability of gathering oblivious mobile robots with limited visibility in a semi-synchronous model. In particular, we give an algorithm that solves the problem in finite time in a system where compasses are unstable for some arbitrary long periods, provided that they stabilize eventually. In addition, our algorithm is self-stabilizing.

The phase synchronization problem requires each node to infinitely transfer from one phase to the next one under the restriction that at most two consecutive phases can appear among all nodes. In this paper, we propose a self-stabilizing algorithm under the parallel execution model to solve this problem for semi-uniform systems of general graph topologies. The proposed algorithm is memory-efficient; its space complexity per node is (logΔ + log) bits, where Δ is the maximum degree of the system and > 1 is the number of phases.

Self-stabilizing protocols provide autonomous recovery from finite number of transient faults. Fault-containing self-stabilizing protocols promise not only self-stabilization but also quick recovery from and small effect of a small number of faults. However, existing composition techniques of self-stabilizing protocols (e.g. fair composition) cannot preserve the fault-containment property when composing fault-containing protocols. In this paper, we present () framework that preserves the fault-containment property of the composed protocol. We show an example of fault-containing composition of a minimum spanning tree protocol on arbitrary weighted graphs and a median finding protocol on trees via .

Mobile ad hoc networks (MANETs) have many well-known applications in military settings as well as in emergency and rescue operations. However, lack of infrastructure and lack of centralized control make MANETs inherently insecure, and therefore specialized security services are needed for their deployment. is an essential and fundamental security service in MANETs. It is needed to securely cope with dynamic membership and topology and to bootstrap other important security primitives and services without the assistance of any centralized trusted authority. An ideal protocol must involve minimal interaction among the MANET nodes, since connectivity can be unstable. Also, since MANETs are often composed of weak or resource-limited devices, self-certification protocol must be efficient in terms of computation and communication. Unfortunately, previously proposed protocols are far from being ideal.

In this paper, we propose fully non-interactive self-certification protocol based on bi-variate polynomial secret sharing and threshold BLS signature techniques. In contrast with prior work, our techniques do not require any interaction and do not involve any costly reliable broadcast communication among MANET nodes. We thoroughly analyze our proposal and show that it compares favorably to previous mechanisms.

In this paper, we address issues related to defending against wide-spreading worms on the Internet. We study a new class of worms called the self-adaptive worms. These worms dynamically adapt their propagation patterns to defensive countermeasures, in order to avoid or postpone detection, and to eventually infect more computers. We show that existing worm detection schemes cannot effectively defend against these self-adaptive worms. To counteract these worms, we introduce a game-theoretic formulation to model the interaction between worm propagator and defender. We show that the effective integration of multiple defensive schemes (e.g., worm detection, forensics analysis) is critical for defending against self-adaptive worms. We propose different combinations of defensive schemes for different kinds of self-adaptive worms, and evaluate the performance of defensive schemes based on real-world traffic traces.

We present an algorithm to self-heal reconfigurable networks. This algorithm reconfigures the network during an attack to protect two critical invariants. First, it insures that the network remains connected. Second, it insures that no node increases its degree by more than (log). We prove that our algorithm can successfully maintain these invariants even for large networks under massive attack by a computationally unbounded adversary.

Synthesis algorithms usually suffer from two factors of time and space complexity. In order to overcome the time complexity problem, several approaches have been proposed in the literature to incrementally properties to existing verified programs (e.g., [1]). In order to overcome the space explosion problem, recently, an increasing interest in parallel and distributed techniques has emerged in the model checking community (e.g., [2, 3]). Such techniques parallelize the state space of a given model over a network or cluster of workstations and run a distributed model checking algorithm over the parallelized state space. On the other hand, the space explosion problem is still unaddressed in the context of automated program synthesis.