Catálogo de publicaciones - libros

We would like to discuss what seems to be a general methodology to develop fast distributed algorithms for optimization problems on graphs, based on the primal-dual schema. The kind of problems we have in mind are of the following type. We have a synchronous, message-passing network that is to compute a global function of its own topology. Examples of such functions are maximal independent sets, vertex and edge colorings, small dominating sets, vertex covers and so on. Crucially, nodes only know their neighbours and have very little or no global information. In what follows, the only global information allowed will be n, the number of nodes in the network (or an upper bound on it). In this setting the running time of a protocol is given by the number of communication rounds needed to compute the output. By the end of the algorithm each node or edge will have decided its final status: its own color, whether or not to be part of the dominating set etc. In many situations of interest the cost of communication is orders of magnitude larger than local computation cost, and the model provides a rough, but quite useful, quantitative framework to develop and analyze interesting algorithms.

Efficient data gathering is an important issue in sensor networks. We will discuss the problem of time efficient data gathering, in which data sensed throughout the network must be collected at a sink node; the aim is to minimize the time needed to complete the process. The emphasis is on some algorithmic and graph theoretical problems arising in the area.

This paper surveys some aspects of the graph theoretic notion of treewidth. In particular, we look at the interaction between different characterizations of the notion, and algorithms and algorithmic applications.

We consider the problem of periodic exploration of all nodes in undirected graphs by using a finite state automaton called later a . The robot, using a constant number of states (memory bits), must be able to explore any unknown anonymous graph. The nodes in the graph are neither labelled nor colored. However, while visiting a node the robot can distinguish between edges incident to it. The edges are ordered and labelled by consecutive integers 1,...,() called , where () is the degree of . Periodic graph exploration requires that the automaton has to visit every node infinitely many times in a periodic manner. Note that the problem is unsolvable if the local port numbers are set arbitrarily, see [8]. In this context, we are looking for the minimum function (), such that, there exists an efficient deterministic algorithm for setting the local port numbers allowing the robot to explore all graphs of size along a traversal route with the period (). Dobrev proved in [13] that for oblivious robots () ≤ 10. Recently Ilcinkas proposed another port labelling algorithm for robots equipped with two extra memory bits, see [20], where the exploration period () ≤ 4 − 2. In the same paper, it is conjectured that the bound 4 − (1) is tight even if the use of larger memory is allowed. In this paper, we disprove this conjecture presenting an efficient deterministic algorithm arranging the port numbers, such that, the robot equipped with a constant number of bits is able to complete the traversal period in () ≤ 3.75 − 2 steps hence decreasing the existing upper bound. This reduces the gap with the lower bound of () ≥ 2 − 2 holding for any robot.

A large group of autonomous, mobile entities e.g. robots initially placed at some arbitrary node of the graph has to jointly visit all nodes (not necessarily all edges) and finally return to the initial position. The graph is not known in advance (an online setting) and robots have to traverse an edge in order to discover new parts (edges) of the graph. The team can locally exchange information, using wireless communication devices.

We compare a cost of the online and optimal offline algorithm which knows the graph beforehand (competitive ratio). If the cost is the total time of an exploration, we prove the lower bound of (log /loglog) for competitive ratio of any deterministic algorithm (using global communication). This significantly improves the best known constant lower bound. For the cost being the maximal number of edges traversed by a robot (the energy) we present an improved (4 − 2/)-competitive online algorithm for trees.

Fraigniaud (2006) introduced a new measure of difficulty for a distributed task in a network. The smallest of a distributed problem is the smallest number of bits of information that has to be available to nodes in order to accomplish the task efficiently. Our paper deals with the number of bits of advice required to perform efficiently the graph searching problem in a distributed setting. In this variant of the problem, all searchers are initially placed at a particular node of the network. The aim of the team of searchers is to capture an invisible and arbitrarily fast fugitive in a monotone connected way, i.e., the cleared part of the graph is permanently connected, and never decreases while the search strategy is executed. We show that the minimum number of bits of advice permitting the monotone connected clearing of a network in a distributed setting is ( log), where is the number of nodes of the network, and this bound is tight. More precisely, we first provide a labelling of the vertices of any graph , using a total of ( log) bits, and a protocol using this labelling that enables clearing in a monotone connected distributed way. Then, we show that this number of bits of advice is almost optimal: no protocol using an oracle providing ( log) bits of advice permits the monotone connected clearing of a network using the smallest number of searchers.

