| Résumé | Cet exposé présente différents modèles de systèmes distribués.
Ces modèles correspondent à différents niveaux d'abstraction et à
différents niveaux de synchronisation entre les processus. Ces modèles
sont étudiés à travers le problème de l'élection qui met en évidence
les bons objets combinatoires pour les comprendre et comparer leur
puissance. Cette étude permet d'obtenir une caractérisation des réseaux
asynchrones qui communiquent par échange de messages en mode synchrone
et admettant un algorithme d'élection (idem pour les réseaux fonctionnant
suivant le modèle d'Angluin).
Cette étude permet également d'obtenir une caractérisation des réseaux
asynchrones qui communiquent par échange de messages en mode asynchrone
et admettant un algorithme d'élection. Cet algorithme nécessite un nombre
polynomial de messages de taille polynomiale alors que le précédent
algorithme, du à Yamashita et Kameda, nécessite un nombre polynomial de
messages de taille exponentielle.
(Ce travail a été effectué en collaboration avec Jérémie Chalopin,
CNRS-LIF-Marseille).
|