Catálogo de publicaciones - libros

Global state snapshots are a fundamental primitive for wireless networks that sense and control real environments. Consistent and timely snapshots are potentially costly. Cost reduction is often realized by gathering only a “delta” from previous snapshots. In this paper, we explore an alternative form of efficiency by generalizing the notion of a snapshot to satisfy properties, wherein the state of nearby nodes is available with greater resolution, speed, and frequency than that of farther away nodes. Our algorithms are memory efficient and do not require global time synchronization or localization.

For pedagogical reasons, we describe our solutions for the case of perfect 2-d grid topologies first, and then show how to extend them for higher dimensions, for network with irregular density, arbitrary sized holes, networks and non unit disk radios. We also discuss how different control applications can exploit these generalized snapshots.

We consider the distributed construction of a minimum weight 2-edge-connected spanning subgraph (2-ECSS) of a given weighted or unweighted graph. A 2-ECSS of a graph is a subgraph that, for each pair of vertices, contains at least two edge-disjoint paths connecting these vertices. The problem of finding a minimum weight 2-ECSS is NP-hard and a natural extension of the distributed MST construction problem, one of the most fundamental problems in the area of distributed computation. We present a distributed -approximation algorithm for the unweighted 2-ECSS construction problem that requires ( ) communication rounds and ( ) messages. Moreover, we present a distributed 3 -approximation algorithm for the weighted 2-ECSS construction problem that requires ( log ) communication rounds and ( log +  ) messages.

Wireless embedded sensor networks are predicted to provide attractive application possibilities in industry as well as at home. IEEE 802.15.4 and ZigBee are proposed as standards for such networks with a particular focus on pairing reliability with energy efficiency, while sacrificing high data rates.

IEEE 802.15.4 is configurable in many aspects, including the synchronicity of the communication, and the periodicity in which battery-powered sensors need to wake up to communicate. This paper develops a formal behavioral model for the energy implications of these options. The model is modularly specified using the language , which has an operational semantics mapping on stochastic timed automata. The latter are simulated using a variant of discrete-event simulation implemented in the tool . We obtain estimated energy consumptions of a number of possible communication scenarios in accordance with the standards, and derive conclusions about the energy-optimal configuration of such networks. As a specific fine point, we investigate the effects of drifting clocks on the energy behavior of various application scenarios.

Considering an asynchronous system made up of processes and where up to of them can crash, finding the weakest assumptions that such a system has to satisfy for a common leader to be eventually elected is one of the holy grail quests of fault-tolerant asynchronous computing. This paper is a step in such a quest. It has two main contributions. First, it proposes an asynchronous system model, in which an eventual leader can be elected, that is weaker and more general than previous models. This model is captured by the notion of . An is a set of  + 1 processes: a process (the center of the star) plus a set of processes (the points of the star). Intuitively, assuming logical times (round numbers), the assumption means that there are a process , a subset of the round numbers , and associated sets () such that each set {} ∪ () is a -star centered at , and each process of () receives from a message tagged in a timely manner or among the first ( − ) messages tagged it ever receives. The star is called because the set () is allowed to change with . It is called because the star can disappear during finite periods. This assumption, not only combines, but generalizes several synchrony and time-free assumptions that have been previously proposed to elect an eventual leader (e.g., eventual -source, eventual -moving source, message pattern assumption). Each of these assumptions appears as a particular case of the assumption. The second contribution of the paper is an algorithm that eventually elects a common leader in any system that satisfies the assumption. That algorithm enjoys, among others, two noteworthy properties. Firstly, from a design point of view, it is simple. Secondly, from a cost point of view, only the round numbers can increase without bound. This means that, be the execution finite or infinite, be links timely or not (or have the corresponding sender crashed or not), all the other local variables (including the timers) and message fields have a finite domain.

The multiprocessor Deadline-Monotonic scheduling of sporadic task systems is studied. A new sufficient schedulability test is presented and proved correct. It is shown that this test offers non-trivial quantitative guarantees, including a processor speedup bound.

