Séminaires AND et extérieurs

Jusqu'à présent, les itérations chaotiques ont été étudiées et utilisées dans des situations de convergence, de stabilité. Nous avons regardé au contraire s'il était possible d'utiliser ces itérations pour engendrer du "désordre", le but étant de proposer des applications en "sécurité informatique". On entend par là : chiffrement, tatouage numérique, génération de nombres pseudoaléatoires, fonctions de hachage, etc.

Ces applications ne sont valables qu'à partir du moment où l'on est en mesure de prouver, mathématiquement, que le désordre dont on parle n'est pas qu'apparent, mais fondamentalement complexe. La théorie mathématique du chaos nous a offert un cadre rigoureux d'étude pour ces itérations.

Je me propose de vous présenter, dans le cadre de ce séminaire, nos avancées théoriques et leurs conséquences pratiques.

La stéganographie est l'art de dissimuler une information secrète au sein d'un conteneur d'aspect anodin (une image, un son, etc.) sans que ce dernier apparaisse avoir subi une quelconque modification pour tout non initié.

Il s'agira, au-delà des concepts et enjeux fondamentaux de cette science, d'approcher concrètement l'utilisation de la stéganographie par le biais d'un outil applicatif et d'une librairie Java open source.

La diffusion en continu (streaming) de données audiovisuelles n'est plus considérée comme une technologie d'avant-garde, mais entre dans le quotidien du grand public. Cependant, les systèmes de streaming d'aujourd'hui sont encore loin d'être parfaits. En effet, les fonctionnalités permettant de parcourir rapidement des contenus "streamés" sont toujours absentes de ces systèmes! Par ailleurs, dans un système de streaming pair-à-pair (P2P), le problème de la disponibilité des données, qui est dû au départ imprévisible d'un pair, n'a pas encore reçu l'attention appropriée. Les travaux présentés dans cette thèse s'articulent autour de ces deux problématiques et contribuent à y remédier en apportant des solutions pertinentes.

Afin de permettre une navigation accélérée au sein des présentations multimédias diffusées en continu, nous avons défini une sémantique adéquate pour le parcours rapide. Cette nouvelle sémantique, qui relie la navigation accélérée dans une présentation à son contenu, a été mise en œuvre par une heuristique de préchargement appropriée. L'objectif de celle-ci est de minimiser le temps d'attente des utilisateurs suite à une action de navigation accélérée.

En ce qui concerne le second point, nous défendons l'idée qu'il faudrait consacrer les ressources du système P2P pour garantir, dans la mesure du possible, la disponibilité des données uniquement pour les contenus qui sont en cours d'accès. Pour ce faire, nous avons opté pour la préservation des suffixes de ces contenus dans un cache virtuel distribué. Nous avons élaboré une stratégie adaptative pour la gestion de ce cache par un système asservi qui prend en compte la taille variable du cache et la charge du streaming dans le système.

En dernier lieux, nous avons décrit la conception et la mise en œuvre d'un prototype qui démontre la faisabilité d'un système de streaming P2P où la difussion d'un contenu est assurée par un seul pair le détenant. Notre prototype, dénommé JStreaper, permet notamment d'adapter les contenus audiovisuels aux capacités d'affichage et de traitement des terminaux destinataires.

The matching problem asks for a large set of disjoint edges in a graph. It is a problem that has received considerable attention both from the sequential and the self-stabilizing communities. Previous work has resulted in self-stabilization algorithms for computing a maximal (1/2-approximation) matching in a general graph, as well as computing a 2/3-approximation on more specific graph types.

In this lecture we present a single self-stabilizing algorithm for the maximal matching problem that unites all of the previous algorithms in that it has the same time complexity as the previous best algorithms for the sequential adversarial, the distributed fair, and the synchronous daemon. In addition, the algorithm improves the previous best time complexities for the distributed adversarial daemon from O(n²) and O(d·m) to O(m) where n is the number of processes, m is the number of edges, and d is the maximum degree in the graph.

Moreover, we present the first self-stabilizing algorithm for finding a 2/3-approximation to the maximum matching problem in a general graph. We show that our new algorithm converges in time O(2ⁿ⁺²·d·n) moves and O(n²) rounds under a distributed adversarial and distributed fair daemon, respectively, where n is the number of nodes in the graph.