Résumé de séminaire

Résumé :

Le databroadcast (dissémination de données) est un moyen efficace de réduire la charge des serveurs d'information (web, satellite, ethernet, sans fil, videotext, TV, etc...) en tirant parti des possibilités de diffusion naturelle de ces média. Dans un tel système (appelé push-based), les clients n'émettent pas de requêtes au serveur mais, comme pour la radio, se connectent sur le canal d'émission et attendent que l'information qui les intéresse soit diffusées, à charge du serveur de choisir l'ordre des diffusions pour minimiser l'attente moyenne des clients.

L'ensemble des travaux théoriques sur ce domaine a porté jusqu'à présent sur le cas où chaque client n'était intéressé que par une unique information. Ce problème d'ordonnancement étant déjà NP-dificile, plusieurs algorithmes d'approximation ont été proposés.

Nous nous intéressons ici au cas où il existe des dépendances entre les fichiers requis par les utilisateurs et proposons les premiers algorithmes d'approximation pour ce problème. Nous démontrons de plus que, comme cela a été constaté dans les systèmes réels, nos algorithmes permettent des gains de performance arbitrairement grands sur les algorithmes préexistants.

Travail en collaboration avec Sandeep Dey

Références :

Home page : http://perso.ens-lyon.fr/nicolas.schabanel/