Catálogo de publicaciones - libros

A group of identical mobile agents moving asynchronously among the nodes of an anonymous network have to gather together in a single node of the graph. This problem known as the (asynchronous anonymous multi-agent) rendezvous problem has been studied extensively but only for networks that are safe or fault-free. In this paper, we consider the case when some of the edges in the network are dangerous or faulty such that any agent travelling along one of these edges would be destroyed. The objective is to minimize the number of agents that are destroyed and achieve rendezvous of all the surviving agents. We determine under what conditions this is possible and present algorithms for achieving rendezvous in such cases. Our algorithms are for arbitrary networks with an arbitrary number of dangerous channels; thus our model is a generalization of the case where all the dangerous channels lead to single node, called the . We do not assume prior knowledge of the network topology; In fact, we show that knowledge of only a “tight” bound on the network size is sufficient for solving the problem, whenever it is solvable.

In this paper, we propose the partition approach and define several new classes of partitioned failure detectors weaker than existing failure detectors for the -set agreement problem in both the shared-memory model and the message-passing model. In the shared-memory model with  + 1 processes, for any 2 ≤  ≤ , we first propose a partitioned failure detector that solves -set agreement with shared read/write registers and is strictly weaker than , which was conjectured to be the weakest failure detector for -set agreement in the shared-memory model [19]. We then propose a series of partitioned failure detectors that can solve -set agreement, yet they are strictly weaker than  [10], the weakest failure detector ever found before our work to circumvent any asynchronous impossible problems in the shared-memory model. We also define two new families of partitioned failure detectors in the message-passing model that are strictly weaker than the existing ones for -set agreement. Our results demonstrate that the partition approach opens a new dimension for weakening failure detectors related to set agreement, and it is an effective approach to check whether a failure detector is the weakest one or not for set agreement. So far, all previous candidates for the weakest failure detectors of set agreement have been disproved by the partitioned failure detectors.

Distributed storage algorithms implement the abstraction of a shared register over distributed base objects. We study a specific class of storage algorithms, which we call : these have the pragmatic property that old values written in the implemented register might be eventually forgotten, i.e., they are not permanently kept in the storage and might be overwritten in the base objects by more recent values. This paper precisely captures this property and argues that most storage algorithms are amnesic. We establish a fundamental impossibility of an amnesic storage algorithm to implement a robust register abstraction over a set of base objects of which at least one can fail arbitrarily, even if only in a responsive manner, unless readers are allowed to write to the base objects. Our impossibility helps justify the assumptions made by practical robust storage algorithms. We also derive from this impossibility the first sharp distinction between and registers. Namely, we show that, if readers do not write, then no amnesic algorithm can implement a regular register using safe registers.

We give a distributed approximation algorithm for the vertex-packing problem in unit-disk graphs. Given a graph , the algorithm finds in a unit-disk graph a collection of pairwise disjoint copies of of size which is approximately equal to the packing number of in . The algorithm is deterministic and runs in a poly-logarithmic number of rounds in the message passing model.

This paper studies the impact of omission failures on asynchronous distributed systems with crash-stop failures. We provide two different transformations for algorithms, failure detectors, and problem specifications, one of which is weakest failure detector preserving. We prove that our transformation of failure detector [1] is the weakest failure detector for consensus in environments with crash-stop and permanent omission failures and a majority of correct processes. Our results help to use the power of the well-understood crash-stop model to automatically derive solutions for the general omission model, which has recently raised interest for being noticeably applicable for security problems in distributed environments equipped with security modules such as smartcards [2,3,4].

The paper presents a deterministic distributed algorithm that given an node unweighted graph constructs an () edge 3-spanner for it in (log) time. This algorithm is then extended into a deterministic algorithm for computing an () edge ()-spanner in 2log time for every integer parameter . This establishes that the problem of the deterministic construction of a linear (in ) stretch spanner with few edges can be solved in the distributed setting in polylogarithmic time.

The paper also investigates the distributed construction of sparse spanners with almost pure additive stretch (1 + ,), i.e., such that the distance in the spanner is at most 1 +  times the original distance plus . It is shown, for every > 0, that in (log) time one can deterministically construct a spanner with () edges that is both a 3-spanner and a (1 + ,8log)-spanner. Furthermore, it is shown that in time one can deterministically construct a spanner with () edges which is both a 3-spanner and a (1 + ,4)-spanner. This algorithm can be transformed into a Las Vegas randomized algorithm with guarantees on the stretch and time, running in ( + log) expected time.

