Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 13 Mars 2001

Modeles et algorithmes pour le routage compact et la recherche d'informations dans les reseaux avec menteurs

par Nicolas Hanusse (LRI)

Dans cet expose, deux problemes "cousins" sont presentes: routage et recherche d'informations. Le probleme general du routage dans les reseaux distribues arbitraires et les machines paralleles consiste a developper des methodes pour acheminer des messages d'un noeud a un autre. Chaque noeud indique une direction a suivre pour aller a destination. Lorsque les reseaux sont grands, il devient necessaire de limiter la quantite d'information, c'est-a-dire la memoire requise a chaque routeur tout en preservant un acheminement rapide des messages. La recherche d'information peut etre vue comme une variante du routage mais les contraintes sont differentes: instances multiples d'une meme information, conseil errone a certains noeuds (appeles menteurs), ... les performances en temps deviennent plus preoccupantes que la quantite de memoire.

Les reseaux sont modelises par des graphes et nous nous interessons a l'impact de la topologie des graphes pour le routage compact et pour la recherche d'information dans des reseaux avec menteurs. Comme illustration, nous montrerons qu'on peut router dans un reseau planaire avec des tables de routage de relativement petites tailles et nous presenterons des exemples d'algorithmes deterministes et probabilistes pour la recherche d'informations par agents mobiles.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr