Catálogo de publicaciones - libros

Grid monitoring systems collect a substantial amount of information on the infrastructure’s status in order to perform various tasks, more commonly to provide a better use of the grid’s entities. Modern computational and data grids have become very complex by their size, their heterogeneity, their interconnection. Monitoring systems as any other grid’s tools have to adapt to this evolution. In this paper we present a decentralized, scalable, and autonomous grid monitoring system able to tackle the growths of scale and complexity. System’s components communications are hierarchically organized on a peer-to-peer overlay network. Fresh information is efficiently propagated thanks to an gossip protocol that limits the number of message. Automation of key management operations eases system administration and maintenance. This approach provides scalability and adaptability. The main properties of our application are presented and discussed. Performance measurements confirm the efficiency of our system.

The deferred update technique is a widely used approach for building replicated database systems. Its fame stems from the fact that read-only transactions can execute locally to any single database replica, providing good performance for workloads where transactions are mostly of this type. In this paper, we analyze the deferred update technique and show a number of characteristics and limitations common to any replication protocol based on it. Previous works on this replication method usually start from a protocol and then argue separately that it is based on the deferred update technique and satisfies serializability. Differently, ours starts from the abstract definition of a serializable database and gradually changes it into an abstract deferred update protocol. In doing that, we can formally characterize the deferred update technique and rigorously prove its properties. Moreover, our specification can be extended to create new protocols or used to prove existing ones correct.

is an important application category in cyber-physical systems, and is a good canonical example of this application class. Such applications are interactive, dynamic, stream-based, computationally demanding, and needing real-time or near real-time guarantees. A control loop characterizes the behavior of this application class. ASAP is a scalable distributed architecture for a multi-modal sensor network that caters to the needs of this application class. Features of this architecture include (a) generation of cues that allow the infrastructure to pay to data streams of interest; (b) abstraction that allows easy integration of multi-modal sensing capabilities; and (c) dynamic redirection of sensor sources to distributed resources to deal with sudden burstiness in the application. In both empirical and emulated experiments, ASAP shows that it scales up to a thousand of sensor nodes (comprised of high bandwidth cameras and low bandwidth RFID readers), significantly mitigates infrastructure and cognitive overload, and reduces and due to its ability to integrate multi-modal sensing.

We consider the following abstraction of recommendation systems. There are players and objects, and each player has an arbitrary binary preference grade (“likes” or “dislikes”) for each object. The preferences are unknown at start. A player can find his grade for an object by “probing” it, but each probe incurs cost. The goal of a recommendation algorithm is to find the preferences of the players while minimizing cost. To save on cost, players post the results of their probes on a public “billboard” (writing and reading from the billboard is free). In asynchronous systems, an adversary controls the order in which players probe. Active algorithms get to tell players which objects to probe when they are scheduled. In this paper we present the first low-overhead algorithms that can provably reconstruct the preferences of players under asynchronous scheduling. “Low overhead” means that the probing cost is only a polylogarithmic factor over the best possible cost; and by “provably” we mean that the algorithm works with high probability (over internal coin tosses) for all inputs, assuming that each player gets some minimal number of probing opportunities. We present algorithms in this model for exact and approximate preference reconstruction.

This report describes a necessary and sufficient test for the schedulability of a set of sporadic hard-deadline tasks on a multiprocessor platform, using any of a variety of scheduling policies including global fixed task-priority and earliest-deadline-first (EDF). The contribution is to establish an upper bound on the computational complexity of this problem, for which no algorithm has yet been described. The compute time and storage complexity of the algorithm, which performs an exhaustive search of a very large state space, make it practical only for tasks sets with very small integer periods. However, as a research tool, it can provide a clearer picture than has been previously available of the real success rates of global preemptive priority scheduling policies and low-complexity sufficient tests of schedulability.

This paper tackles the consensus problem in asynchronous systems prone to byzantine failures. One way to circumvent the FLP impossibility result consists in adding synchrony assumptions (deterministic solution). In the context of crash failures (at most processes may crash), the weakest partially synchronous system model assumes at least one correct process with outgoing links that eventually permit a bounded transmission delay with at least neighbors (the set of neighbors may change over time).

Aguilera et al. provided the main result for systems where at most processes may exhibit a byzantine behavior. They assume a correct process with all its outgoing and incoming links eventually timely. This paper considers a system model with at least one correct process connected with privileged neighbors with eventually timely outgoing and incoming links. In this system model, a byzantine consensus protocol is proposed. It uses authentication and assumes  ≥ 2.

We consider the problem of synchronizing clocks in synchronous systems prone to transient and dynamic process failures, i.e., we consider systems where all processes may alternate correct and Byzantine behaviors. We propose a clock synchronization algorithm based on periodical resynchronizations which is based on the assumption that no more than  < /3 processes (with the number of processors in the system) are simultaneously faulty. Both, accuracy (clocks being within a linear envelope of real-time) and precision (maximum deviation between clocks) perpetually hold for processes which sufficiently long follow their algorithm. We provide expressions for both the recovery time and the failure turn-over rates. Both expressions are independent of , and are less than the time needed to execute 3 resynchronizations.

We consider the problem of exploring an anonymous unoriented ring by a team of identical, oblivious, asynchronous mobile robots that can view the environment but cannot communicate. This weak scenario is standard when the spatial universe in which the robots operate is the two-dimentional plane, but (with one exception) has not been investigated before. We indeed show that, although the lack of these capabilities renders the problems considerably more difficult, ring exploration is still possible.

We show that the minimum number () of robots that can explore a ring of size is (log) and that () = (log) for arbitrarily large . On one hand we give an algorithm that explores the ring starting from any initial configuration, provided that and are co-prime, and we show that there always exist such in (log). On the other hand we show that (log) agents are necessary for arbitrarily large . Notice that, when and are not co-prime, the problem is sometimes unsolvable (i.e., there are initial configurations for which the exploration cannot be done). This is the case, e.g., when divides .

In Sensor Networks, the lack of topology information and the availability of only one communication channel has led research work to the use of randomization to deal with collision of transmissions. However, the scarcest resource in this setting is the energy supply, and radio communication dominates the sensor node energy consumption. Hence, redundant trials of transmission as used in randomized protocols may be counter-effective. Additionally, most of the research work in Sensor Networks is either heuristic or includes unreallistic assumptions. Hence, provable results for many basic problems still remain to be given. In this paper, we study upper and lower bounds for deterministic communication primitives under the harsh constraints of sensor nodes.

We address the Leader Election (LE) problem in networks of anonymous sensors sharing no kind of common coordinate system. The contribution of this paper is twofold: First, assuming anonymous sensors agreeing on a common () of their own coordinate system, we provide a complete characterization on the sensors positions to deterministically elect a leader. Our result holds for any  > 1, even if the sensors have unlimited visibility and regardless of their capabilities, unbounded memory, mobility, and communication settings. Second, we show that this statement also holds assuming sensors without chirality provided that is odd.