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

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.