Catálogo de publicaciones - libros

The paper considers broadcasting protocols in radio networks with known topology that are efficient in both time and energy. The radio network is modelled as an undirected graph  = (,) where || = . It is assumed that during execution of the communication task every node in is allowed to transmit at most once. Under this assumption it is shown that any radio broadcast protocol requires transmission rounds, where is the diameter of . This lower bound is complemented with an efficient construction of a deterministic protocol that accomplishes broadcasting in rounds. Moreover, if we allow each node to transmit at most times, the lower bound  + (( − )) on the number of transmission rounds holds. We also provide a randomised protocol that accomplishes broadcasting in  + (log) rounds. The paper concludes with a discussion of several other strategies for energy efficient radio broadcasting and a number of open problems in the area.

Communication in networks suffers if a link fails. When the links are edges of a tree that has been chosen from an underlying graph of all possible links, a broken link even disconnects the network. Most often, the link is restored rapidly. A good policy to deal with this sort of link failures is , where the temporarily broken link is replaced by a single link from the underlying graph. A rapid replacement of a broken link by a swap link is only possible if all swap links have been precomputed. The selection of high quality swap links is essential; it must follow the same objective as the originally chosen communication subnetwork. We are interested in a minimum diameter tree in a graph with edge weights (so as to minimize the maximum travel time of messages). Hence, each swap link must minimize (among all possible swaps) the diameter of the tree that results from swapping. We propose a distributed algorithm that efficiently computes all of these swap links, and we explain how to route messages across swap edges with a compact routing scheme.

Many recommend planning for the worst and hoping for the best. In this paper we devise indulgent consensus algorithms that can tolerate crash failures and arbitrarily long periods of asynchrony, and yet perform (asymptotically) optimally in well-behaved, synchronous executions with few failures. We present two such algorithms: In synchronous executions, the first has , using only () messages, but runs in superlinear time of (). The second has a message complexity of , but has an optimal running time, completing in () rounds in synchronous executions with at most failures. Both of these results improve significantly over the most message-efficient of previous indulgent consensus algorithms which have a message complexity of at least () in well-behaved executions.

Let consider autonomous mobile robots that can move in a two dimensional plane. The gathering problem is one of the most fundamental tasks of autonomous mobile robots. In short, given a set of robots with arbitrary initial locations, gathering must make all robots meet in finite time at a point that is not predefined. In this paper, we study about the feasibility of gathering by mobile robots that have . While the direction of each local coordinate system is fixed in usual systems, the dynamic compass model allows the angle difference between a local coordinate system and the global coordinate system to vary with time in the range of [0, ]. This paper proposes a semi-synchronous gathering algorithm for robots with (/2 − )-absolute error dynamic compasses, where is an arbitrary small constant larger than zero. To the best of our knowledge, the proposed algorithm is the first one that considers both inaccurate compass models and more than two robots. We also show the optimality of our algorithm. It is proved that for any  ≥ /2, there is no algorithm to gather two robots with -absolute error dynamic compasses.

This paper presents an efficient scheme maintaining a in dynamic trees using asymptotically optimal labels. In order to maintain the short labels, the scheme uses relatively low message complexity. In particular, if the initial dynamic tree contains just the root, then the scheme incurs an (log) amortized message complexity per topology change, where is the current number of nodes in the tree. As a separator decomposition is a fundamental decomposition of trees used extensively as a component in many static graph algorithms, our dynamic scheme for separator decomposition may be used for constructing dynamic versions to these algorithms.

The paper then shows how to use our dynamic separator decomposition to construct rather efficient labeling schemes on dynamic trees, using the same message complexity as our dynamic separator scheme. Specifically, we construct efficient routing schemes on dynamic trees, for both the designer and the adversary port models, which maintain optimal labels, up to a multiplicative factor of (loglog). In addition, it is shown how to use our dynamic separator decomposition scheme to construct dynamic labeling schemes supporting the ancestry and NCA relations using asymptotically optimal labels, as well as to extend a known result on dynamic distance labeling schemes.

