Abstract FR:

Dans cette thèse, nous nous intéressons aux aspects algorithmiques des calculs locaux dans les domaines de la synchronisation d'algorithmes et du contrôle de l'exécution. Dans un premier temps nous proposons différents protocoles de synchronisation qui ont besoin, pour certains, d'avoir une connaissance structurelle du graphe (diamètre, nombre de processeurs, etc. . . ). D'autre part, nous utilisons le concept des réductions de graphes pour présenter un algorithme capable de reconnaître des propriétés de graphes à 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. Enfin, nous introduisons le langage de programmation des calculs locaux (Lidia). Ce langage est basé sur un système de transition à deux niveaux où les préconditions de chaque transistion sont exprimées par la logique L*∞. En se servant despropriétés descriptives de L*∞, nous établissons la complétude du langage Lidia.