Catálogo de publicaciones - libros

A tri-redundant version of a system is a system that is specified from as follows. First, system has the same number of processes and the same topology as system . Second, each variable in a process in system is replaced by three variables , , and in the corresponding process in system . Third, the actions in each process in system are modified before they are added to the corresponding process in system and some new actions are added to the corresponding process in system . In this paper, we show that a tri-redundant version of a system has interesting stabilization and fault-masking properties. In particular, we show that if is stabilizing, then is also stabilizing. We also show that if ever reaches stabilization, and then a “visible fault” occurs, then the effect of the fault is masked and the reached stabilization of remains in effect.

Consider a communication network where each process needs to securely exchange messages with its neighboring processes. In this network, each sent message is encrypted using one or more symmetric keys that are shared only between two processes: the process that sends the message and the neighboring process that receives the message. A straightforward scheme for assigning symmetric keys to the different processes in such a network is to assign each process () keys, where is the maximum number of neighbors of any process in the network. In this paper, we present a more efficient scheme for assigning symmetric keys to the different processes in a communication network. This scheme, which is referred to as logarithmic keying, assigns (log) symmetric keys to each process in the network. We show that logarithmic keying can be used in rich classes of communication networks that include star networks, acyclic networks, limited- cycle networks, and planar networks.

Peer-to-peer applications share files between users themselves rather than downloading files from file servers. Self-downloading protocols have the property that eventually, every user downloads only from other users. This paper considers efficient ways of dividing files into segments so that users can exit the system as soon as file downloading is complete. One vulnerability of file sharing between peers is the possibility that files or segments could be counterfeit or corrupt. Protocols that are -safe tolerate some number of instances of faulty segments in a file being downloaded, because each segment is downloaded times before being uploadable. It is shown that -safe self-downloading is possible for a sufficiently large arrival rate of users to the system. In addition, the paper presents upper and lower connectivity and sharing bounds for = 2.

One of the simplest protocols for clock synchronization in wireless ad hoc and sensor networks is the converge-to-max protocol, which has the simple logic of adjusting each node’s clock to be at least as large as any neighbor’s. This paper examines the converge-to-max protocol, showing it to be stabilizing even when node clocks have skew, bounded domains, and dynamic communication links.

We present a scheme that achieves self-stabilizing digital clock synchronization assuming a “synchronous” system. This synchronicity is established by the assumption of a common “beat” delivered with a regularity in the order of the network message delay, thus enabling the nodes to execute in lock-step. The system can be subjected to severe transient failures with a permanent presence of nodes. Our algorithm guarantees eventually synchronized digital clock counters, i.e. common increasing integer counters associated with each beat. We then show how to achieve regular clock synchronization, progressing at real-time rate and with high granularity, from the synchronized digital clock counters.

There is one previous self-stabilizing clock synchronization algorithm, which also converges in linear time (relying on an underlying pulse mechanism), but it requires to execute and terminate agreement in between consecutive pulses. Such a scheme, although it does not assume a synchronous system, cannot be easily transformed to a synchronous system in which the pulses (beats) are in the order of the message delay time apart. The only other digital clock synchronization algorithm operating in a similar synchronous model converges in expected exponential time. Our algorithm converges (deterministically) in linear time.

This paper develops a distributed algorithm to color the edges of a bipartite network in such a way that any two adjacent edges receive distinct colors. The algorithm has the self-stabilizing property. It works with an arbitrary initialization. Its execution model is assumed to be the central daemon, and its time complexity is () moves, where and are the number of nodes and the number of edges, respectively.

In this paper, we show that the use of diversified COTS servers allows to detect intrusions corresponding to unknown attacks. We present an architecture that ensures both confidentiality and integrity at the COTS server level and we extend it to enhance availability. Replication techniques implemented on top of agreement services are used to avoid any single point of failure. On the one hand we assume that COTS servers are complex softwares that contain some vulnerabilities and thus may exhibit arbitrary behaviors. While on the other hand other basic components of the proposed architecture are simple enough to be exhaustively verified. That’s why we assume that they can only suffer from crash failures. The whole system is assumed to be asynchronous and furthermore messages can be lost. In the particular case of Web servers connected to databases, we identify the properties that have to be maintained and the alarms that have to be raised. We describe in details how the different replicated levels interact together and, for each level, we precise the reasons that have led us to use a particular agreement service. Performance evaluations are conducted to measure the quality of service of the Intrusion Detection System (quantity of false positives and lack of false negatives) and the additional cost induced by the mechanisms used to ensure the availability of this secure architecture.

Wireless sensor networks (WSNs) comprised of low-cost devices tend to be unreliable, with failures a common phenomenon. Being able to accurately observe the network health status — of nodes of each type and links of each type — is essential to properly configure applications on WSN fabrics and to interpret the information collected from them.

In this paper we study accurate network health monitoring in WSNs. Specifically, we reconsider the well-known problem of message-passing rooted spanning tree construction and its use in PIF (propagation of information with feedback) for the case of a WSN. We present a stabilizing protocol, Chowkidar, that is initiated upon demand; that is, it does not involve ongoing maintenance, and it terminates with accurate results, including detection of failure and restart during the monitoring process. Our protocol is distinguished from others in two important ways. Given the resource constraints of WSNs, it is message-efficient in that it uses only a few messages per node. And it tolerates ongoing node and link failure and node restart, in contrast to requiring that faults stop during convergence.

We have implemented the protocol as part of enabling a network health status service that is tightly integrated with a remotely accessible wireless sensor network testbed, Kansei, at The Ohio State University. We report on experimental results.

Embedded distributed systems have become an integral part of safety-critical computing applications, necessitating system designs that incorporate fault tolerant clock synchronization in order to achieve ultra-reliable assurance levels. Many efficient clock synchronization protocols do not, however, address Byzantine failures, and most protocols that do tolerate Byzantine failures do not self-stabilize. Of the Byzantine self-stabilizing clock synchronization algorithms that exist in the literature, they are based on either unjustifiably strong assumptions about initial synchrony of the nodes or on the existence of a common pulse at the nodes. The Byzantine self-stabilizing clock synchronization protocol presented here does not rely on any assumptions about the initial state of the clocks. Furthermore, there is neither a central clock nor an externally generated pulse system. The proposed protocol converges deterministically, is scalable, and self-stabilizes in a short amount of time. The convergence time is linear with respect to the self-stabilization period. Proofs of the correctness of the protocol as well as the results of formal verification efforts are reported.

The -packing problem asks for a subset of the nodes in a graph such that the distance between any pair of nodes in is greater than . This problem has applications to placing facilities in a network.

In the current paper we present a self-stabilizing algorithm for computing a maximal -packing in a general graph. Our algorithm uses a constant number of variables per node. This improves the memory requirement compared to the previous most memory efficient algorithm [9] which used variables per node. In addition the presented algorithm is very short and simple.