Le séminaire du LaRIA a
lieu le jeudi à partir de 14h00 en amphithéâtre
Cassini, bâtiment des Minimes (sauf modification exceptionnelle).
Pour tous renseignements et/ou
propositions d'exposés s'adresser Sidney Youlou
N.B. Ce semestre, les séminaires recherches se
dérouleront en alternance avec les séminaires du Master
Pro. Ils auront donc lieu tous les quinze jours uniquement.
Prochains séminaires
(année 2006-2007) :
| Date | 25 septembre |
| Orateur | Xavier Défago (Japan Advanced Institute of Science and Technology) |
| Résumé |
Just like any distributed system, reaching agreement among a set of mobile robots is a fundamental issue in distributed robotic systems. However, unlike traditional distributed systems, the physical location of the nodes is of primary importance. Reaching agreement in this context is often illustrated by the gathering problem. Namely, starting from any initial configuration, a group of robots sharing no knowledge of a global coordinate system must move to meet at a non-predetermined location. While being very simple to express, the gathering problem retains the inherent difficulty of agreement, namely the question of breaking symmetry between robots. In this presentation, I will give a general overview of the difficulties surrounding gathering, as well as a report on some of our most recent results. More specifically, I will first discuss the use of a compass to solve the gathering problem deterministically in a system with limited visibility and little synchrony. In particular, we have focused on the case where the compasses of the robots are either unstable or make bounded errors. After that, I will briefly report on the solvability of the gathering problem in the presence of faults, using synchrony or randomization. |
| Date | 19 octobre |
| Orateur | Pierre Lemarinier (Laboratoire de Recherche en Informatique, Orsay) |
| Résumé | L'accroissement du nombre de processeurs dans les systèmes de calcul entraîne l'augmentation de la probabilité d'apparition d'une panne franche lors de l'exécution d'une application numérique. Les recherches sur les environnements de calcul par passage de messages ont conduit à l'implémentation de plusieurs protocoles de tolérance aux pannes au sein de librairies MPI. Plusieurs approches ont été ainsi proposées, utilisant des protocoles de prises d'état coordonnés ou d'enregistrement de messages. Les protocoles à points de reprise coordonnés sont les plus fréquemment implémentés pour apporter la tolérance aux pannes dans les systèmes à passage de messages. Il en existe principalement deux classes : bloquant ou non bloquant. Nous avons implémenté ces deux protocoles au sein de la librairie MPICH, nous les avons évalué et comparé en terme de performance et de scalabilité et j'en présenterai les principaux résultats. |
| Date | 9 novembre |
| Orateur | Richard Groult (LaRIA, Laboratoire de Recherche
en Informatique d'Amiens) |
| Résumé | Une
"répétition en tandem avec évolution"
consiste en une suite de copies plus ou moins contiguës où
chaque copie est fortement similaire à celle qui la
précède et à celle qui lui succède. Il
n'existe pas de notion de modèle comme pour les
répétitions en tandem "classiques" et la
première et la dernière copie peuvent être
complètement différentes. Ce "nouveau"
type de répétition a été mis en
évidence durant l'assemblage du génome humain. Je commencerai par définir, de façon formelle, les répétitions en tandem avec évolution à partir des observations effectuées dans les séquences biologiques. Après avoir effectué des tests sur des logiciels de recherche de répétitions, je conclus qu'il n'existe pas de logiciel capable de les détecter efficacement. J'ai alors conçu des algorithmes capables de détecter ce type de répétitions. Ces algorithmes ont été implantés afin de mettre à disposition des biologistes des outils qui détectent efficacement ces répétitions dans de très grandes séquences génomiques, telles les chromosomes humains. Une méthode d'exécution sur une grille de calcul est également présentée. Les résultats des tests réalisés sur des chromosomes montrent la présence de ces répétitions dans plusieurs génomes. |
| Date | 21 décembre |
| Orateur | Eddy Caron (LIP, Laboratoire de l'Informatique du Parallélisme Lyon) |
| Résumé | Facing the limits of
traditional tools of resource management within computational grids (related
to scale, dynamicity, etc. of the platforms newly considered), new
approaches, based on peer-to-peer technologies are emerging. The resource
discovery and in particular the service discovery is concerned by this
evolution. Among the solutions, a promising one is the indexing of
resources using trie structures and more particularly prefix trees. The
major advantages of trie-structured approaches is the capability to
support search queries on ranges of values with a latency growing
logarithmically in the number of nodes in the trie. Those techniques are
easy to extend to multicriteria searches. One drawback of using tries is
its inherent poor robustness in a dynamic environment, where nodes join
and leave the network, leading to the split of the tree into a forest,
which results in the impossibility to route requests. Within most recent
approaches, the fault-tolerance is a prevention mechanism, often
replication-based. Finally, we will give idea to deal with load balancing
related to its mapping on the physical network. |
| Date | 18 janvier 2007 |
| Orateur | Julien Bernat (IML, Institut de Mathematiques de
Luminy, Marseille) |
| Résumé | Sous des
hypothèses algébriques, certains systèmes
dynamiques symboliques associés à des substitutions
peuvent admettre une représentation géométrique.
Dans ce cas, on peut établir des liens entre des
propriétés de nature combinatoire,
géométrique ou ergodique, et formuler de nombreuses
questions encore non résolues. Dans cet exposé, nous nous intéressons à l'étude de propriétés combinatoires. Après avoir rappelé les notions utiles à l'étude de systèmes substitutifs, nous montrerons comment l'étude des paires équilibrées irréductibles permet d'obtenir des informations sur l'algorithme des paires équilibrées. Nous nous intéresserons plus particulièrement aux cas des langages sturmiens, d'Arnoux-Rauzy, puis nous nous intéresserons à une représentation géométrique discrète permettant d'étudier une classe de langages substitutifs. |
| Date | 25 janvier |
| Orateur | Laurent Mouchard (Université de Rouen) |
| Résumé | Nous présenterons des
résultats récents sur les structures d'indexation pour la recherche de
généricite (facteurs de longueur maximale communs a un ensemble de
séquences) ou de spécificité (facteurs minimaux propres a une séquences)
ainsi que des résultats plus anciens sur un certain nombre de répétitions
dans les séquences. Cet expose sera également l'occasion de présenter
quelques problèmes ouverts d'intérêt, notamment les structures de donnes
compressées, alternatives économiques aux structures a suffixes
habituelles. |
| Date | 15 février |
| Orateur | Elöd Egyed-Zsigmond (LIRIS, INSA Lyon) |
| Résumé | A venir |
Séminaires
de l'année 2005-2006
Séminaires
de l'année 2004-2005
Séminaires
de l'année 2003-2004
Séminaires
de l'année 2002-2003
Séminaires de l'année 2001-2002
Séminaires
des années précédentes