% \section{Composante Algorithmique Distribuée (AD)} \label{probresAD} \small{\textit{Participants~: T.~Andriamampinina, C.~Banderier, %\vspace{-.2cm} F.~Butelle, C.~Cérin, J-C.~Dubacq, L.~Finta, M.~Hakem, H.~Kenniche, C.~Lavault, G.~Paillard, A.~Rasoanaivo, V.~Ravelomanana, S-M.~Sedjelmaci, M.Valencia-Pabon}} %J-M.~Le Bars, A.~Viola} \subsection{Thèmes de recherche} L'algorithmique distribuée existe au sein de l'équipe \acs{OCAD} depuis presque quinze ans. Quant aux méthodes d'étude, à la conception et à l'analyse des algorithmes distribués, elles ont bien évolué durant cette période. La mathématisation du domaine s'est manifestée tout particulièrement par l'utilisation d'outils et de méthodes d'analyse sans cesse plus raffinés, entre autres dans les mesures de complexité en temps et en messages. La recherche et l'analyse d'algorithmes, c'est-à-dire de procédures effectives permettant de résoudre des problèmes ou bien de calculer la valeur d'une fonction en un nombre fini d'étapes, est particulièrement active autour des thèmes suivants~: \bi \item[--]\ les problèmes de communication dans les réseaux d'interconnexion~; \item[--]\ la modélisation et l'étude de problèmes issus des systèmes distribués~; \item[--]\ l'analyse en moyenne de classes générales d'algorithmes et de protocoles distribués~; \item[--]\ l'étude des algorithmes probabilistes, \item[--]\ l'étude de propriétés fondamentales de familles d'objets et structures combinatoires~: arbres, graphes, hypergraphes, permutations, modèles d'urnes, etc. \ei Les outils utilisés sont généralement issus des mathématiques classiques (analyse complexe, équation différentielles, asymptotique, probabilités) et les \textit{séries génératrices} en constituent la \guillemotleft~brique de base~\guillemotright\ par excellence. À partir des séries génératrices, de nombreuses techniques analytiques peuvent être mises en \oe uvre, allant de l'approximation asymptotique (réelle et complexe) aux méthodes stochastiques. Les résultats fournissent alors des informations très précises sur le comportement qualitatif ou quantitatif des systèmes étudiés (cf.~Ph. Flajolet, D.E. Knuth, R. Motwani, etc.). Ce progrès vers des techniques rodées en mathématiques discrètes --- la \textit{combinatoire analytique}, la théorie de graphes et les \textit{probabilités} --- s'est trouvé accéléré ces dernières années par l'arrivée dans l'équipe de jeunes chercheurs spécialistes du domaine (Vlady Ravelomanana, Cyril Banderier, Mario Valencia-Pabon). \subsubsection*{Conception et analyse d'algorithmes distribués} \label{aad} Les systèmes distribués se caractérisent par un processus de circulation et d'échange de l'information entre entités autonomes communicantes concourant à la réalisation d'un objectif commun. Le développement d'outils et de méthodes algorithmiques appropriées (combinatoire analytique, méthodes stochastiques, asymptotique complexe, etc.) permet d'analyser plus finement de nombreux algorithmes distribués, en particulier en moyenne. En retour, ces méthodes permettent de concevoir de nouvelles classes d'algorithmes distribués, dont la complexité en communication et/ou en temps est notablement améliorée. Les classes de réseaux (graphes) considérés possèdent des structures (topologies) très diverses et peuvent jouir de caractéristiques variées~: réseaux synchrones ou asynchrones, anonymes ou avec identités, fautifs ou sûrs, fixes ou mobiles, information structurelle, etc. Outre la recherche et la spécification (plus ou moins fouillées) de l'algorithme lui-même, les résultats portent prioritairement sur l'analyse de la complexité (au pire et en moyenne) de ces algorithmes (probabilistes ou non). Plus rarement, cette analyse de complexité est poussée plus loin~: calcul de tous les moments, preuve d'existence et mise en évidence d'une distribution limite, etc. (cf. \S~\ref{persprech2}). \medskip \textbf{Classes générales d'algorithmes distribués} De vastes \textit{classes d'algorithmes distribués} sont conçues et analysées dans cet axe de recherche. Ces algorithmes (déterministes ou probabilistes) s'appliquent à divers problèmes cruciaux du distribué, dans un très grand nombre de topologies de réseaux et sous diverses contraintes matérielles et temporelles. Franck Butelle et Christian Lavault étudient le problème de l'\textit{élection anonyme} dans les réseaux \textit{quelconques} (plus particulièrement les anneaux) et celui de la recherche d'un \textit{arbre optimal avec contraintes} (de diamètre ou de degré minimaux) dans un graphe \textit{quelconque}. Un grand nombre de \textit{protocoles d'ordonnancement dans des réseaux quelconques} (sous diverses contraintes matérielles ou temporelles) sont l'objet des travaux de Franck Butelle, Mourad Hakem et Lucian Finta. Enfin, de nouvelles méthodes pour construire des classes d'algorithmes distribués ont été utilisées par Christian Lavault et Gabriel Paillard~: \textit{inversions de liens d'un réseau acyclique orienté}, \textit{inversions d'arcs d'un (multi)graphe quelconque}, etc. (cf.~\S~\ref{persprech2}). Dans un univers réparti, l'ordonnancement est un problème de contrôle qui peut être pris en charge par la coopération des processus communicants situés sur chaque site actif. L'impossibilité d'avoir un état global cohérent d'un système totalement réparti fait que la plupart des algorithmes proposés ne permettent pas d'avoir une solution optimale. Seules des heuristiques peuvent être utilisées, comme celle proposée par Franck Butelle et Mourad Hakem (cf.~\ref{res2}). Dans la littérature courante, les hypothèses formulées pour la conception d'algorithmes d'ordonnancement distribué temps réel s'avèrent trop simplificatrices. En général, ils ne traitent en effet que de tâches indépendantes et ils supposent que les coûts de migration de celles-ci ne sont pas trop onéreux. De fait, le problème relevant de la prise en compte des contraintes de précédence réparties demeure non résolu. C'est seulement grâce à des hypothèses réalistes qu'il est possible de concevoir un algorithme d'ordonnancement distribué temps réel (cf.~\ref{res2}). \medskip \textbf{Protocoles de communication dans les réseaux sans fil} L'algorithmique des réseaux sans fils se situe à la frontière de l'algorithmique distribuée et de la théorie des graphes. L'environnement (structures, caractéristiques) y est supposé \textit{quelconque} (anonyme, synchrone ou asynchrone, tolérant aux fautes, etc.). C'est un champ d'investigation très fructueux, commun aux deux premiers axes de recherche du thème~: la conception et l'analyse d'algorithmes distribués et l'étude de structures ou objets combinatoires à dominante aléatoire. L'intérêt porté aux réseaux sans fils (réseaux mobiles ad hoc, capteurs, etc.) s'est considérablement accru ces dernier temps. Ceux-ci sont en effet utilisés en cas de sinistre (tremblement de terre, incendie, sauvetage, etc.) ou dans le cadre d'applications spécifiques diverses, militaires en particulier (\guillemotleft~concret~\guillemotright\ et lucratif~!). Contrairement aux réseaux mobiles cellulaires, qui nécessitent une infrastructure rigide, les \textit{réseaux mobiles ad hoc} (ou \textsc{Manet}) et les \textit{capteurs} doivent pouvoir s'utiliser très souplement et s'auto-organiser très rapidement pour fournir des services locaux spécifiques, souvent en urgence. Les capteurs sont ainsi des entités identiques minuscules à énergie (durée de vie des batteries) très limitée qui sont déployées massivement sur une région bien déterminée (du plan ou de l'espace) afin d'y mesurer des données locales (température, pression, hygrométrie, hydrométrie, mouvements divers, etc.) et les communiquer. Un \textsc{Manet} est un \textit{système distribué} \textit{non centralisé} à \textit{topologie variable}. Aucune unité privilégiée n'est en mesure de communiquer avec toutes les stations (anonymes). La situation et l'évolution globale du réseau leur reste donc inconnue. Le modèle de réseau considéré est \guillemotleft~à sauts multiples~\guillemotright\ et un \textsc{Manet} se modélise par un graphe $G$ non orienté, où une arête entre deux sommets (stations) indique que ceux-ci peuvent communiquer directement. Tous les problèmes suscités par un \textsc{Manet} $G$ (structure, communication, mobilité, sécurité, etc.) supposent que certaines propriétés structurelles de $G$ soient \textit{a priori} connues de chaque station. La plupart des protocoles de contrôle fondamentaux, comme la diffusion ou l'élection, utilisent ce type d'hypothèse initiale. C'est ainsi qu'une diffusion dans $G$ suppose, en général, la connaissance par les stations de certaines de ses caractéristiques exactes ou partielles (majorées)~: son nombre de n\oe uds $n$, son degré maximum $\Delta$, son diamètre $D$, etc. \medskip L'objectif de cet axe de recherche est d'étudier et d'analyser de manière assez systématique les principaux \textit{protocoles de contrôle} pour la communication dans les \textsc{Manets}. Christian Lavault et Vlady Ravelomanana étudient les algorithmes probabilistes de \textit{diffusions}, d'\textit{initialisation}, d'\textit{élection}, de \textit{routages}, de \textit{k-clustering}, d'\textit{exclusion mutuelle}, de \textit{tri}, etc. L'\guillemotleft~initialisation~\guillemotright\ consiste à attribuer aléatoirement des identités distinctes à chaque entité (radio, capteur, etc.) du réseau~; elle s'apparente à une attribution de \guillemotleft~codes~\guillemotright\ uniques (largeurs de bandes passantes, coloriage, (ré)étiquetage, etc.). Par ailleurs, le modèle des \textit{graphes aléatoires géométriques} (cf.~\ref{acc}) permet à Vlady Ravelomanana d'obtenir des mesures précises sur les propriétés générales et extrêmales de ces réseaux~: taille, composantes, transitions de phase, régimes, etc. \subsubsection*{Systèmes distribués et algorithmique parallèle} \textit{\textbf{Grid Computing}} L'arrivée de Christophe Cérin en 2005, permet à la conception d'algorithmes parallèles ou distribués de bénéficier d'une nouvelle impulsion, dans un cadre moins théorique et mieux adapté aux besoins en développement~: le \textit{Grid Computing}. L'évolution du calcul parallèle s'est progressivement orienté ces dernières années vers l'utilisation de composants standards. Ainsi est apparu le calcul sur \textit{réseaux de stations de travail} (ou \textit{Cluster Computing}). Ces nouvelles architectures parallèles atteignent des puissances de calcul de l'ordre du Téraflop. On est capable d'interconnecter plus de mille PC entre eux et de les faire communiquer par des interfaces répandues (de type Gigabit \textsc{Ethernet}) ou spécialisées (de type \textsc{Myrinet}). Depuis cinq ans est apparue la notion de \textit{grille}, qui vise à mutualiser les ressources, par exemple celles des PC des grands centres de recherche ou des internautes, connectés à Internet. Les grilles sont donc des environnements logiciels qui autorisent les applications à intégrer, à afficher, à instrumentaliser des ressources qui sont détenues par des organismes ou des individus situés dans différentes zones géographiques. Les paradigmes \textit{grappe} et \textit{grille} ont en commun le souci de partager des ressources de calcul, de stockage dans un but d'économie des moyens mis en \oe uvre. Le projet d'\acs{ANR} \textit{SafeScale} (\textit{Security And Fault-tolerance to Exploit Safety ambient Computing in lArge scaLe Environments} -- \texttt{https\string://www-lipn.univ-paris13.fr/safescale}) a été retenu fin 2005. Il est piloté par le \acs{LIPN} avec pour partenaires l'\textsc{ENSTB}, l'\acs{Irisa}, le \acs{LIG}, et l'université Joseph Fourier. Le \acs{LIPN} s'est positionné sur des aspects applicatifs. Il propose d'étudier deux applications~: le partitionnement de données et l'évaluation (détermination) de polynômes. Pour ces deux applications, il s'agit de distribuer des calculs et des données sur Internet et de vérifier le calcul produit en le comparant avec des résultats produits sur des sites de confiance. Pour le partitionnement de données, il s'agit de le faire par des techniques de vol de cycles plutôt que par des techniques statiques qui prédéterminent ce qu'il faut envoyer sur chacun des sites. Pour l'évaluation de polynômes, il s'agit d'implémenter dans un premier temps la méthode actuelle qui se prête bien à une distribution à large échelle et qui a été développée en particulier par Frédéric Toumazet de l'équipe \acs{LCR} et membre de \textit{SafeScale}. Dans un deuxième temps on greffera une certification des résultats mais il y a déjà un travail important à fournir pour construire l'architecture matérielle de calcul. Elle se fera très certainement à base d'\textsc{ExtremWeb} (\texttt{http\string://www.xtremweb.net}). \medskip \textbf{PGCD de deux entiers} Les travaux de recherche de Sidi Mohamed Sedjelmaci ont permis, quant à eux, de maintenir un très bon niveau de publications internationales en arithmétique parallèle (étude et analyse d'\textit{algorithmes parallèles du PGCD de deux entiers}). Le PGCD est une opération arithmétique fondamentale dont les applications sont multiples. La plupart des logiciels scientifiques utilisent l'algorithme séquentiel polynomial de Schönhage, de complexité en temps $O\left(n(\log n)^2 \log\log n\right)$ pour des entiers de $n$ bits. En calcul parallèle, on ignore si ce problème est dans la classe NC de P ou bien P-complet (la classe la plus \guillemotleft~difficile~\guillemotright\ de P). Deux directions de recherche s'imposent donc~: tenter une démonstration directe de l'appartenance du PGCD à la classe P-complet ou bien exhiber un algorithme parallèle de PGCD appartenant à NC. \subsubsection*{Algorithmique, combinatoire et complexité} \label{acc} Parmi les objets ou les structures les plus utilisés, on peut citer les mots, les arbres, les graphes et hypergraphes, les cartes, les chemins, les permutations, les partitions, etc. Parmi les exemples classiques d'opérations ou de manipulations, citons les bijections, les codages, l'énumération, la génération aléatoire, la visualisation, le coloriage et le (ré)étiquetage. Les problèmes combinatoires suscités par l'algorithmique peuvent être de nature diverse~: \bi \item[--]\ l'énumération et comptage d'objets permettant, en particulier, d'effectuer des analyses exactes et en moyenne d'algorithmes, \item[--]\ la représentation et la manipulation efficaces d'objets mathématiques variés (graphes, n\oe uds, groupes, séries formelles, etc.), \item[--]\ les calculs explicites sur ces objets, \item[--]\ la mise à jour de correspondances entre ces objets à travers des bijections, \item[--]\ la génération aléatoire, qui a pour objectif d'engendrer des objets combinatoires, non pas de façon exhaustive mais selon une loi de probabilité donnée~; \item[--]\ les études purement combinatoires des propriétés de certains objets ou familles d'objets comme les mots, les arbres, les chemins ou bien encore les (hyper)graphes. \ei \medskip \textbf{Propriétés de structures et de familles d'objets combinatoires} Les méthodes de la combinatoire analytique permettent de résoudre quantité de problèmes soulevés en algorithmique. Trois directions de recherche prédominent au sein de la composante AD. \begin{itemize} \item[--] D'une part, l'étude par Vlady Ravelomanana et Christian lavault des propriétés générales et extrêmales des graphes et hypergraphes aléatoires $\mathbb{G}(n,p)$, $\mathbb{G}(n,r)$ ou $\mathbb{H}(n,p)$ et de leurs algorithmes (processus d'apparition de composantes, taille de composantes, transitions de phase, régimes, couplages, etc.). \item[--] D'autre part, l'analyse par Cyril Banderier de la combinatoire des marches aléatoires sur $\mathbb{Z}$ ou $\mathbb{N}$, de chemins dirigés dans le plan (énumération en moyenne, asymptotique, etc.), en lien avec l'évolution d'une pile ou d'une file d'attente. \item[--] Enfin, la théorie de la coloration des graphes. Le partitionnement d'un ensemble d'objets en classes vérifiant certaines règles est un processus fondamental pour beaucoup de problèmes combinatoires. Un ensemble de règles simples peut nous permettre de savoir pour chaque couple d'objets si ils peuvent ou non appartenir à la même classe~: cette problématique concerne en particulier la théorie de la coloration des graphes. Une des directions de recherche de Mario Valencia-Pabon, Vlady Ravelomanana et Christian lavault consiste à étudier certains généralisations de problèmes de colorations des sommets ou des arêtes d'un graphe que l'on trouve souvent dans des problèmes d'ordonnancement de tâches. \end{itemize} \medskip \textbf{Mesure de complexité~: l'analyse perturbative (\textit{Smoothed Analysis})} Il s'agit d'une mesure de complexité intermédiaire entre le pire des cas et la complexité en moyenne qui semble adéquate pour quantifier la \guillemotleft~difficulté~\guillemotright\ d'un problème. Il paraît ainsi naturel de s'intéresser aux nombreux problèmes classés NP ou assimilés (d'optimisation et de combinatoire). En effet, être \guillemotleft~worst-case-NP~\guillemotright\ est fort différent d'être \guillemotleft~average-case-NP~\guillemotright, lui-même fort différent d'être \guillemotleft~average-case-NP sur une région suffisamment grande~\guillemotright. C'est de ce dernier point dont on a besoin, par exemple, pour avoir un cryptosystème fiable~: le pire des cas dans le \textit{paysage de complexité} de l'algorithme, ne doit pas être un pic isolé mais un plateau. Comment quantifier et étudier cette notion de \guillemotleft~problème difficile sur une grande région~\guillemotright~? C'est ici qu'intervient le concept de \textit{smoothed analysis} (traduit par \textit{analyse perturbative})~: où sont les instances difficiles~? Plus précisément, la complexité perturbée est ainsi définie comme le maximum sur les entrées du temps moyen mis par l'algorithme à s'exécuter sur les perturbations de l'entrée. \textit{L'analyse perturbative} étudie donc la complexité d'un algorithme (ou d'une valeur particulière) autour d'une instance perturbée. Comment se modifie le paysage de complexité d'un algorithme lorsque l'on perturbe les instances d'entrée autour d'éventuelles régions \guillemotleft~difficiles~\guillemotright~? L'analyse perturbative mesure la performance moyenne d'un algorithme autour d'une instance, permettant ainsi de déceler ces régions difficiles (cf.~\S~\ref{res2} -- résultats de Cyril Banderier). \subsection{Résultats significatifs} \label{res2} \subsubsection*{Conception et analyse d'algorithmes distribués} \smallskip \textbf{Classes générales d'algorithmes distribués} Dans ce domaine particulièrement vaste, de nombreux résultats significatifs ont été obtenus par Franck Butelle, Lucian Finta, Mourad Hakem (ordonnancement) et par Franck Butelle, Christian Lavault, Mario Valencia-Pabon (arbres optimaux contraints). On peut ainsi citer un grand nombre de \textit{protocoles d'ordonnancement dans les réseaux quelconques} (parallèles ou distribués et sous diverses contraintes matérielles ou temporelles)~\cite{ocad:ABFM05,ocad:BuFiHa07,ocad:HaBu04a}, plusieurs bons algorithmes de recherche d'un \textit{arbre optimal avec contraintes} (de diamètre ou de degré minimaux) dans un graphe \textit{quelconque}~\cite{ocad:BuBuLa04,ocad:LaVa08}, l'analyse poussée d'une \textit{élection anonyme} dans les anneaux~\cite{ocad:LaLo06}, et de nouvelles méthodes de conception de classes d'algorithmes distribués~: \textit{inversions de liens d'un réseau acyclique orienté}, \textit{inversions d'arcs d'un (multi)graphe quelconque}~\cite{ocad:LPF05}, etc. Grâce à des hypothèses plus réalistes (réseau arbitrairement grand et totalement distribué, groupes de tâches sporadiques dépendantes caractérisées par leurs échéances temporelles, pouvant apparaître sur n'importe quel site et à n'importe quel moment, etc.), Franck Butelle, Lucian Finta et Mourad Hakem ont récemment proposé un algorithme original d'ordonnancement distribué temps réel~\cite{ocad:BuFiHa07}. \medskip \textbf{Protocoles de communication dans les réseaux sans fil} Dans le domaine des \textit{protocoles de contrôle} pour la communication dans les réseaux sans fil, les résultats les plus significatifs se centrent autour d'études et d'analyses assez systématique des algorithmes probabilistes classiques du domaine (Christian Lavault et Vlady Ravelomanana). Plus précisément, la \textit{diffusion}~\cite{ocad:LMR07,ocad:LaOlRa08,ocad:R07}, l'\textit{initialisation}~\cite{ocad:DLPR04,ocad:LaOlRa08,ocad:R07}, l'\textit{élection}~\cite{ocad:LMR07}, le \textit{k-clustering}~\cite{ocad:R06b}, l'\textit{exclusion mutuelle}, le \textit{routage}~\cite{ocad:LOR,ocad:R07}, etc. Il faut noter de plus que la plupart des protocoles que nous avons proposés sont \guillemotleft~efficaces en énergie~\guillemotright, i.e. ils consomment très peu d'énergie. Dans~\cite{ocad:LMR07}, par exemple, les stations ne restent éveillées qu'au plus $O(\log\log(n))$ unités de temps pour une élection de complexité en temps $O(\log(n))$. Sur les graphes géométriques aléatoires pouvant servir de support de modélisation aux réseaux sans fil, Vlady Ravelomanana~\cite{ocad:R04} a quantifié les degrés des sommets ainsi que les taux de couverture durant le régime supercritique. Ces résultats ont permis de concevoir des protocoles d'initialisation~\cite{ocad:R07} lors des phases de déploiements aléatoires des stations de ces réseaux. \subsubsection*{Systèmes distribués et algorithmique parallèle} \smallskip \textbf{\textit{Grid Computing}} Christophe Cérin et Jean-Christophe Dubacq ont obtenu récemment un résultat significatif d'une partie des objectifs de leurs recherches dans l'\acs{ANR} \textit{SafeScale}~\cite{ocad:CDR06}, dont le LIPN est porteur. Ce travail propose des méthodes exactes et approchées pour déterminer les quantités de données à envoyer à chaque processeur d'un grappe de processeurs à partir d'une configuration donnée. Le schéma de partitionnement, réalisé dans un contexte où les processeurs sont hétérogènes, tient compte de la complexité (connue ou estimée) du traitement qui le suit. \medskip \textbf{PGCD de deux entiers} Le meilleur algorithme parallèle proposé à ce jour demeure celui de Chor et Goldreich (1990) de complexité $O(n/\log n)$ sur un modèle de PRAM \textit{CRCW} avec $n^{1+\epsilon}$ processeurs ($\epsilon > 0$ constante quelconque). Les résultats les plus récents dans ce domaine utilisent des techniques de \guillemotleft~réduction$k$-aire~\guillemotright\ (algorithmes \guillemotleft~accélérés~\guillemotright\ de Jebelean et Weber). En particulier, l'amélioration de l'algorithme de Weber par Mohamed Sedjelmaci permet de proposer plusieurs algorithmes parallèles plus performants~\cite{ocad:S04}. \subsubsection*{Algorithmique, combinatoire et complexité} \smallskip \textbf{Propriétés de structures et de familles d'objets combinatoires} \medskip \textbf{\textit{Graphes et hypergraphes aléatoires}} Vlady Ravelomanana travaille sur les \textit{tailles des composantes géantes dans les graphes aléatoires} $\mathbb{G}(n,p)$~\cite{ocad:R06a,ocad:R06b,ocad:R07}. Ses résultats montrent en particulier que ces composantes possèdent $O(\ell^{1/3}\,n^{2/3})$ sommets lorsque le nombre d'arêtes est exactement $n + \ell$, avec $\ell = o(n)$. Ces analyses fines montrent donc que durant la phase critique de transition la taille des plus grandes composantes d'un tel objet varie violemment de $O(\log{n})$ à  $O(n^{2/3})$ puis de manière plus douce de $O(n^{2/3})$ à $O(n)$ (en passant par toutes les phases intermédiaires). Ces résultats se généralisent aux hypergraphes aléatoires $\mathbb{H}(n,p)$~\cite{ocad:R06a,ocad:R06b,ocad:R07}. Ce sont là les premiers résultats concernant les tailles des composantes géantes durant ce phénomène, connu sous le nom de \textit{Double-Jump} d'Erd\H{o}s-Rényi. \medskip \textbf{\textit{\'Enumération de marches aléatoires sur}} ${\mathbb N}$ Ce sujet qui est l'objet d'études combinatoires depuis plus d'un siècle~\cite{ocad:BS05} reste cependant au c\oe ur de nombreuses disciplines~\cite{ocad:BK03}. Dans le cas d'un jeu de sauts autre que $+1$ et $-1$, l'étude de ces marches sur $\mathbb{N}$ devient fort délicate, néanmoins, une approche initiée par C. Banderier et Philippe Flajolet montre que de nombreux paramètres se prêtent à une étude énumerative et asymptotique exacte. Plus récemment, C. Banderier et B. Gittenberger~\cite{ocad:BG06} ont ainsi montré que l'aire sous une marche aléatoire a des moments algébriques, ouvrant la porte à une analyse fine de ce paramètre délicat relié à la fonction d'Airy. \medskip \textbf{\textit{Coloration d'arêtes d'un multigraphe}} Le résultat obtenu par Jean Cardinal, V. Ravelomanana et M. Valencia-Pabon \cite{ocad:CaRaVa07} sur un type de coloration d'arêtes d'un multigraphe connu comme \textit{chromatic edge strength} est intéressant dans le contexte des problèmes d'ordonnancement des tâches cycliques et parallèles. Il montre qu'il est toujours possible de trouver un ordonnancement pour ce type de tâches qui permet de minimiser à la fois le temps total d'exécution et le temps moyen avant qu'une tâche se termine. Ce problème est connu comme étant NP-difficile même si le (multi)graphe associé des tâches est bipartite, planaire et de degré maximum 3. \medskip \textbf{\textit{Noyaux de graphes dirigés}} C. Banderier, J.-M. Le Bars et V. Ravelomanana~\cite{ocad:BBR04} ont étudié une classe de graphes orientés (digraphes) avec une contrainte de coloriage due à Von Neumann et issue de la théorie des jeux (de type jeu de Nim). Cette contrainte est équivalente à la notion de \textit{noyaux d'un digraphe}, qui apparaît dans de nombreux domaines, non seulement en théorie des jeux mais aussi en théorie de la complexité, en intelligence artificielle (logique des défauts, argumentation en système multi-agents), loi 0-1 en logique monadique du second ordre, et en combinatoire (graphes parfaits), etc. La notion de noyau d'un digraphe débouche sur des questions difficiles (au sens de la NP-complétude, de la \#P-complétude, ou de l'approximation). Cependant, les auteurs ont montré qu'il est possible d'utiliser les séries génératrices et leurs singularités afin d'obtenir, par exemple, des résultats sur la taille du noyau dans un circuit ou dans un digraphe unicircuit, et la probabilité de gagner à certains jeux de Nim. C'est un premier pas vers un traitement des noyaux dans des graphes plus complexes, avec, par exemple, une approche à la Wright. Cette méthode peut être appliquée plus généralement à n'importe quelle contrainte \guillemotleft~locale\guillemotright\ de coloriage dans des structures combinatoires décomposables. \medskip \textbf{\textit{Mesure de complexité~: l'analyse perturbative}} Les résultats de C. Banderier, R. Beier et K. Mehlhorn~\cite{ocad:BBM03} ont déjà exhibé des paysages de complexité assez variés ou surprenants~; notamment certains dont le pire des cas classique n'est paradoxalement pas la région la plus difficile, etc. (Un succès de cette approche est, pour l'instant, une explication de la complexité polynomiale en pratique de la méthode du simplexe.) Notons que cette étude fait intervenir de l'asymptotique de coefficients de fonctions de variables complexes (vérifiant des équations différentielles d'un certain type) qui apparaissent de façon ubiquitaire en analyse d'algorithmes~; divers problèmes qui y sont liés demeurent toujours ouverts (cf.~\S~\ref{persprech2}). \subsection{Perspectives de recherche} \label{persprech2} Malgré la diversité des thèmes de recherche de la composante AD et de leurs perspectives, un souci commun est de progresser toujours plus dans la compréhension profonde des modèles, de la structure et des propriétés essentielles des objets analysés. Pour cela, des progrès notables doivent être réalisés dans la recherche et la compréhension d'outils adéquats plus sophistiqués, donc de plus en plus mathématisés. \subsubsection*{Conception et analyse d'algorithmes distribués} Nous trouvons un exemple presque paradigmatique de tels besoins dans les analyses de complexité d'algorithmes distribués. Après s'être intéressés à la complexité dans le pire des cas, les chercheurs ont borné la complexité \textit{en moyenne} de ces algorithmes. Nous nous proposons de raffiner ces analyses en moyenne (asymptotique exacte de l'espérance, variance, etc.), voire d'inclure des preuves d'existence et de mise en évidence d'une \textit{distribution limite} (lorsqu'elle existe). Seules des techniques de bon niveau mathématique peuvent autoriser ce type d'analyses~: séries génératrices, approximations asymptotiques (réelles ou complexes), méthodes probabilistes, etc. \medskip \textbf{Classes générales d'algorithmes distribués} \smallskip Le recrutement récent de Mario Valencia-Pabon procure déjà un élan et des compétences accrues (théorie des graphes, coloration, etc.)aux recherches en algorithmique distribuée. Un premier résultat, soumis en commun avec Christian Lavault, est la conception et l'analyse d'un algorithme performant de construction d'un \textit{arbre de recouvrement minimum à degré mimimum} d'un graphe quelconque~\cite{ocad:LaVa08}. Sur cette base, nous avons aussi commencé l'analyse en moyenne d'algorithmes de \textit{routage par retournement d'arcs} (total ou partiel) dans les graphes sans cycle orientés (DAG) quelconques. (Des résultats sont déjà obtenus pour la ligne et les forêts arborescentes.) \medskip Dans le vaste domaine de l'ordonnancement, Franck Butelle, Lucian Finta et Mourad Hakem prolongent leur étude de grandes classes de protocoles de contrôle distribués. Il s'agit d'abord d'algorithmes distribués d'ordonnancement sous \textit{divers types de contraintes} (matérielles et temporelles), puis ensuite, petit à petit, de leur \textit{relaxation partielle}. L'introduction d'algorithmes \textit{tolérants aux fautes} (pannes franches et transitoires, fautes quelconque, fautes byzantines, etc.) d'une part et, d'autre part, de la prise en compte de la \textit{finesse dans les délais de communication} dans les réseaux constituent autant de perspectives nouvelles vers la construction d'une palette très générale de ces classes de protocoles. Par ailleurs, ces travaux devraient s'intégrer en tant qu'outils pour le \textit{Grid Computing} (\textsc{Grid}5000). \medskip \textbf{Protocoles de communication dans les réseaux sans fil} Les problèmes en chantier dans cet axe de recherche sont fondamentaux pour la communication dans un \textsc{Manet}. Certains résultats pourraient être utilisés comme \guillemotleft~briques de base~\guillemotright\ pour des protocoles de contrôle de haut niveau déjà cités. L'objectif principal de Christian Lavault, Vlady Ravelomanana et Mario Valencia-Pabon est de réussir à émuler un réseau \textsc{Manet} à simple saut à l'aide d'un réseau \textsc{Manet} à sauts multiples, sans aucune information structurelle \textit{à priori} sur le graphe $G$ engendré. Les hypothèses (très générales) sont donc les suivantes~: \be \item initialement, les stations sont \textit{indiscernables} (symétriques et anonymes)~; \item les stations ne possèdent \textit{a priori} aucune connaissance structurelle (exacte ou partielle) de $G$, ni son nombre de noeuds $n$, ni son degré maximum $\Delta$, ni son diamètre $D$ (ou des majorants). \ee Il s'agit donc de surmonter l'absence d'information en évaluant l'ensemble des caractéristiques de $G$ et de construire pas à pas des algorithmes de diffusion probabilistes efficaces afin d'approcher $\Delta$, $D$ et enfin $n$ avec une erreur $\epsilon > 0$ faible. Les méthodes stochastiques et l'asymptotique (réelle et complexe) appliquées aux séries génératrices multivariées permettent d'obtenir des résultats suffisamment précis pour espérer résoudre ces problèmes de manière satisfaisante. \subsubsection*{Systèmes distribués et algorithmique parallèle} \smallskip \textbf{\textit{Grid Computing}} Deux ouvertures internes à Paris 13 sont amenées à se développer. \textbf{--} La première consiste à partir de la souche du logiciel de calcul sur grille de PC \textsc{XtremWeb} et de l'adapter dans un contexte bio-médical, une première collaboration entre le \acs{LIPN} et l'UFR SMBH est mise en place en 2006 via un stage de deuxième année d'élève ingénieur de Paris 13. Du coté SMBH, le Dr. Jean-Marie Rocchisani (MCU-PH Médecine Nucléaire, Paris 13) s'est intéressé depuis plusieurs années aux grilles médicales, notamment \textsc{HealthGrid} et plus particulièrement à leurs applications pour la plate-forme de simulation Monte Carlo GATE (\texttt{http\string://opengatecollaboration.healthgrid.org}). GATE est un outil performant de simulation des systèmes d'imagerie utilisant des rayonnements particulaire ou photonique, existants ou en cours de développement. A. Martineau et J.-M. Rocchisani ont déjà validé la modélisation avec GATE d'une \guillemotleft~gamma-caméra~\guillemotright\ dédiée à l'imagerie du petit animal et des petits organes. Les objectifs sont donc de paralléliser pour la grille l'application GATE pour la plate-forme \textsc{XtremWeb} (besoin du SMBH) et d'offrir également un niveau de certification des images produites par le système de calcul \textsc{XtremWeb} (besoin du \acs{LIPN}). Pour l'instant, dans le cadre de \textit{SafeScale}, il n'y a que de la certification symbolique qui est envisagée c'est à dire que la certification consiste soit à évaluer un polynôme soit à vérifier que le résultat est trié puis de garder ou rejeter le calcul. Dans le cas de GATE, la certification pourra utiliser plusieurs critères quantitatifs d'évaluation de la qualité des résultats des simulations de deux systèmes d'imagerie de référence (un \guillemotleft~Tomographe par Émission de Positons~\guillemotright\ et une \guillemotleft~gamma-caméra~\guillemotright). \textbf{--} La seconde est relative à la rénovation de la grappe commune \acs{LAGA}-\acs{LIPN}. Plusieurs financements (de l'ANR \textit{SafeScale}, \acs{CNRS}, interne à Paris 13) ont été injectés pour acheter des n\oe uds, du matériel d'interconnexion, de la climatisation. Cette infrastructure doit permettre aux deux laboratoires d'avoir une plate-forme de base afin de mettre au point des tests dimensionnants par exemple. Nous avons retenu une organisation matérielle à la \textsc{Grid}5000 c'est-à-dire hautement reconfigurable, seule garantie à notre avis pour que la plate-forme puisse être acceptée par le plus grand nombre de chercheurs des deux laboratoires. Les années qui arrivent vont permettre au groupe des grilles de commencer le travail de prototypage en interne avant déploiement dans \textsc{Grid}5000. \smallskip Au niveau national, concernant le projet \textit{SafeScale}, le \acs{LIPN} s'est en particulier positionné sur le plan des applications. Dans les 18 derniers mois du projet, nous avons en chantier~: \begin{enumerate} \item Le résultat obtenu dans~\cite{ocad:CDR06} préfigure une partie du programme de recherche de Christophe Cérin et Jean-Christophe Dubacq dans l'\acs{ANR} \textit{SafeScale}. Une collaboration étroite avec l'Imag (\acs{LIG}) autour des travaux de Daouda Traoré et de Serge Guelton pour les implémentations liées à l'intergiciel étudié \textsc{Kaapi} (\textit{Kernel for Adaptative, Asynchronous Parallel and Interactive programming}). Nous travaillons sur le partitionnement de données et l'auto-adaptativité --- comment faire recouvrir le temps de partitionnement avec la diffusion des données dans un contexte parallèle adaptatif (aux congestions réseaux par exemple). Nous avons également identifié le problème de la génération des éléments fréquents comme application pouvant bénéficier d'une technique adaptative de gestion des processus. L'idée est de commencer dynamiquement la génération des groupes de $k+1$ éléments fréquents avant d'avoir terminé la génération complète des groupes de $k$ éléments (méthode de l'algorithme classique). L'intergiciel \textsc{Kaapi} doit nous permettre de le réaliser de manière souple. \item En interne, Frédéric Toumazet doit proposer un code stable de son application de vérification de propriétés de polynômes avant la fin 2007 afin que nous puissions l'intégrer avec un intergiciel de type \textsc{XtremWeb}. \end{enumerate} \smallskip Au niveau international, deux co-tutelles de thèse viennent d'être mise en place avec l'\'Ecole Supérieure des Sciences et Technologies de Tunis (ESSTT). Le travail est orienté respectivement vers l'algorithmique parallèle de gestion des communications entre grappes de grappes et l'ordonnancement par vol de cycle d'une part et la gestion de données dans des systèmes pair-à-pair de publication d'annonces. L'opération de diffusion pour des grappes de grappes est étudiée dans le cadre d'heuristiques à partir d'arbres binomiaux convenablement définis. Par ailleurs nos travaux actuels et futurs se démarquent par le fait que nous visons à réaliser la diffusion lorsque les n\oe uds possèdent plusieurs cartes réseaux. Un premier travail expérimental~\cite{ocad:ACDJ07} autour de plusieurs systèmes pairs-à-pairs nous a permis de montrer en 2007 les limites de ces systèmes lorsqu'on les déploie sur un nombre relativement important de noeuds (300 processeurs). Nous envisageons plus particulièrement un travail sur le stockage des informations de gestion ou des données applicatives de programmes tournant sur des plate-formes de type grille de PC. En effet, les plate-formes actuelles sont fortement centralisées dans le sens ou un coordinateur central dispose de toutes les connaissances pour ordonnancer les travaux et, de plus n'utilisent pas les techniques pairs-à-pairs pour stocker les données générées en cours d'exécution. Ces deux aspects limitent les capacités de passage à l'échelle des intergiciels de grille de PC. \medskip \textbf{PGCD de deux entiers} Mohamed Sedjelmaci approfondit l'étude des algorithmes parallèles de calcul du PGCD en proposant deux variantes de l'algorithme d'Euclide, l'une \textit{binaire}, l'autre sous forme \textit{accélérée}. \subsubsection*{Algorithmique, combinatoire et complexité} \smallskip \textbf{Graphes et hypergraphes aléatoires} \textbf{--} Les \textit{graphes aléatoires géométriques} sont minutieusement étudiés par Penrose. Il subsiste cependant plusieurs problèmes ouverts, dont le \textit{rayon critique} des disques à partir duquel un graphe possède (asymptotiquement presque sûrement) un cycle hamiltonien. Vlady Ravelomanana a étudié jusqu'à présent les graphes aléatoires géométriques \textit{homogènes}, i.e. dont tous les points possèdent le même rayon. Dans un futur proche, nous nous proposons d'étudier ces structures lorsque les centres des disques, dispersés aléatoirement, disposent d'un rayon selon une certaine loi de probabilité. Ces problèmes sont intimement liés à ceux soulevés par la communication dans les réseaux sans fils (capteurs en particulier). En effet, toute station très utilisée voit sa batterie s'affaiblir rapidement et, par conséquent, son rayon de transmission et de réception diminuer en proportion. \textbf{--} Dans le domaine des (hyper)graphes aléatoires ($\mathbb{G}(n,p)$ ou $\mathbb{H}(n,p)$), nous nous intéressons aux problèmes liés aux transitions de phases. Typiquement, en augmentant la probabilité d'existence $p$ d'une arête, l'objet passe d'un état \guillemotleft~gazeux~\guillemotright\ à un état \guillemotleft~liquide~\guillemotright, puis d'un état \guillemotleft~liquide~\guillemotright\ à un état \guillemotleft~solide~\guillemotright. Nous avons pour objectif de caractériser de tels phénomènes dans un cadre général et unificateur, grâce aux techniques offertes par la combinatoire analytique et les méthodes probabilistes. \textbf{--} Il s'agit aussi d'étendre des résultats sur les graphes~\cite{ocad:R06a,ocad:R07b} à certaines variétés d'hypergraphes et ce, de la manière la plus générale possible. Notre second but est d'utiliser ces résultats afin de quantifier les transitions de phases dans les instances aléatoires des problèmes de satisfiabilité tels que $2$-XORSAT, $(2+k)$-SAT ou SAT, qui sont des problèmes centraux en théorie de la complexité. Ensuite, nous nous proposons d'exploiter les résultats et les méthodes obtenus pour concevoir et analyser des algorithmes classiques d'optimisation combinatoire (couplages, ensembles indépendants, cliques, etc.). Ces travaux pourront enfin servir de briques de base pour les études d'approximation en moyenne d'algorithmes (cf. paragraphe \textit{Approximation en moyenne et analyse perturbative \textsc{(Aperox)}} ci-dessous). \medskip \textbf{Combinatoire des mots circulaires et des permutations} Ce projet vise à ébaucher un début d'\textit{unification} de la recherche en combinatoire (analytique et algébrique) au \acs{LIPN}~; ces premiers pas s'effectuent par une coopération (déjà en \oe uvre) entre les combinatoriciens de l'équipe \acs{OCAD} et ceux du thème \textit{Combinatoire} de l'équipe \acs{LCR}. Le rapport de Master (2006) et le sujet de thèse de Hichem Kenniche (co-encadré par Gérard H. E. Duchamp et Christian Lavault) s'inscrivent dans cet objectif. En effet, l'étude et l'analyse d'algorithmes et de structures combinatoires dans des cycles de permutations complètent avec grand profit leur combinatoire algébrique. La statistique des objets combinatoires relatifs aux permutations \guillemotleft~classiques~\guillemotright\ (pics, creux, doubles montées-descentes) s'obtient aisément à partir de leurs séries génératrices. Il existe cependant peu de travaux généralisant ces résultats aux permutations dites \guillemotleft~en anneau~\guillemotright\ (ou \textit{unicycliques}), i.e. dans une même classe d'équivalence de cycle définie aux permutations circulaires près. Il en est de même pour l'application à l'analyse en moyenne d'algorithmes distribués d'élection avec identités sur un anneau (en cycle) qui procèdent par élimination des pics (creux) de ces identités. La série génératrice associée et l'asymptotique des coûts permettent de calculer les premiers moments de la complexité en temps et en messages, puis de prouver l'existence d'une distribution limite (si elle existe), etc. Le but est, en effet, d'associer les approches analytique et algébrique et d'étendre leurs résultats de manière à lever les verrous scientifiques dus aux différentes représentations des objets combinatoires \guillemotleft~circulaires~\guillemotright\ en général~: sur un alphabet $\Sigma$, propriétés des colliers construits sur $\Sigma^{*}$, évaluation de la longueur moyenne des occurrences d'un symbole de $\Sigma$ dans un collier, etc. \medskip \textbf{Approximation en moyenne et analyse perturbative (\textsc{Aperox})} Le projet \textsc{Aperox} repose sur l'emploi d'outils mathématiques pour étudier la \guillemotleft~qualité~\guillemotright\ d'algorithmes approchés pour des problèmes \guillemotleft~difficiles~\guillemotright\ d'optimisation discrète (NP-h). \textsc{Aperox} associe ainsi deux domaines de recherche qui constituent, depuis plus de dix ans, deux axes forts d'\acs{OCAD}~: la mesure de complexité d'un algorithme et l'évaluation des solutions retournées par un algorithme, pour un problème donné~; il exploite des compétences et des complémentarités de l'équipe en analyse en moyenne d'algorithmes (Cyril Banderier et Vlady Ravelomanana) et en approximation polynomiale (Sophie Toulouse). Précisément, le projet se propose d'initier deux approches nouvelles~: \bi \item[--]\ \textit{l'approximation en moyenne}, qui mesure le degré d'approximation d'un problème sur des instances aléatoires~; \item[--]\ \textit{l'analyse perturbative}, déjà détaillée au \S~\ref{acc}. \ei Concernant l'approximation en moyenne, les motivations sont les suivantes~: outre le fait de disposer d'un indicateur complémentaire d'évaluation des algorithmes, l'analyse en moyenne du rapport d'approximation permet surtout de fournir des informations sur les problèmes qui sont non- ou mal approximables (tels, notamment, les problèmes MaxSAT, MaxCCSP, MaxIS, etc.)~; plus spécifiquement, de même que s'affranchir de l'exactitude pour la résolution des problèmes NP-difficiles (NP-h) permet de structurer NP-h en fonction du degré d'approximation des problèmes (classes (D)PTAS, (D)APX, (D)PolyAPX, etc.), s'affranchir du pire cas pour les problèmes zéro-approximables en différentiel (0-DAPX) devrait offrir une certaine structuration des problèmes 0-DAPX (ou plus largement, des problèmes non approximables à rapport constant) en fonction de leur degré d'approximation en moyenne (approximable à rapport moyen constant, polynomial, etc.). Toujours dans le sens d'une évaluation plus fine des algorithmes, on pourrait envisager de faire l'analyse perturbative du rapport d'approximation~; si une telle démarche offrirait en effet un indicateur encore plus significatif de la qualité d'un algorithme, le défi semble cependant plus qu'ambitieux. Aussi, à défaut d'analyser le comportement du rapport lui-même, il serait intéressant d'étudier le comportement de la valeur d'une solution optimale, d'une pire solution, d'une solution approchée définie structurellement (ex.~: un optimum local). Par ailleurs, faire l'analyse en moyenne d'une solution retournée au voisinage (perturbé) d'une pire instance (instance réalisant le pire cas d'un algorithme donné) donnerait plus de sens à l'analyse pire cas de l'algorithme considéré, en proposant une réponse à la question~: le pire cas est-il significatif~? \subsection{Diffusion de la recherche} \subsubsection*{\'Evaluation de la recherche} \label{dif2} \paragraph{Comités éditoriaux} \begin{itemize} \item[-- C. Cérin] Éditeur en chef d'un numéro spécial de \textit{Parallel Computing} en 2006-2007. \item[-- C. Lavault] Membre du comité de rédaction de \textit{Studia Informatica Universalis} depuis 2001. \item[-- C. Lavault] Membre du comité scientifique de \textit{Parallélisme, réseaux et répartition} depuis 1995. \end{itemize} \paragraph{Comités de programmes} \begin{itemize} \item[-- Christophe Cérin, Jean-Christophe Dubacq et Lucian Finta (2007).] Membre du comité de programme de la Conférence \textit{Grid and Pervasive Computing} (GPC-2007), France, 2-4 mai 2007. \item[-- Jean-Christophe Dubacq (2007).] Membre du comité de programme du numéro spécial de la revue \textit{Parallel Computing} (PARCO), Elsevier. \item[-- Christian Lavault (2007).] \textit{Co-chair} de la \textit{3rd International Conference on Mobile ad-hoc and Sensor Networks} (MSN-2007), Beijing (Chine), 12-14 déc. 2007. \item[-- Christian Lavault (2007).] Membre du comité de programme de la Conférence \textit{The 2007 International Symposium on Parallel and Distributed Processing with Applications} (ISPA-2007), Canada, 21-24 août 2007. \item[-- Mario Valencia-Pabon (2007).] Membre du comité de programme de la Conférence \textit{Latin-American Algorithms, Graphs and Optimization Symposium} (LAGOS-2007), Chili, 25-29 nov. 2007. \item[-- Christophe Cérin (2007).] Program Chair pour un numéro spécial de la revue \textit{Parallel Computing} (PARCO). \item[-- Christophe Cérin (2006).] Program Co-Chair de \textit{Grid and Pervasive Computing} (GPC'2006). Membre des comités de programme de SBAC, AINA, GPC et de RenPar 2006. Finance Chair de HPDC'2006. %\item[-- Christophe Cérin (2006).] \item[-- Christian Lavault (2003, 2004, 2005).] Membre des comités de programme d'OPODIS (\textit{International Conference on Principles of Distributed Systems}) en 2003, 2004 et 2005. \item[-- Cyril Banderier (2003).] Responsable du comité de programme de la conférence \textit{Marches aléatoires discrètes~: théorie et applications en combinatoire, biologie algorithmique, informatique théorique, probabilités, physique statistique} (DRW-2003), IHP, 2003. \end{itemize} \paragraph{Comités de lecture ou d'évaluation} \begin{itemize} \item[-- Cyril Banderier.] Rapporteur d'une vingtaine d'articles pour des revues et conférences internationales (Algorithmica, Disc. Math., JCT-a, JTNB, RSA, TCS, EJC, SLC, DRW, FPSAC, Gascom, Mathinfo, MFCS, IEEE, Proba. Stat., etc.). \item[-- Franck Butelle.] Rapporteur d'une demi-douzaine d'articles pour des revues et conférences internationales (Ann. of Telecom, Int. J. on Fondations of Comp. Science, IPDPS, etc.). \item[-- Christophe Cérin.] Rapporteur d'une demi-douzaine d'articles pour des revues et conférences internationales (IEEE Trans. on Comp., AINA, IPDPS, GPCSBAC, etc.). Finance Chair de HPDC'2006. \item[-- Christian Lavault.] Rapporteur d'une vingtaine d'articles pour des revues et conférences internationales. (Acta Inf., Dist. Comput., Inf. \& Comput., IPL, Par. \& Dist. Comput., Par. Proc. Letters, Studia Inf. Univ. , TCS, DISC, ICALP, IEEE Int. Conf. on CS and Appli., ICDCS, MFCS, OPODIS, SIROCCO, IEEE TPDS, etc.). \item[-- Vlady Ravelomanana.] Rapporteur d'une quinzaine d'articles pour des revues et conférences internationales. (Disc. Maths and TCS, IPL, J. of Algo., J. de Th. des Nombres de Bordeaux, Par. Proc. Letters, RSA, TCS, IEEE TPDS, IEEE/ACM Trans. on Net., DRW, FPSCAC, HICSS, IEEE Int. Conf. on CS and Appli., etc.). \item[-- Mario Valencia-Pabon (2006-2007).] Rapporteur d'une douzaine d'articles pour des revues et conférences internationales (App. Disc. Maths., Disc. Maths., J. of Comput. and App. Maths, STACS, LAGOS, etc.). \end{itemize} \paragraph{Autres responsabilités d'évaluation} \begin{itemize} \item[-- Christophe Cérin (2003-2006).] Membre du jury du prix de thèse de Spécif. \item[-- Christian Lavault (2007).] Rapport d'évaluation d'un projet du COFECUB (\textit{COmité Français d'Èvaluation de la Coopération Universitaire et scientifique avec le Brésil})~: \textit{Modèles hybrides et adaptatifs pour la construction des systèmes répartis adaptés au facteur d'échelle (scalable)}. \item[-- Christian Lavault (2006).] Rapport d'évaluation pour la nomination de la professeure P. Flocchini comme \textit{Full Professor} de l'Université d'Ottawa (CRU -- Ontario, Canada). \item[-- Christian Lavault (2005).] Rapport d'évaluation pour nomination de la professeure P. Flocchini à une Chaire de recherche de l'Université d'Ottawa (CRU -- Ontario, Canada). \end{itemize} \paragraph{Jurys hors \acs{LIPN}} \begin{itemize} \item[Jurys de thèse :] Cyril Banderier (rapporteur~: 1). Christophe Cérin 3 (rapporteur~: 2). Christian Lavault 16 (rapporteur~: 7). \item[Jurys d'habilitation à diriger des recherches :] Christian Lavault (2). \end{itemize} \subsubsection*{Organisation de la recherche} \paragraph{Responsabilité de groupes de travail du \acs{CNRS}} \begin{itemize} \item[--] Christian Lavault. Responsable du groupe \textit{Combinatoire analytique} de \textsc{MathSTIC} \textit{Alea} dans le GDR 673 du CNRS \textit{Informatique Mathématique} (IM). Responsable de l'équipe \textit{Combinatoire et analyse d'algorithmes distribués} (CADAD) du groupe de travail \textit{ALEA} dans le projet \acs{CNRS} \textit{MathSTIC} de décembre 2001 à janvier 2006 (laboratoires partenaires~: LaRIA, université d'Amiens, et \acs{LIPN}). \item[--] Christophe Cérin. Responsable depuis 2007 du groupe \textit{Sécurité, Sureté} dans le GDR ASR (Architecture, système, Réseaux). \end{itemize} \paragraph{Organisation de conférences et événements scientifiques} \begin{itemize} \item[--] Cyril Banderier (2005-2006)~: coorganisation des Congrès \textit{MATh.en.JEANS}. \item[--] Christophe Cérin, J.-C. Dubacq et L. Finta (2007)~: organisateurs locaux de la conférence \textit{Grid and Pervasive Computing} (GPC-2007), France, 2-4 mai 2007. \item[--] Christophe Cérin (2006)~: organisateur en 2006 d'un numéro spécial de la revue \textit{Parallel Computing} sur les \textit{Large Scale Grids}. \item[--] Christophe Cérin (2005)~: co-organisateur en 2005 d'un workshop en marge de la conférence \textsc{Europar} (Lisbonne) sur les système de Grilles (workshop sur invitation). \item[--] Christian Lavault, V. Ravelomanana (2005)~: membres du comité d'organisation (avec J.-M. Le Bars) des \textit{Journées ALEA} 2005 (CIRM, \textsc{smf}-\acs{CNRS}, Luminy). \item[--] Cyril Banderier, Christian Lavault, Vlady Ravelomanana (2003)~: comité d'organisation de la conférence \textit{Marches aléatoires discrètes~: théorie et applications en combinatoire, biologie algorithmique, informatique théorique, probabilités, physique statistique} (DRW-2003), IHP, 2003. \end{itemize} \subsubsection*{Contrats} %\vskip 1cm \noindent {\footnotesize \begin{tabular}{lp{.5cm}lllp{1cm}p{.5cm}p{.5cm}p{.5cm}} \rotatebox{40}{Type} & \rotatebox{40}{Coordinateur} & \rotatebox{40}{Resp. scient.} & \rotatebox{40}{Nom} & \rotatebox{40}{Financeur} & \rotatebox{40}{Période} & \rotatebox{40}{Durée (mois)} & \rotatebox{40}{Budget global (k\texteuro)} & \rotatebox{40}{Part LIPN (k\texteuro)} \\ \acs{PAI} & $\bullet$ & C. Banderier & Amadeus & Égide & 01/2005-12/2006 & 24 & 18 & 9 \\ \acs{ANR} & $\bullet$ & C. Cérin & \textit{SafeScale} & \acs{CNRS} & 01/2006-12/2008 & 36 & 337 & 70 \\ \acs{ACI} & & C. Cérin & \textit{Grid Explorer} & \acs{CNRS} & 06/2003-07/2006 & 36 & 2000 & \\ \acs{AUF} & $\bullet$ & C. Lavault & \textit{Coop. \acs{AUF}} & \acs{AUF} & 07/2006-12/2008 & 24 & 22 & \\ \acs{ECOS} & $\bullet$ & C. Lavault & \textit{Action \acs{ECOS}} & \acs{ECOS}-Sud & 01/2008-01/2011 & 36 & 63 & \end{tabular}} \subsubsubsection{\acs{ANR} \textsc{\textit{SafeScale}}} \textit{Autres partenaires : universités de Grenoble, Rennes et Brest} Le projet d'\acs{ANR} \textsc{\textit{SafeScale}} -- \textit{Security And Fault-tolerance to Exploit Safety ambient Computing in lArge scaLe Environments} est piloté par le \acs{LIPN} et regroupe des laboratoires à Grenoble, Rennes et Brest. Quatre chercheurs du \acs{LIPN} y sont représentés : Christophe Cérin, Jean-Christophe Dubacq, Lucian Finta et Frédéric Toumazet. Ce projet a été labélisé fin 2005. Par ailleurs et en liaison avec les grilles, le \acs{LIPN} s'est également positionné dans l'initiative fr-\textsc{Grid} qui vise à installer un portail d'accès à la grille opérationnelle. Ce projet est porté par Ph. d'Anfray (Renater) et C. Cérin. L'embryon de portail est sur \texttt{http\string://www.fr-grid.org}. Parmi les objectifs affichés de cette initiative figure la formation (une semaine de formation sera organisée début 2007). \subsubsubsection{\acs{ACI} \textsc{\textit{Grid Explorer}, \acs{Inria}-\acs{STIC}}} \textit{Autres partenaires : \acs{Inria}, universités de Grenoble, Tunis et Versailles} Christophe Cérin participe à l'\acs{ACI} \textsc{\textit{Grid Explorer}} et à un projet \acs{Inria}-\acs{STIC}-université Tunisienne en cours de montage pour un renouvellement. Il sera porté par le \acs{LIPN} avec comme partenaires Grenoble, Versailles, \acs{Inria} Futur, \textsc{esstt} et la Faculté des Sciences de Tunis. \subsubsubsection{Coopération \acs{AUF}} \textit{Autres partenaires : universités d'Antananarivo et de Bruxelles (ULB)} Ce projet de coopération de l'\acs{AUF} de deux années (2006-2008) regroupe trois universités francophones, l'\textit{Université d'Antananarivo} (Tananarive, Madagascar), l'\textit{Université Libre de Bruxelles} (ULB, Bruxelles, Belgique) et l'université Paris 13. Ses objectifs visent à la formation et au renforcement d'un troisième cycle en informatique théorique et mathématiques discrètes à l'université d'Antananarivo (formation doctorale IGMA, \textit{Informatique et Génie Mathématique}). Il s'agit en particulier de cours dans le cadre du DEA IGMA, d'encadrements de doctorants et de stagiaires en Master recherche, ainsi que d'échanges interuniversitaires de chercheurs. \\ Co-responsables~: C. Lavault (Paris 13) et A. Randrianarivony (Un. d'Antananarivo). Responsables locaux~: J. Cardinal (ULB), C. Lavault et V. Ravelomanana (Paris 13), A. Randrianarivony (Un. d'Antananarivo). \subsubsubsection{Action \acs{ECOS}-\acs{SECyT}} \textit{Autres partenaires : universités de Buenos Aires, Nationale de la Plata (Argentine), de Chile, Columbia University, de Magdeburg et de Rio de Janeiro} Le projet franco-argentin \acs{ECOS}-\acs{SECyT} \textit{Coloration des graphes : généralisations et applications aux jeux combinatoires} a pour partenaires institutionnels \acs{ECOS}-Sud (Ministère des Affaires Étrangères et Ministère de l'Éducation Nationale) et \acs{SECyT} (Secretaría de Ciencia, Tecnología e Innovación Productiva). Cette coopération de recherche universitaire implique deux laboratoires, le LIPN (Un. Paris 13, France) et le Departamento de Computación (Facultad de Ciencias Exactas y Naturales, Un. de Buenos Aires, Argentine). \\ Cinq chercheurs du LIPN y participent~: Christian Lavault (\acs{PU}), Mario Valencia-Pabon (\acs{MCF}), Sophie Toulouse (\acs{MCF}), Vlady Ravelomanana (\acs{MCF}) et Hichem Kenniche (doctorant). \\ Co-responsables~: Christian Lavault (LIPN, Un. Paris 13) et Pablo Jacovkis (\acs{PU}, Departamento de Computación, Un. de Buenos Aires). \smallskip Par ailleurs, Mario Valencia-Pabon participe à l'action de collaboration internationale \textit{Théorie des graphes et optimisation combinatoire} pilotée par l'Université de Buenos Aires (Argentine) dans le cadre de l'ANPCyT. Les six partenaires de ce projet de recherche scientifique et technologique d'une durée de 38 mois sont l'Un. de Buenos Aires (Argentine), Columbia University (USA), l'Un. de Magdeburg (Allemagne), l'Un. de Paris 13 (France), l'Un. Nationale de la Plata (Argentine), l'Un. Fédérale de Rio de Janeiro (Brésil) et l'Un. de Chile (Chili). (Budget global~: 225 000 euros.) \subsubsection*{Dissémination} \paragraph{Actions de vulgarisation de la recherche} \begin{itemize} \item[--] Cyril Banderier (2003 à 2006)~: \\ \hspace*{.5cm} Congrés \textit{MATh.en.JEANS} (Paris, 2004-2006). \\ \hspace*{.5cm} Journées \textit{Savante Banlieue} (Villetaneuse, 2003-2006)~: stand et/ou miniconférence. \\ \hspace*{.5cm} Rencontres \acs{CNRS} Jeunes \textit{Sciences et Citoyens} (Futuroscope de Poitiers, 2005-2006). \\ \hspace*{.5cm} Intervention en collège à Epinay sur Seine (2004-2006). \\ \hspace*{.5cm} Rencontres \acs{CNRS} Jeunes \`a Drancy en 2006. \\ \hspace*{.5cm} Salon 2006 de la culture et des jeux mathématiques (Paris, 2005-2006)~: \\ \hspace*{.5cm} animation du stand \acs{CNRS}\textit{/MATh.en.JEANS}. \\ \hspace*{.5cm} Projet \textit{Animath} sur Pi, journée au Palais de la découverte (juin 2006). \\ \hspace*{.5cm} \textit{Fête de la science}, Math pour tous/Cité des Sciences (Paris, 13-15 octobre 2006). %A CASER OU PAS : - Journée séminaire de la filière Math-Info de Paris 13 (Villetaneuse) (November 4, 2005) \item[--] Christophe Cérin, Jean-Christophe Dubacq (2006)~: Coordination de l'intervention du LIPN à \textit{Savante banlieue}. \end{itemize} \paragraph{Invitations, tutoriels} \begin{itemize} \item[--] Cyril Banderier (2003)~: Journées du \acs{LIPN}, \acs{IG} (26-27 mai 2003). \item[--] Cyril Banderier (2003)~: Rencontres mathématiques de Rouen \guillemotleft~in honor of Claude Dellacherie\guillemotright, Rouen (18-20 juin 2003). \item[--] Cyril Banderier (2004)~: Séminaire d'algorithmique du GREYC, Caen (26 Octobre 2004) \item[--] Cyril Banderier (2005)~: \textit{Joint Seminar}, TU Wien/U Wien. (15 novembre 2005) \item[--] Cyril Banderier (2006)~: Séminaire de théorie des nombres et de combinatoire, Lyon (3 octobre 2006) \item[--] Christophe Cérin (2005-2006)~: invitation annuelle à Tunis pour les \textit{Journées du parallélisme} et dans le cadre d'un projet \acs{Inria} \textsc{stic} avec les universités tunisiennes. \item[--] Christian Lavault (2006)~: \textit{Advanced Research Workshop on Information Security in Wireless Networks}, NATO-ARW, septembre 2006, Suceava (Roumanie). Tutoriel invité~: \textit{Link Reversal Routing Algorithms in \textsc{MANET}s}. \item[--] Vlady Ravelomanana (2006)~: \textit{Advanced Research Workshop on Information Security in Wireless Networks}, NATO-ARW, septembre 2006, Suceava (Roumanie). Tutoriel invité~: \textit{Random Geometric Graphs and Wireless Networks}. \item[--] Christian Lavault et Vlady Ravelomanana (2005)~: \textit{Journées ALEA} 2005 (CIRM, \textsc{smf}-\acs{CNRS}, Luminy). \end{itemize} \subsubsection*{Collaborations universitaires et invitations} \begin{itemize} \item 1999-2004. Christian Lavault. Dans le cadre d'une coopération ERASMUS-SOCRATES , échanges avec l'\textit{université Polytehnica} de Bucarest (Roumanie). \\ Responsables~: V.~\textsc{Cristea} et A.~\textsc{Florea}.) \item 2005-\ . Christophe Cérin. Projet \acs{Inria} \textsc{stic}-université Tunisienne qui vise la formation doctorale en Tunisie et s'appuie sur un programme de recherche entre Grenoble, Versailles, Villetaneuse et la faculté des sciences et l'\textsc{esstt} de Tunis. \item 2006-2008. Cyril Banderier, Christian Lavault, Vlady Ravelomanana, Sophie Toulouse. Coopération \acs{AUF} entre trois universités francophones, l'\textit{université d'Antananarivo} (Tananarive, Madagascar), l'\textit{université Libre de Bruxelles} (ULB, Bruxelles, Belgique) et l'université Paris 13. Le projet consiste à développer la formation et le renforcement d'un troisième cycle en informatique théorique et mathématiques discrètes à l'université d'Antananarivo (formation doctorale IGMA, \textit{Informatique et Génie Mathématique}). \\ Responsables~: C. Lavault (Paris 13) et A. Randrianarivony (Un. d'Antananarivo). Responsables locaux~: J. Cardinal (ULB), C. Lavault et V. Ravelomanana (Paris 13), A. Randrianarivony (Un. d'Antananarivo). \end{itemize} %\subparagraph{Autres échanges / collaborations interlaboratoires} \hfill %\paragraph{\'Echanges universitaires et collaborations industrielles} \hfill %\paragraph{Collaborations industrielles} \hfill %\subparagraph{Autres collaborations industrielles} \hfill \subsection{Formation à la recherche} %\paragraph{Invitations à des écoles (printemps, été, hiver, automne, \textit{autre })} \medskip \no \textit{\textbf{Thèses soutenues}} \bi \item[2002-2006.] Mourad Hakem~: \textit{Ordonnancements distribués} \\ Financement de thèse~: \\ Soutenue le 16 décembre 2006 \\ Directeur~: Christian Lavault. Encadrant~: Franck Butelle \\ Situation actuelle du diplômé~: postdoctorant. \item[2001-2005.] Gabriel Paillard~: \textit{Quelques contributions à l'algorithmes distribués} \\ Financement de thèse~: allocation de recherche brésilienne \\ Soutenue le 28 juin 2005 \\ Directeur~: Christian Lavault \\ Situation actuelle du diplômé~: assistant en Informatique à l'Universitad Federal du Ceara (Brésil) depuis septembre 2006. \ei %\medskip \no \textit{\textbf{HDR soutenues}} \medskip \no \textit{\textbf{Doctorants}} \\ \medskip \noindent{ \footnotesize \begin{tabular}{lll} nom & date & position actuelle pour thèses \\ %H. Mourad & 10/02-06/07 & \acs{ATER} \acs{IG} \\ T. Andriamampinina & 10/03-12/07 & \acs{AM} \acs{IG} \\ E. Levy & 10/03-12/07 & Assistant ULB (Belgique) \\ A. Rasoanaivo & 10/06-12/09 & bourse \acs{AUF} \\ H. Kenniche & 10/06-12/09 & bourse \acs{IG} \end{tabular}} \paragraph{Cours de DEA / Master 2 recherche} \begin{itemize} \item[-- 2003 à 2004.] (F. Butelle)~: \textit{algorithmique du texte}, DEA ISCCA, Paris~8-EPHE. \item[-- 2003 à 2004.] (C. Lavault)~: \textit{Introduction à l'analyse des algorithmes}, DEA ISCCA, Paris~8-EPHE. \textit{Introduction à l'analyse des algorithmes distribués}, DESS IED (enseignement à distance), Paris~8. \item[-- 2003 à 2005.] (C. Lavault)~: \textit{Algorithmique distribuée}, DEA \acs{IA}-\acs{OC}, \acs{IG}. \item[-- 2005 à 2007.] (C. Banderier, C. Lavault, V. Ravelomanana)~: \textit{Combinatoire analytique}, 2\ieme année de Master Recherche Mathématiques-Informatique, \acs{IG}. (Commun avec le Master Mathématiques-Informatique-Technologies 2\ieme année recherche (\textit{Mathématiques et Applications au codage et à la cryptologie}), Paris~8.) \item[-- 2006-2008] (C. Banderier, C. Lavault, V. Ravelomanana)~: \textit{Algorithmique et Combinatoire analytique}, DEA IGMA (\textit{Informatique et Génie Mathématique}), Université d'Antananarivo (Madagascar). \end{itemize} \paragraph{Stages de DEA / Master 2 recherche} \begin{itemize} \item[-- 2003.] (C. Lavault)~: E. Levy (DEA \textsc{ia-oc} Paris 13, \textsc{mpri2})~: \textit{Analyse et conception d'un algorithme distribué de cycle hamiltonien pour les graphes aléatoires de type $\mathbb{G}(n,p)$}. \item[-- 2005.] (C. Lavault, V. Ravelomanana)~: Thanh-Binh Doan (DEA \acs{IA}-\acs{OC} Paris 13)~: \textit{Algorithmique des réseaux radio}. \item[-- 2006.] (G. Duchamp, C. Lavault)~: H. Kenniche (Master MMI2 Paris 13, \acs{LIPN})~: \textit{Combinatoire des mots circulaires et permutations}. \item[-- 2006.] (V. Ravelomanana, S. Toulouse)~: H. Razafisambatra (DEA IGMA Tananarive)~: \textit{Approximation de problèmes définis sur des collections d'ensembles}. \item[-- 2006.] (V. Ravelomanana, S. Toulouse)~: S. Djabali (P6-UPMC, \acs{LIPN})~: \textit{Approximation en moyenne}. % \item[-- 2007.] \end{itemize}