is a thread library entirely based on lock-free methods, i.e. no spin-locks or similar synchronization mechanisms are employed in the implementation of the multithreading. Since lock-freedom is highly desirable in multiprocessors/multicores due to its advantages in parallelism, fault-tolerance, convoy-avoidance and more, there is an increased demand in lock-free methods in parallel applications, hence also in multiprocessor/multicore system services. This is why a lock-free multithreading library is important. To the best of our knowledge is the first thread library that provides a lock-free implementation of blocking synchronization primitives for application threads. Lock-free implementation of objects with blocking semantics may sound like a contradicting goal. However, such objects have benefits: e.g. library operations that block and unblock threads on the same synchronization object can make progress in parallel while maintaining the desired thread-level semantics and without having to wait for any “slow” operations among them. Besides, as no spin-locks or similar synchronization mechanisms are employed, processors are always able to do useful work. As a consequence, applications, too, can enjoy enhanced parallelism and fault-tolerance. The synchronization in is achieved by a new method, which we call (RHO), that does not need any special kernel support.

We present a novel translation of systems that are tolerant of crash failures to systems that are tolerant of Byzantine failures in an asynchronous environment, making weaker assumptions than previous approaches. In particular, we assume little about how the application is coded. The translation exploits an extension of the Srikanth-Toueg protocol, supporting ordering in addition to authentication and persistent delivery. We illustrate the approach by synthesizing a version of the Castro and Liskov Practical Byzantine Replication protocol from the Oki and Liskov Viewstamped Replication protocol.

We consider static ad-hoc wireless networks where nodes have the same initial battery charge and they may dynamically change their transmission range at every time slot. When a node transmits with range (), its battery charge is decreased by ×() where > 0 is a fixed constant.

The goal is to provide a range assignment schedule that maximizes the number of broadcast operations from a given source (this number is denoted as the of the schedule). This maximization problem, denoted as , is known to be -hard and the best algorithm yields worst-case approximation ratio (log), where is the number of nodes of the network [5].

We consider instances formed by selecting points independently and uniformly at random from a square of side length in the Euclidean plane.

We first present an efficient algorithm that constructs a range assignment schedule having length, with high probability, not smaller than 1/12 of the optimum.

We then design an efficient distributed version of the above algorithm where nodes initially know and their own position only. The resulting schedule guarantees the same approximation ratio achieved by the centralized version thus obtaining the first distributed algorithm having performance for this problem.

Objects like queue, swap, and test-and-set allow two processes to reach consensus, and are consequently “universal” for a system of two processes. But are there deterministic objects that do not solve 2-process consensus, and nevertheless allow two processes to solve a task that is not otherwise wait-free solvable in read-write shared memory?

The answer “no” is a simple corollary of the main result of this paper: Let be a deterministic object such that no protocol solves consensus among  + 1 processes using copies of and read-write registers. If a task is wait-free solvable by  + 1 processes using read-write shared-memory and copies of , then is also wait-free solvable when copies of are replaced with -consensus objects. Thus, from the task-solvability perspective, -consensus is the second strongest object (after ( + 1)-consensus) in deterministic shared memory systems of  + 1 processes, i.e., there is a distinct gap between - and ( + 1)-consensus.

We derive this result by showing that any ( + 1)-process protocol that uses objects can be emulated using only -consensus objects. The resulting emulation is non-blocking and relies on an knowledge of . The emulation technique is another important contribution of this paper.

We investigate the complexity of searching for a given vertex in a scale-free graph, using only locally gathered information. In such graphs, the number of nodes of degree is proportional to for some constant > 0. We consider two random scale-free graph models: the Chung-Lu model and the Móri model (a generalization of the Barabási-Albert model) proving two lower bounds of ( / log) and () on the expected time to find the worst-case target, under a restrictive model of local information.