Contribution à l'algorithmique distribuée de contrôle : arbres couvrants avec et sans containtes
Franck Butelle · HAL (Le Centre pour la Communication Scientifique Directe) · 1994
In this PhD thesis, we present a study of distributed asynchronous algorithms of control. Distributed algorithms are algorithms operating on distributed systems. These systems consist in networks of sites, where each site can be either simple (when reduced to a single processor) or complex (when expanded to a whole computer or a Local Area Network). In this study, we only consider networks of sites sharing neither memory nor global clock. Sites work in parallel, asynchronously and each computation is only performed by message exchange. In such a context, distributed algorithms are called ``message-driven''. We try to limit waiting states by not introducing synchronization mechanisms. Generally speaking, we make no particular assumption on the way algorithms start, namely, any non-empty subset of sites may start an algorithm. We try to remain as general as possible but in this work, we limit our considerations to determinist algorithms. Our assumptions are supporting the essential properties of distributed algorithms~: that is essentially the local behaviour. A control algorithm establishes a virtual structure over the whole network in which each site can distinguish some of its neighbors to play special roles. More particularly, we have chosen to study structures which are similar to spanning trees. We recall that numerous problems in distributed computing, such as distributed termination and leader election, can be reduced to spanning tree construction. In order to construct such a structure or to elect a leader, most of known distributed algorithms transform this problem into an extrema-finding problem. In fact, they elect the site which has the greatest (or the lowest) identity and construct a spanning tree at the same time. We study two kinds of algorithms~: phase-based algorithms and what we call anarchic algorithms. The latter algorithms are designed to behave without any kind of synchronization. Of course their study is difficult and they often need more message exchange, but this kind of un-foreseeable behaviour is a rather good way for improving the fault tolerance. We present a new algorithm of such a kind, moreover it is associated to a leader election which is not an extrema-finding. Its analysis leads us to show worst-case examples, but these examples are rare and our empirical average-case analysis show that this algorithm is almost as good as the best known algorithm for spanning tree construction. This latter algorithm uses token-based methods and therefore behave more sequentially. Other algorithms such as constructing constrained spanning trees, are studied. The most popular constraint is the minimum total weight, which represents an economical criterion. To our knowledge, the Minimum Diameter Spanning Tree is a problem which had never been addressed in the field of distributed research. We consider ``weighted'' diameter~: viz. the diameter $D$ of a graph is the sum of the edges' weights along the longest shortest path. If we consider time complexity, this constraint is obviously of great interest, since it always exists a couple of sites needing at least $D$ units of time to exchange information. We present a method for constructing a MDST and from this method, we give different algorithms, whether fault tolerance is needed or not. Finally, the practical study of distributed algorithm on large networks leads to build a simulator. Compared to the others simulators, ours offer the advantage of being simple and easily adaptable. In order to have faster and more realistic simulations, we parallelize this algorithm. The same code can be performed on a personal computer, a parallel computer or even a distributed machine.