Consider a distributed network of nodes that is connected to a global source of “beats”. All nodes receive the “beats” simultaneously, and operate in lock-step. A scheme that produces a “pulse” every beats is shown. That is, the nodes agree on “special beats”, which are spaced beats apart. Given such a scheme, a clock synchronization algorithm is built. The “pulsing” scheme is self-stabilized despite any transient faults and the continuous presence of up to nodes. Therefore, the clock synchronization built on top of the “pulse” is highly fault tolerant. In addition, a highly fault tolerant general stabilizer algorithm is constructed on top of the “pulse” mechanism.

Previous clock synchronization solutions, operating in the exact same model as this one, either support and converge in linear time, or support and have that also depends on the value of (the clock wrap around value). The proposed scheme combines the best of both worlds: it converges in that is independent of and is tolerant to up to nodes. Moreover, considering problems in a self-stabilizing, tolerant environment that require nodes to know the global state (clock synchronization, token circulation, agreement, etc.), the work presented here is the first protocol to operate in a network that is not fully connected.

We study oblivious deterministic gossip algorithms for multi-channel radio networks with a malicious adversary. In a multi-channel network, each of the processes in the system must choose, in each round, one of the channels of the system on which to participate. Assuming the adversary can disrupt one channel per round, preventing communication on that channel, we establish a tight bound of on the number of rounds needed to solve the -gossip problem, a parameterized generalization of the all-to-all gossip problem that requires (1 − ) of the “rumors” to be successfully disseminated. Underlying our lower bound proof lies an interesting connection between -gossip and extremal graph theory. Specifically, we make use of Turán’s theorem, a seminal result in extremal combinatorics, to reason about an adversary’s optimal strategy for disrupting an algorithm of a given duration. We then show how to generalize our upper bound to cope with an adversary that can simultaneously disrupt  <  channels. Our generalization makes use of selectors: a combinatorial tool that guarantees that any subset of processes will be “selected” by some set in the selector. We prove this generalized algorithm optimal if a maximum number of values is to be gossiped. We conclude by extending our algorithm to tolerate traditional Byzantine corruption faults.

The timestamp problem captures a fundamental aspect of asynchronous distributed computing. It allows processes to label events throughout the system with timestamps that provide information about the real-time ordering of those events. We consider the space complexity of wait-free implementations of timestamps from shared read-write registers in a system of processes.

We prove an lower bound on the number of registers required. If the timestamps are elements of a nowhere dense set, for example the integers, we prove a stronger, and tight, lower bound of . However, if timestamps are not from a nowhere dense set, this bound can be beaten; we give an algorithm that uses  − 1 (single-writer) registers.

We also consider the special case of anonymous algorithms, where processes do not have unique identifiers. We prove anonymous timestamp algorithms require registers. We give an algorithm to prove that this lower bound is tight. This is the first anonymous algorithm that uses a finite number of registers. Although this algorithm is wait-free, its step complexity is not bounded. We also present an algorithm that uses () registers and has bounded step complexity.

We study adaptive routing algorithms in a round-based model. Suppose we are given a network equipped with load-dependent latency functions on the edges and a set of commodities each of which is defined by a collection of paths (represented by a DAG) and a flow rate. Each commodity is controlled by an agent which aims at balancing its traffic among its paths such that all used paths have the same latency. Such an allocation is called a Wardrop equilibrium.

In recent work, it was shown that an infinite population of users each of which carries an infinitesimal amount of traffic can attain approximate equilibria in a distributed and concurrent fashion quickly. Interestingly, the convergence time is independent of the underlying graph and depends only mildly on the latency functions. Unfortunately, a direct simulation of this process requires to maintain an exponential number of variables, one for each path.

The focus of this work lies on the distributed and efficient computation of the adaptation rules by a finite number of agents. In order to guarantee a polynomial running time, every agent computes a randomised path decomposition in every communication round. Based on this decomposition, agents remove flow from paths with high latency and reassign it proportionally to all paths. This way, our algorithm can handle exponentially large path collections in polynomial time.