salle A. Pnueli CE3
23 mars 2006 - 11h00
Codes identifiants : une approche combinatoire d’un problème de détection de défaillances dans les réseaux
par Julien Moncel de Leibniz
Résumé : Les codes identifiants ont été introduits à la fin des années 90 pour modéliser un problème de détection de défaillances dans des réseaux multiprocesseurs [1]. Ils sont également utilisés pour concevoir des systèmes de localisation et de détection dans des environnements fermés munis de capteurs sans-fil [2]. Dans cet exposé, nous allons présenter une approche combinatoire de ce problème, dans le cadre de la théorie des graphes et de la théorie des codes. Plusieurs questions seront discutées, de natures algorithmique (complexité du problème) et structurelle (contructions de graphes extrémaux, bornes). Les outils utilisés relèvent de la théorie des graphes, mais aussi de l’algèbre et de la théorie des probabilités, qui sont utilisés en particulier pour aborder des problèmes extrémaux. Nous replacerons également ce sujet dans le cadre plus général des problèmes de tests groupés, en lien avec d’autres applications liées à la sécurité dans les réseaux. En particulier, nous présenterons un lien entre les codes identifiants et les codes superimposés, qui sont utilisés pour modéliser un problème d’identification d’utilisateurs dans des canaux de communication partagés. Cet exposé, qui se voudra accessible au plus grand nombre, décrira des développements récents de la théorie des codes identifiants, ainsi que quelques perspectives de recherche.
Références :
[1] M. G. Karpovsky, K. Chakrabarty, L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Transactions on Information Theory 44(2), (1998), 599–611.
[2] S. Ray, D. Starobinski, A. Trachtenberg, R. Ungrangsi, Robust Location Detection with Sensor Networks, IEEE Journal on Selected Areas in Communications 22(6) (2004), 1016-1025.
