ENS de Cachan
Département
Informatique
Conférences de rentrée 2013









Davide Frey

Le 3/9, 14h-17h

Epidemic protocols: from overlays to applications.

Epidemic, or gossip-based, protocols provide a flexible paradigm for a large number of distributed applications. Initially introduced in the context of replicated databases, they have proved successful in a variety of tasks comprising overlay maintenance, data dissemination, and even distributed content recommendation. In this lecture, we will provide a brief introduction to epidemic protocols by presenting their main properties and by studying three important applications. We will first consider the problem of maintaining a peer-to-peer overlay through the use of random-peer-sampling and clustering protocols. We will then show how to combine these building blocks to yield complex applications such as video streaming and recommendation. In the context of video streaming, we will present HEAP, HEterogeneity-Aware gossip Protocol. HEAP leverages a gossip to approximate the relative bandwidth capabilities of peer-to-peer nodes. Based on this information, it then tunes gossip-based dissemination in order to leverage the most capable nodes. In the context of recommendation, we will instead present WhatsUp, a decentralized gossip-based news-item recommender.

Alix Munier

Le 4/9, 14h-17h

Etude de systèmes DataFlow Synchrones pour l'optimisation des ressources de communication

Les Graphes DataFlow Synchrones (SDF en abrégé pour "Synchronous DataFlow Graphs") constituent un formalisme issu de la conception de systèmes électroniques. Ils ont été introduits par Lee et Messerschmitt en 1988 et ont été utilisés intensivement dans le monde académique et industriel, donnant naissance à de nombreuses extensions. A titre d'exemple, ils sont aujourd'hui utilisés pour modèliser les communications lors de l'exécution d'une application sur l'architecture multi-coeurs développée par la société Kalray. Le but de ce cours est de présenter un ensemble d'outils mathématiques pour l'analyse d'un SDF et leur utilisation dans un contexte industriel. La première partie du cours est consacrée à la présentation des problèmes qui nous intéressent et à des simplifications mathématiques du modèle. Nous commencerons par présenter le modèle des SDF, et un ensemble de problèmes concrets associés : évaluation de la vivacité, du débit maximum atteignable et limitation des ressources de communication. Puis, nous montrerons un ensemble de simplifications polynomiales qui permettent de limiter la structure des SDF étudiés : notion de consistance, de contrainte de précédence, de jetons utiles et normalisation d'un SDF consistant. La seconde partie de cet exposé porte sur la présentation de méthodes pour l'évaluation de la vivacité et du débit maximum. La complexité de ces problèmes n'est pas connue, et toutes les méthodes exactes sont de complexité exponentielle. Elles sont de fait difficilement utilisables dans un contexte industriel ou comme certificat pour des méthodes d'optimisation. Nous présenterons tout d'abord une méthode exacte basée sur une expansion (non polynomiale) du problème. Puis, nous montrerons que, quand on fixe une politique périodique d'exécution des acteurs, on peut obtenir des algorithmes polynomiaux pour évaluer des bornes maximum du débit et des conditions suffisantes de vivacité. Nous verrons enfin qu'une solution intermédiaire est intéressante pour améliorer les résultats obtenus pour un temps de réponse acceptable. La dernière partie porte sur la présentation de travaux de recherche récents en lien avec des applications industrielles. Nous montrerons comment la caractérisation d'un ordonnancement périodique d'un SDF permet d'utiliser la programmation linéaire pour minimiser la taille des ressources de communication tout en assurant un débit minimum. Nous conclurons par la présentation d'extensions des SDF qui permettent de modèliser des problèmes industriels et pour lesquels nos outils mathématiques peuvent s'étendre.

Olivier Roux

Le 5/9, 14h-17h

Modélisation et analyse formelles des systèmes dynamiques complexes: application aux réseaux de régulation biologique.