The -renaming problem consists in providing the processes with a new name taken from a new name space of size . A renaming algorithm is adaptive if the size depends on the number of processes that want to acquire a new name (and not on the total number of processes). Assuming each process proposes a value, the -set agreement problem allows each process to decide a proposed value in such a way that at most different values are decided. In an asynchronous system prone to up to process crash failures, and where processes can cooperate by accessing atomic read/write registers only, the best that can be done is a renaming space of size  =  +  where is the number of processes that participate in the renaming. In the same setting, the -set agreement problem cannot be solved for  ≥ .

This paper focuses on the way a solution to the renaming problem can help solving the -set agreement problem when  ≤ . It has several contributions. The first is a -resilient algorithm (1 ≤  < ) that solves the -set agreement problem from any adaptive ( +  − 1)-renaming algorithm, when  = . The second contribution is a lower bound that shows that there is no wait-free -set algorithm based on an ( +  − 1)-renaming algorithm that works for any value of , when  < . This bound shows that, while a solution to the ( +  − 1)-renaming problem allows solving the -set agreement problem despite  =  failures, such an additional power is useless when  < . In that sense, in an asynchronous system made up of atomic registers, ( +  − 1)-renaming allows progressing from  >  to  = , but does not allow bypassing that frontier. The last contribution of the paper is a wait-free algorithm that constructs an adaptive ( +  − 1)-renaming algorithm, for any value of the pair (,), from a failure detector of the class (this last algorithm is a simple adaptation of an existing renaming algorithm).

Given a graph  = (,), a vertex of is a if it minimizes the sum of the distances to all other vertices of . The median problem consists in finding the set of all median vertices of . In this note, we present a self-stabilizing algorithm for the median problem in partial rectangular grids. Our algorithm is based on the fact that partial rectangular grids can be isometrically embedded into the Cartesian product of two trees, to which we apply the algorithm proposed by Antonoiu, Srimani (1999) and Bruell, Ghosh, Karaata, Pemmaraju (1999) for computing the medians in trees. Then we extend our approach from partial rectangular grids to plane quadrangulations.

The maximal matching problem has received considerable attention in the self-stabilizing community. Previous work has given different self-stabilizing algorithms that solves the problem for both the adversarial and fair distributed daemon, the sequential adversarial daemon, as well as the synchronous daemon. In the following we present a single self-stabilizing algorithm for this problem that unites all of these algorithms in that it stabilizes in the same number of moves as the previous best algorithms for the sequential adversarial, the distributed fair, and the synchronous daemon. In addition, the algorithm improves the previous best moves complexities for the distributed adversarial daemon from () and () to () where n is the number of processes, m is the number of edges, and is the maximum degree in the graph.

Recently, quite a few papers studied methods for representing network properties by assigning to the vertices of a network. Consulting the labels given to any two vertices and for some function (e.g. “distance(,)”) one can compute the function (e.g. the graph distance between and ). Some very involved lower bounds for the sizes of the labels were proven.

In this paper, we demonstrate that such lower bounds are very sensitive to the number of vertices consulted. That is, we show several almost trivial constructions of such labeling schemes that beat the lower bounds by large margins. The catch is that one needs to consult the labels of vertices instead of two. We term our generalized model .

Additional contributions are several extensions. In particular, we show that it is easy to extend our schemes for tree to work also in the dynamic scenario. We also demonstrate that the study of the queries model can help in designing a scheme for the traditional model too. Finally, we demonstrate extensions to the non-distributed environment. In particular, we show that one can preprocess a general weighted graph using almost linear space so that flow queries can be answered in almost constant time.