Aspects algorithmiques et implémentation dans des calculs locaux
Thèses de doctorat
Date de soutenance
2005-12-01Résumé
Dans cette thèse nous nous intéressons aux aspects algorithmiques des calculs locaux dans les domaines de la synchronisation et du contrôle de l’exécution. Nous introduisons, entre autre, deux synchroniseurs dont l'un se ...Lire la suite >
Dans cette thèse nous nous intéressons aux aspects algorithmiques des calculs locaux dans les domaines de la synchronisation et du contrôle de l’exécution. Nous introduisons, entre autre, deux synchroniseurs dont l'un se base sur l'utilisation de l'algorithme de Y. Shi, B. Szymanski et N. Prywest et l'autre sur l'application des marches aléatoires dans les graphes. Ensuite, nous utilisons le concept des réductions de graphes pour présenter un algorithme capable de reconnaitre des propriétés de graphes a l'aide des calculs locaux. Cette étude introduit la notion de systèmes de réduction pratiques (handy reduction systems) qui nous permet de démontrer que toutes les propriétés de graphes de largeur arborescente bornée, définissable en logique monadique du second ordre, peuvent être reconnues par les calculs locaux. Nous établissons un lien directe entre les systèmes de réduction pratiques et le concept de reconnaisseurs de graphes avec connaissance structurelle (labeled graph recognizers). Ce lien nous permet de donner les conditions nécessaires pour qu'une propriété caractérisée par un système de réduction pratique soit reconnue au moyen de calculs locaux. Enfin, nous introduisons le langage de programmation des calculs locaux (Lidia). Ce langage est base sur un système de transition a deux niveaux ou les préconditions de chaque transition sont exprimées par la logique Gam. En se servant des propriétés descriptives de Gam, nous établissons la complétude du langage Lidia.< Réduire
Résumé en anglais
In this thesis, we study the algorithmic aspects of local computations in the area of distributed algorithms. We focus our attention on two special domains. These are network synchronization and execution control. We present ...Lire la suite >
In this thesis, we study the algorithmic aspects of local computations in the area of distributed algorithms. We focus our attention on two special domains. These are network synchronization and execution control. We present new results concerning the synchronization of networks under the assumption that processes are aware of some network properties. The results presented here make use, amongst others, of randomization and of the SSP protocol introduced by Y. Shi, B. Szymanski and N. Prywest. On the other hand, we take advantage of graph reduction algorithms to present an algorithmically solution for recognizing graph properties by local computations. To this end, we introduce the notion of handy reduction systems and prove, specially, that all properties on graphs of bounded treewidth, definable in the monadic second order logic, can be recognized by local computations. We also demonstrate that any handy reduction systems corresponds to a labeled graph recognizer with structural knowledge and, with the help of special kind of graphs morphisms : coverings, we derive necessary conditions for the size-recognizability of a graph property characterized by a handy reduction systems. At the end, we introduce the programming language for implementing local computations (Lidia). This language is built on a two levels transition system and on the logic G*oc, used to describe the preconditions of each transition system. We exploit results from the finite model theory to prove the descriptive power of G*00 and to show that any algorithm encoded by local computations can be implemented in Lidia.< Réduire
Mots clés
Informatique
systèmes distribués
synchroniseurs
réduction de graphes
langages formels
logique
Unités de recherche