Archives
2011
2010
2009
2008
2007
2006
2005
2004
2003

Événements   Share

Séminaire du Département d'informatique et d'ingénierie

Conférencier :

Andrzej Pelc, professuer au Département d'informatique et d'ingénierie de l'UQO

Thème de la conférence :

Oracles : un nouveau paradigme pour les algorithmes dans les réseaux

Résumé :

Nous étudions le problème de la quantité d'information concernant le réseau qui doit être fournie aux nœuds du réseau ou aux agents mobiles pour effectuer une tâche de communication ou d'exploration de manière efficace. Notre approche est quantitative : nous étudions le nombre minimal de bits (la grandeur minimale de l'oracle) qui doit être donné aux nœuds ou aux agents pour accomplir la tâche. La grandeur minimale de l'oracle peut servir comme une nouvelle mesure de complexité d'une tâche distribuée.

Ce nouveau paradigme dans l'algorithmique distribuée est présenté à travers deux exemples. Le premier est une tâche d'exploration, où un agent mobile doit parcourir tous les liens du réseau en faisant le moins de traversées d'arêtes possible. Le deuxième est une tâche de diffusion de messages à partir d'une source et nous comparons deux de ses variantes. Dans l'une, appelée le réveil du réseau, seulement les nœuds qui ont déjà reçu le message de la source peuvent envoyer des messages; dans l'autre, tous les nœuds peuvent envoyer des messages, même avant d'obtenir le message de la source. Notre résultat principal montre que le nombre minimal de bits d'information pour faire le réveil du réseau de n nœuds avec un nombre linéaire de messages est de l'ordre de n log n, mais la deuxième variante de la diffusion avec un nombre linéaire de messages peut se faire avec seulement O(n) bits d'information.   

Modifié par:  Direction des communications et du recrutement
Dernière mise à jour:  19.03.2007 10.39

Nouvelles
Événements
Communiqués

 

Savoir Outauouais

l'UQO, ça grandit
Pour nous joindre | À propos du site | Webmestre
Université du Québec en Outaouais, 283 boul. Alexandre-Taché, C.P. 1250, succursale Hull, Gatineau, Québec, Canada, J8X 3X7 | Tél.: 1 800 567-1283 ou 819 595-3900
© Université du Québec en Outaouais, 2007