%O Thesis %9 PhdThesis %F SELLAMI_2004-PhD %A Sellami, Afif %T Des calculs locaux aux algorithmes distribués %I Université Bordeaux I %C Talence, France %X The goal of this thesis is to show that the model of the graph relabelling systems is a relevant model for the study, comprehension and the implementation of distributed algorithms.
In a distributed algorithm, the termination detection of an algorithm is difficult since an algorithm is executed simultaneously by many processes and the algorithm finishes only when all the processes finished. To solve this problem, we use a particular product of two graph relabelling systems. The first codes the algorithm of which we want to detect his termination and the second codes an algorithms which detects his global termination.
The asynchronous algorithms are often less powerful than the synchronous corresponding algorithms. It is very useful to have a general method which makes the simulation of synchronous algorithms on asynchronous systems possible. For that, we use another product, similar than used for the termination detection problem, to simulate synchronous systems.
We had implemented a platform called Visidia which uses graph relabelling systems to implement distributed algorithms. With Visidia we can test, experiment, verify and visualize the execution of distributed algorithms coded with the help of graph relabelling systems or local computation.
We use Visidia to make experiments on algorithms which solve the sharing resource problems. Many algorithms were tested: the drinking philosophers problem, mutual exclusion in trees and finally, mutual exclusion in random network. %U http://grenet.drimm.u-bordeaux1.fr/pdf/2004/SELLAMI_AFIF_2004.pdf %D 2004