Program > By author > Sohier Devan

Wednesday 26
Distributed algorithms, multi-agent and parallel computing
Alain Bui
› 11:30 - 12:00 (30min)
› Bât B - TD 31
Optimisation locale d'un système distribué asynchrone sujet à des défaillances
Devan Sohier  1@  
1 : Parallélisme, Réseaux, Systèmes d'information, Modélisation  (PRISM)  -  Website
CNRS : UMR8144, Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)
45 avenue des Etats-Unis Bâtiment Descartes 78035 Versailles CEDEX -  France

Un système distribué est constitué d'un ensemble de noeuds de calcul, exécutant chacun un algorithme dans le but de faire émerger une propriété globale dans le système. Les noeuds n'ont cependant qu'une connaissance partielle de l'état du système distribué, au travers des communications qu'ils entretiennent entre eux (messages, mémoire partagée, ou tout autre mécanisme de communication), communications qui peuvent être sujettes à des perturbations (asynchronisme, et pertes de messages en particulier).

Le système distribué évolue par l'action des algorithmes exécutés par les différents noeuds, mais peut également subir des événements non-contrôlé par l'algorithme : pannes, changements du graphe de communication, etc.

Chaque noeud doit donc exécuter un algorithme visant à optimiser le fonctionnement du système sur la base d'informations partielles et incertaines. Nous présenterons dans cet exposé plus particulièrement deux mécanismes probabilistes basés sur l'observation locale de l'état du système distribué : l'un vise à la construction de plus courts chemins, et l'autre à la circulation d'un jeton unique dans un système asynchrone sujet à des pertes de messages.


Online user: 1