Catálogo de publicaciones - libros

A fast self-stabilizing algorithm is described to rapidly construct a balanced overlay network from a directed graph initially with out-degree 1, a natural starting case that arises in peer-to-peer systems where each node attempts to join by contacting some single other node. This algorithm constructs a balanced search tree in time ( + log), where is the key length and is the number of nodes, improving by a factor of log on the previous bound starting from a general graph, while retaining the properties of low contention and short messages. Our construction includes an improved version of the distributed Patricia tree structure of Angluin  [1], which we call a . This data structure responds gracefully to node failures and supports search, predecessor, and successor operations in () time with smoothly distributed load for predecessor and successor operations. Though the resulting tree data structure is highly vulnerable to disconnection due to failures, the fast predecessor and successor operations (as shown in previous work) can be used to quickly construct standard overlay networks with more redundancy.

Self-stabilization is a versatile technique to withstand any transient fault in a distributed system. Mobile robots (or agents) are one of the emerging trends in distributed computing as they mimic autonomous biologic entities. The contribution of this paper is threefold. First, we present a new model for studying mobile entities in networks subject to transient faults. Our model differs from the classical robot model because robots have constraints about the paths they are allowed to follow, and from the classical agent model because the number of agents remains fixed throughout the execution of the protocol. Second, in this model, we study the possibility of designing self-stabilizing algorithms when those algorithms are run by mobile robots (or agents) evolving on a graph. We concentrate on the core building blocks of robot and agents problems: naming and leader election. Not surprisingly, when no constraints are given on the network graph topology and local execution model, both problems are impossible to solve. Finally, using minimal hypothesis with respect to impossibility results, we provide deterministic and probabilistic solutions to both problems, and show equivalence of these problems by an algorithmic reduction mechanism.

Peer to peer overlay networks have proven to be a good support for storing and retrieving data in a fully decentralized way. A sound approach is to structure them in such a way that they reflect the structure of the application. Peers represent objects of the application so that neighbours in the peer to peer network are objects having similar characteristics from the application’s point of view. Such structured peer to peer overlay networks provide a natural support for range queries. While some complex structures such as a Voronoï tessellation, where each peer is associated to a cell in the space, are clearly relevant to structure the objects, the associated cost to compute and maintain these structures is usually extremely high for dimensions larger than 2.

We argue that an approximation of a complex structure is enough to provide a native support of range queries. This stems from the fact that neighbours are important while the space partitioning associated to a given peer is not as crucial. In this paper, we present the design, analysis and evaluation of RayNet, a loosely structured Voronoï-based overlay network. RayNet organizes peers in an approximation of a Voronoï tessellation in a fully decentralized way. It relies on a Monte-Carlo algorithm to estimate the size of a cell and on an epidemic protocol to discover neighbours. In order to ensure efficient (polylogarithmic) routing, RayNet is inspired from the Kleinberg’s small world model where each peer gets connected to close neighbours (its approximate Voronoï neighbours in Raynet) and shortcuts, long range neighbours, implemented using an existing Kleinberg-like peer sampling.

We study private computations in a system of tiny mobile agents. We consider the mobile population protocol model of Angluin [2] and ask what can be computed without ever revealing any input to a curious adversary. We show that any computable predicate of the original population model can be made private through an obfuscation procedure that exploits the inherent non-determinism of the mobility pattern. In short, the idea is for every mobile agent to generate, besides its actual input value, a set of wrong input values to confuse the curious adversary. To converge to the correct result, the procedure has the agents eventually eliminate the wrong values; however, the moment when this happens is hidden from the adversary. This is achieved without jeopardizing the tiny nature of the agents: they still have very small storage size that is independent of the cardinality of the system. We present three variants of this obfuscation procedure that help compute respectively, , , and predicates which, when composed, cover all those that can be computed in the population protocol model.

Network overlays have been the subject of intensive research in recent years. The paper presents an overlay structure, , that is self-stabilizing and is robust against permanent Byzantine faults. The overlay structure has a logarithmic diameter with high probability, which matches the diameter of less robust overlays. The overlay can withstand high churn without affecting the ability of active and correct members to disseminate their messages. The construction uses a randomized technique to choose the neighbors of each member, while limiting the ability of Byzantine members to affect the randomization or to disturb the construction. The basic ideas generalize the original construction that withstands Byzantine failures but was not self-stabilizing.

We consider the parallel simulation of distributed systems based upon the notion of separability. We define a model of distributed systems that integrates a limited set of temporal properties, from which we deduce specific parallel simulation strategies avoiding rollback and dynamic scheduling which are often necessary to obtain an optimal rate of parallelism in parallel and/or distributed simulations. In particular, we present strategies that enable to compute the simulation schedule in advance, or even statically.