A la différence de la bio-informatique traditionnelle, initialement plus portée sur des aspects statiques des systèmes vivants (séquençage du génome, analyse d'image, etc.), la biologie systémique constitue depuis peu un champ de recherche actif et prometteur. Dans ce contexte, nous nous intéressons à modéliser et analyser les comportements dans des systèmes dynamiques complexes que sont les réseaux de régulation biologique (RRB). Ces réseaux décrivent les influences, positives ou négatives, entre des états de composants biologiques (gènes, protéines, etc.). Ces objets sont étudiés notamment pour comprendre la dynamique de production de certaines protéines au sein des cellules. Après un bref état de l'art des modélisations des RRB, nous introduisons la modélisation des RRB selon une approche que nous avons conçue sous le nom de "Frappe de Processus" ("Process Hitting"). Nous présentons une nouvelle approche de vérification formelle basée sur l'interprétation abstraite et l'analyse statique des frappes de processus. En analysant uniquement la structure du programme, et sans construire l'espace des états qu'il engendre, cette méthode originale évite l'habituelle explosion combinatoire dont souffrent les outils actuels de vérification. Nous montrons qu'elle permet donc ainsi d'obtenir des résultats spectaculaires sur des systèmes de grande taille. Appliquée sur des RRB regroupant autour de 100 composants (parmi les plus grands à ce jour), notre approche répond très rapidement (entre le centième et le dixième de seconde) aux questions d'atteignabilité d'états de composants, là où les outils de vérification formelle classiques (type BDD, SDD) échouent régulièrement. Enfin, nous concluons sur nos travaux en cours et perspectives, à savoir l'extension des cas traitables par notre analyse, et l'incorporation de dimensions temporelles et stochastiques, la recherche des propriétés comportementales, etc.

Sabine Coquillart

Le 9/9, 14h-17h

Réalité Virtuelle et Réalité Augmentée, une introduction centrée utilisateur

L'objectif de ce cours est une introduction à la réalité virtuelle et à la réalité augmentée. Après une définition de ces deux domaines basée sur le "Mixed Reality Continuum" proposé par Paul Milgram en 1994, l'exposé présentera les différentes approches technologiques, des plus classiques aux plus inattendues et leurs principaux usages en terme d'applications.

Pascal Koiran

Le 10/9, 11h15-12h45

Quelques mystères de la complexité algébrique

En complexité algébrique on étudie le nombre d'opérations arithmétiques nécessaire pour résoudre un problème donné. De nombreux algorithmes s'expriment naturellement dans ce cadre. Malgré plusieurs décennies de recherches et des progrès récents, les principaux problèmes du domaine sont toujours ouverts. Dans cet exposé je présenterai certains de ces problèmes et des résultats partiels en m'appuyant sur deux exemples :

  • Le calcul du permanent, un petit cousin du déterminant pour lequel on ne prend pas en compte la signature des permutations.
  • La complexité de la multiplication de matrices. Ce problème semble à première vue élémentaire mais les apparences sont parfois trompeuses...

Stéphane Natkin

Le 11/9, 9h30-12h30

Le jeu vidéo : un pur système d'interaction

Un jeu vidéo est dans son essence et peut être dans son esthétique un pur système d'interaction. La combinaison de mécanismes issus de la narration audiovisuelle et des mécanisme de jeux est au cœur de la sensation d'engagement du joueur. La conception d'un jeu vidéo basée sur un certains nombres d'hypothèses sur la sociologie et la psychologie de la perception du joueur. En nous appuyant sur plusieurs exemples, soit de jeux commercialisés, soit de projets d'élèves, soit de travaux de recherche nous présentons ces principes de conception. Enfin nous nous intéressons a l'émergence et le succès des nouveaux dispositifs d'interactions depuis la WII jusqu'à Natal.

Bernadette Charron-Bost

Le 12/9, 14h-17h

Les algorithmes naturels

Les algorithmes constituent un langage très expressif pour modéliser les systèmes biologiques ou physiques et les phénomènes de synchronisation et de coordination que l'on peut observer au sein de ces systèmes multiagents. Cette expression algorithmique permet non seulement d'effectuer des simulations numériques mais aussi et surtout fournit un cadre très puissant pour l'analyse de ces systèmes naturels. Ainsi, on peut légitimement envisager que, pour les sciences du vivant, les algorithmes naturels jouent un rôle analogue à celui des équations différentielles en Physique. Pour conforter cette analogie, il faudrait développer un calcul algorithmique qui serait aux sciences du vivant ce que le calcul différentiel est à la Physique. Nous exposerons plus en détail ce nouveau domaine de recherche et discuterons de ce que peut recouvrir un tel programme de travail autour des notions fondamentales que sont le consensus, la synchronisation et la tolérance aux défaillances. Nous présenterons différents éléments de calcul algorithmique récemment proposés pour l'analyse des algorithmes naturels et qui mettent en jeu des techniques classiques en systèmes dynamiques.


Contacter le Département Informatique
Dernières modifications : le 27/09/2013