We study the impact of faulty processors on the communication cost of distributed algorithms in a message-passing model. The system is synchronous but prone to various kinds of processor failures: crashes, message omissions, (authenticated) Byzantine faults. One of the basic communication tasks, called , or for short, is to exchange the initial values among all non-faulty processors. In this paper we address the question if there is a gossip algorithm which is both fault-tolerant, fast and communication-efficient? We answer this question in affirmative in the model allowing only crash failures, and in some sense negatively when the other kinds of failures may occur. More precisely, in an execution by processors when of them are faulty, each non-faulty processor contributes a constant to the message complexity, each crashed processor contributes () (> 0 could be an arbitrarily small constant independent from , but dependent on the algorithm), each omission (or authenticated Byzantine) processor contributes (), and each—even potential—Byzantine failure results in additional () messages sent.

Consider a network whose inputs change rapidly, or are subject to frequent faults. This is expected often to be the case in the foreseen huge sensor networks. Suppose, that an algorithm is required to output the majority value of the inputs. To address such networks, it is desirable to be able to stabilize the output fast, and to give guarantees on the outputs even before stabilization, even if additional changes occur.

We bound the of the outputs (the number of times the output changes) of majority consensus algorithms even before the final stabilization. We show that the instability can be traded off with their (how fast they are required to stabilize the output if faults occurred). First, for the extreme point of the trade-off, we achieve instability that is optimal for the class of algorithms that are optimal in their output time adaptivity. This is done for various known versions of majority consensus problem. The optimal instability for this case is (log) and is shown to be (log) for most versions and (log) in some cases. Previous such algorithms did not have such a guarantee on the behaviour of the output before its final stabilization (and their instability was ()). We also explain how to adapt the results for other points in the trade off.

The output stabilization in previous algorithms was adaptive only if the faults ceased for () time. An additional result in this paper uses adaptations of some previous tools, as well as the new tools developed here for bounding the instability, in order to remove this limitation that is undesirable when changes are frequent.

Weak fairness guarantees that continuously enabled actions are executed infinitely often. Strong fairness, on the other hand, guarantees that actions that are enabled infinitely often (but not necessarily continuously) are executed infinitely often. In this paper, we present a distributed algorithm for scheduling actions for execution. Assuming weak fairness for the execution of this algorithm, the schedule it provides is strongly fair. Furthermore, this algorithm is maximal in that it is capable of generating strongly fair schedule. This algorithm is the first strongly-fair scheduling algorithm that is both distributed and maximal.

We study replacement algorithms for non-uniform access caches that are used in distributed storage systems. Considering access latencies as major costs of data management in such a system, we show that the total cost of any replacement algorithm is bounded by plus the total cost of the optimal off-line algorithm (OPT). We propose two off-line heuristics: MIN- and MIN-cod, as well as an on-line algorithm: HD-cod, which can be run efficiently and perform well at the same time.

Our simulation results with Storage Performance Council (SPC)’s storage server traces show that: (1) for off-line workloads, MIN-cod performs as well as OPT in some cases, all is at most three times worse in all test case; (2) for on-line workloads, HD-cod performs closely to the best algorithms in all cases, and is the single algorithm that performs well in all test cases, including the optimal on-line algorithm (Landlord). Our study suggests that the essential issue to be considered be the trade-off between the costs of victim blocks and the total number of evictions in order to effectively optimize both efficiency and performance of distributed storage cache replacement algorithms.

In contrast to peer-to-peer file sharing, live streaming based on peer-to-peer technology is still awaiting its breakthrough. This may be due to the additional challenges live streaming faces, e.g., the need to meet real-time playback deadlines, or the increased demands on robustness under churn. This paper presents and evaluates novel neighbor selection and data distribution schemes for peer-to-peer live streaming. Concretely, in order to distribute data efficiently and with minimal delay, our algorithms combine low-latency push operations along a structured overlay with the flexibility of pull operations. The protocols ensure that all peers are able to obtain the required data blocks of a live stream in time, and that due to the loop-free dissemination paths, the overhead is low.