This approach appears to be relevant for a large class of distributed computations, inasmuch as it relies upon a limited set of temporal properties of the simulated systems.

In small-world networks, each peer is connected to its closest neighbors in the network topology, as well as to additional long-range contact(s), also called shortcut(s). In 2000, Kleinberg provided asymptotic lower bounds on routing performances and showed that greedy routing in an -peer small-world network performs in steps when the distance to shortcuts is chosen uniformly at random, and in (log) when the distance to shortcuts is chosen according to a harmonic distribution in a -dimensional mesh. Yet, we observe through experimental results that peer to peer gossip-based protocols achieving small-world topologies where shortcuts are randomly chosen, perform reasonably well in practice.

Kleinberg results are relevant for extremely large systems while systems considered in practice are usually of smaller size (they are typically made up of less than one million of peers). This paper explores the impact of Kleinberg results in the context of practical systems and small-world networks. More precisely, based on the observation that, despite the fact that the routing complexity of gossip-based small-world overlay networks is not polylogarithmic (as proved by Kleinberg), this type of networks ultimately provide reasonable results in practice. This leads us to think that the asymptotic big () complexity alone might not always be sufficient to assess the practicality of a system whose size is typically smaller that what the one theory targets. The paper consequently proposes a refined routing complexity measure for small-world networks (namely, a recurrence formula that can be easily computed). Yet, given that Kleinberg proved that the distribution of shortcuts has a strong impact on the routing complexity (when extremely large networks are considered), arises the question of leveraging this result to improve upon current gossip-based protocols. We show that gossip-based protocols (designed for less than one million of peers) can benefit from a good approximation of Kleinberg-like small-world topologies (designed for extremely large networks). Along, are presented simulation results that demonstrate the relevance of the proposed approach.

This paper investigates whether the assumption of unique identifiers is essential for wait-free distributed computing using shared objects of various types. Algorithms where all processes are programmed identically and do not use unique identifiers are called anonymous. We study the anonymous solvability of two key problems, consensus and naming. These problems are used to define measures of a type ’s power to solve problems anonymously. These measures provide a significant amount of information about whether anonymous implementations of one type from another are possible. We compare these measures with one another and with the consensus numbers defined by Herlihy [13].

FIFO Queues have over the years been the subject of significant research. Such queues are used as buffers both in a variety of applications, and in recent years as a key tool in buffering data in high speed communication networks.

Overall, the most popular dynamic-memory lock-free FIFO queue algorithm in the literature remains the MS-queue algorithm of Michael and Scott. Unfortunately, this algorithm, as well as many others, offers no more parallelism than that provided by allowing concurrent accesses to the head and tail. In this paper we present the Baskets Queue - a new, highly concurrent lock-free linearizable dynamic memory FIFO queue. The Baskets Queue introduces a new form of parallelism among enqueue operations that creates of mixed-order items instead of the standard totally ordered list. The operations in different baskets can be executed in parallel. Surprisingly however, the end result is a linearizable FIFO queue, and in fact, we show that a basket queue based on the MS-queue outperforms the original MS-queue algorithm in various benchmarks.

Blin (2006) proposed a distributed protocol that enables the smallest number of searchers to clear any unknown asynchronous graph in a decentralized manner. means that the searchers are provided no information about the graph. However, the strategy that is actually performed lacks of an important property, namely the monotonicity. That is, the clear part of the graph may decrease at some steps of the execution of the protocol. Actually, the protocol of Blin is executed in exponential time. Nisse and Soguet (2007) proved that, in order to ensure the smallest number of searchers to clear any -node graph in a monotone way, it is necessary and sufficient to provide ( log) bits of information to the searchers by putting short labels on the nodes of the graph. This paper deals with the smallest number of searchers that are necessary and sufficient to monotoneously clear any graph in a decentralized manner, when the searchers have no a priori information about the graph.

The distributed graph searching problem considers a team of searchers that is aiming at clearing any connected contaminated graph. The clearing of the graph is required to be , i.e., the clear part of the graph must remain permanently connected, and , i.e., the clear part of the graph only grows. The of a graph is the smallest number of searchers necessary to clear in a monotone connected way in centralized settings. We prove that any distributed protocol aiming at clearing any unknown n-node graph in a monotone connected way, in decentralized settings, has . That is, we prove that, for any distributed protocol , there exists a constant such that for any sufficiently large , there exists a -node graph such that requires at least searchers to clear . Moreover, we propose a distributed protocol that allows searchers to clear any unknown asynchronous -node graph in a monotone connected way.