Titre : Election du chef dans les réseaux radio.
Auteurs : Dariusz Kowalski, Andrzej Pelc
Résumé:
Nous étudions un des problèmes fondamentaux du calcul distribué, l'élection du chef, dans les réseaux radio ad hoc modélisés par des graphes non-orientés. Une capacité importante des noeuds dans un réseau radio c'est la détection de collisions: la possibilité de distinguer une collision du bruit de fond qui a lieu quand aucun voisin ne transmet. Est-ce que la détection de collisions permet d'accélérer l'élection du chef dans les réseaux radio arbitraires? Nous donnons la réponse affirmative à cette question. Notre résultat principal est un algorithme déterministe d'élection du chef qui travaille en temps O(n) dans tous les réseaux de n noeuds, si la détection de collisions est présente. D'autre part c'est connu que sans cette capacité l'élection du chef exige un temps Omega (n log n), même dans les réseaux complets.
Titre : Consensus et exclusion mutuelle dans un canal à accès multiple.
Auteurs : Jurek Czyzowicz, Leszek Gasieniec, Dariusz Kowalski, Andrzej Pelc
Résumé:
Nous étudions la faisabilité déterministe et la complexité de deux tâches fondamentales du calcul distribué: le consensus et l'exclusion mutuelle. Les processus ont des identificateurs distincts et communiquent à travers un canal à accès multiple. Nous considérons trois caractéristiques qui peuvent exister ou ne pas exister dans le canal: la détection de collisions, la présence de l'horloge globale et la connaissance du nombre n de tous les processus. Si aucune de ces trois caractéristiques n'est présente dans le canal, nous prouvons que le consensus et l'exclusion mutuelle sont impossibles. Si au moins une d'entre elles est présente, les deux tâches sont possibles et nous étudions leur complexité de temps. Nous montrons que la détection de collisions produit une lacune exponentielle dans la complexité. Ensuite nous étudions le consensus et l'exclusion mutuelle en absence de la détection de collisions mais en supposant la présence alternative des deux autres caractéristiques.
Titre : Rendez-vous dans le plan et dans les réseaux.
Auteurs : Jurek Czyzowicz, Arnaud Labourel, Andrzej Pelc
Résumé:
Deux agents mobiles (robots) avec identités distinctes doivent se rencontrer dans un graphe inconnu connexe, possiblement infini, ou dans un terrain connexe dans le plan. Les agents sont modélisés par des points et leurs routes dépendent de leurs identités et de l'environnement inconnu. Le chemin parcourru par chaque agent dépend aussi d'un adversaire asynchrone qui peut controler la vitesse des agents. Est-ce qu'il existe un algorithme déterministe qui permet aux agents de se rencontrer en dépit de cet adversaire puissant? Nous construisons des algorithmes déterministes de rendez-vous pour des agents qui partent des noeuds arbitraires d'un graphe anonyme connexe quelconque (fini ou infini) et pour les agents qui partent de n'importe quels points internes à coordonnées rationnelles d'un terrain connexe fermé.
Titre : Rendez-vous dans les réseaux avec mémoire logarithmique.
Auteurs : Jurek Czyzowicz, Adrian Kosowski, Andrzej Pelc
Résumé:
Deux agents mobiles identiques doivent se rencontrer dans un noeud d'un graphe inconnu connexe. Notre résultat principal établit la grandeur minimale de la mémoire des agents qui garantie le rendez-vous lorsque celui-ci est faisable. Nous montrons que cette grandeur minimale est Theta(\log n), où n est la grandeur du graphe, peu importe le délai entre les temps de départ des agents. En fait la borne inférieure est vrai déjà pour la classe des anneaux.
Titre : Election du chef dans les réseaux arbitraires
Auteurs : Emanuele Fusco, Andrzej Pelc
Résumé:
Nous étudions la grandeur minimale de la mémoire dont il faut équiper les noeuds d'un réseau pour résoudre le problème d'élection du chef de manière déterministe. Les noeuds sont anonymes, mais les ports ont des étiquettages arbitraires. Les noeuds sont modélisés par des automates identiques qui communiquent en échangeants des messages et nous demandons quelle est la mémoire minimale d'un tel automate qui permet de faire l'élection du chef. Nous montrons que la mémoire logarithmique est optimale pour l'élection du chef dans la classe des graphes connexes quelconques. Ce résultat est contrasté avec celui pour la classe des arbres: nous montrons que l'élection du chef peut être faite dans la classe des arbres de degré maximal Delta en utilisant seulement O(log log Delta) bits de mémoire. Nous montrons aussi qu'aucun automate ne peut résoudre le problème de l'élection du chef pour tous les arbres.
Titre : Faisabilité et complexité de diffusion avec pannes aléatoires de transmission.
Auteurs : Andrzej Pelc, David Peleg
Résumé:
Nous considérons la diffusion tolérante aux pannes dans un modèle des pannes aléatoires. Dans chaque ronde de transmission, le transmetteur de chaque noeud peut tomber en panne avec probabilité constante p<1 et les pannes sont indépendantes. Nous étudions aussi bien les pannes d'omission que les pannes byzantines. Notre but est d'établir des conditions de faisabilité et d'estimer la complexité de la diffusion presque certaine, c'est-à-dire une diffusion correcte avec probabilité au moins 1-1/n pour les graphes avec n noeuds, pour n suffisamment grand.
Titre : Rendez-vous asynchrone déterministe dans les graphes.
Auteurs : Gianluca De Marco, Luisa Gargano, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Ugo Vaccaro
Résumé:
Deux agents mobiles (robots), munis d'étiquettes distinctes et situés dans deux noeuds d'un graphe anonyme à topologie inconnue, doivent se rencontrer dans un noeud. Nous considérons la version asynchrone de ce problème de rendez-vous, longtemps étudié dans la littérature, et nous construisons des algorithmes rapides pour le résoudre.
Titre : Le réveil des réseaux radio ad hoc anonymes
Auteur : Andrzej Pelc
Résumé:
Nous considérons la tâche de réveiller un réseau radio ad hoc anonyme par une source unique, en utilisant un algorithme déterministe. Au début, seulement la source est réveillée et doit réveiller les autres noeuds en diffusant des messages à travers le réseau. Les noeuds ne connaissent pas la topologie du réseau et n'ont pas d'étiquettes distinctes. Dans de tels réseaux, certains noeuds sont impossibles à rejoindre. Un noeud est accessible s'il peut être réveillé par un algorithme déterministe possiblement dépendant du réseau. Un algorithme de réveil déterministe pour des réseaux radio ad hoc est dit universel s'il réveille tous les noeuds accessibles. Pour la communication synchrone, nous construisons un tel algorithme et pour la communication asynchrone, nous prouvons qu'aucun algorithme universel ne peut exister.
Titre: Diffusion déterministe centralisée dans les réseaux radio
Auteurs: D. Kowalski, A. Pelc
Résumé:
Nous considérons le problème de diffusion déterministe centralisée dans les réseaux radio. Le but est de construire un algorithme polynomial qui produit un schéma rapide de diffusion pour un réseau radio modélisé par un graphe G donné. Le problème de trouver un schéma optimal de diffusion pour un graphe donné est NP-difficile, donc nous pouvons espérer seulement un bon algorithme d'approximation. Nous présentons un algorithme déterministe polynomial qui produit un schéma de diffusion travaillant en temps O(D log n + log 2 n), pour chaque graphe avec n noeuds et diamètre D.
Titre: Complexité de recherche d'un trou noir
Auteurs: J. Czyzowicz, D. Kowalski, E. Markou, A. Pelc
Résumé:
Un trou noir est un processus stationaire endommageant qui réside dans un noeud du réseau et détruit tous les agents mobiles visitant le noeud sans laisser aucune trace. Nous considérons la tâche de localiser un trou noir dans un réseau (partiellement) synchrone, en supposant une borne supérieure sur le temps de traverser un lien par un agent. Le nombre minimal d'agents capables d'identifier un trou noir est deux. Pour un graphe donné et pour un noeud donné de départ nous voulons trouver le schéma le plus rapide de recherche d'un trou noir dans un scénario général où un certain sous-ensemble de noeuds est sure et le trou noir peut se trouver dans un des autres noeuds. Nous montrons que le problème de trouver le schéma le plus rapide de recherche d'un trou noir par deux agents est NP-difficile et nous présentons une 9.3-approximation pour ce problème.
Titre : Diffusion de messages dans les réseaux radio à topologie inconnue
Auteurs : Dariusz Kowalski, Andrzej Pelc
Résumé:
Nous considérons le problème de diffusion répartie dans des réseaux radio dont les noeuds n'ont aucune connaissance de la topologie du réseau. Pour la diffusion aléatoire, nous proposons un algorithme qui travaille en temps espéré O (D log(n/D) + log 2 n) dans un réseau radio avec n noeuds et diamètre D. Ce temps est optimal, car il est égal à une borne inférieure connue pour ce problème. Pour la diffusion déterministe, nous montrons une borne inférieure Omega (n log n/log (n/D)) sur le temps de la diffusion dans des réseaux radio avec n noeuds et diamètre D. Nous montrons aussi un algorithme qui travaille en temps O (n log n).
Titre : Rendez-vous déterministe en temps polynomial.
Auteurs : Dariusz Kowalski, Andrzej Pelc
Résumé:
Deux agents mobiles doivent se rencontrer dans un noeud d'un réseau modélisé par un graphe connexe. Nous étudions des algorithmes déterministes pour ce problème, en supposant que les agents ont des identificateurs différents et sont situés dans un graphe à topologie inconnue. Notre résultat principal est un algorithme déterministe pour le rendez-vous, travaillant en temps polynomial en n, t et log l, où n est le nombre de noeuds dans le graphe, l est le plus petit des deux identificateurs et t est la différence entre les temps de départ des agents.
Titre : Exploration des arbres défectueux par un agent mobile
Auteurs : Euripides Markou, Andrzej Pelc
Résumé:
Nous considérons le problème de l'exploration des réseaux à topologie d'arbre, dont certaines arêtes sont défectueuses. Un agent mobile, situé dans un noeud de départ et ne connaissant pas la localisation des pannes, doit explorer la composante connexe de ce noeud. Nous construisons un algorithme optimal pour ce problème dans le cas où} le réseau est une ligne et un algorithme qui est seulement 9/8 fois pire que l'optimal dans le cas d'un arbre quelconque.
Titre : Techniques et mécanismes de survivabilité des réseaux supportant des
applications distribuées complexes
Auteur: Ilham Benyahia
Résumé:
Les applications multimédias nécessitant des qualités de services et des garanties de performance au niveau des transmissions telles que la téléphonie sur IP et la vidéoconférence, prennent de l'ampleur et nécessitent des réseaux de plus en plus fiables. Dans ce projet de recherche, nous cherchons différentes techniques de survivabilité de ces réseaux afin de rendre leurs fautes et congestions transparentes et surtout sans impacts majeurs pour le déroulement de telles applications. À l'état actuel, nous concentrons nos travaux sur les mécanismes de reroutage dynamique face à des situations non prévisibles au niveau des réseaux. Notre approche est basée sur des stratégies que nous expérimentons par des simulations et qui permettent de chercher dynamiquement des circuits ou des routes sur lesquels les paquets destinés vers des parties du réseau atteintes par des fautes et congestions seront réacheminées, en optimisant les coûts et les délais de transmission. Nous identifions alors parmi les techniques définies celles qui offrent des solutions qui respectent au mieux les exigences des applications supportées par ces réseaux.
Titre : Approche MDA pour le développement de systèmes répartis
Auteur: Karim El Guemhioui
Résumé:
L'approche MDA (Model Driven Architecture) propose une nouvelle façon de développer des applications réparties d'envergure. On commence par définir un modèle indépendant de la plate-forme sous-jacente du système (appelé modèle PIM) qui décrit la logique d'affaires du système sans égard à des considérations technologiques particulières. Puis on transforme ce modèle en un ou plusieurs modèles spécifiques à des plates-formes particulières (les modèles résultants sont appelés PIM). Chaque modèle PIM décrit comment le modèle de base est implanté dans un environnement d'exécution particulier (tel que CORBA ou C# .NET). En définissant, une seule fois, les fonctionnalités et le comportement du système à partir desquels seront automatiquement dérivées les implantations spécifiques à chaque plate-forme ou technologie choisie, l'approche MDA vise à améliorer, de façon significative, le temps de développement des systèmes logiciels et à éviter que les investissements effectués soient perdus en raison d'une obsolescence rapide de la technologie utilisée. Cette nouvelle approche MDA n'est présentement définie que dans ses grandes lignes et ne précise pas comment le modèle PIM ou les modèles PSM peuvent être définis, ni comment la dérivation automatique des PSM à partir du PIM doit se faire. Nous comptons apporter des éléments de réponse à ces deux questions : (1) en proposant un cadre de travail pour la définition méthodique et systématique de modèles PIM et PSMs et (2) en définissant un ensemble de règles et techniques pour la génération automatique des PSM à partir d'un PIM.
Titre: Conception d'un service de licence transparent et évolutif pour CORBA
Auteurs: Aymeric Nys, Karim El Guemhioui
Résumé:
CORBA est un middleware qui permet la communication d'objets distribués pour former une application répartie. Pour faciliter la conception de ce type d'applications, de nombreux services de base sont offerts. Parmi ces services, le service de licence a deux objectifs. Le premier est classique : le service doit permettre le contrôle de l'utilisation d'une application en fonction de la licence qui a été négociée entre le client et son fournisseur. Le second est de permettre de mesurer l'utilisation d'une application. Un des avantages liés à la mesure de l'utilisation des applications, est d'obtenir une meilleure connaissance de l'utilisation d'un parc logiciel. En conséquence, des diminutions de coûts peuvent être effectuées en réalisant des achats de groupes de licences et en procédant à une meilleure allocation des licences aux groupes de travail. Nous proposons le design et l'implantation de ce service, avec comme objectifs principaux de conception la transparence (l'utilisateur ne doit pas avoir conscience que l'application utilisée fait appel à un service de ce genre) et une capacité d'évolution pour pouvoir intégrer de nouveaux types de licence non encore prévus.
Titre: Temps de la diffusion de messages dans les réseaux sans fil à topologie inconnue.
Auteurs: Dariusz Kowalski, Andrzej Pelc
Résumé:
Dans un article célèbre
R. Bar-Yehuda, O. Goldreich, and A. Itai, On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomisation, in Journal of computer and system sciences, 45, 1992, pp. 104--126,
les auteurs donnent la preuve d'une borne inférieure linéaire sur le temps de diffusion dans les réseaux radio dont les noeuds connaissent seulement leur propre identité et celles de leurs voisins. Cette preuve est faite en construisant une classe de graphes de diamètre 3 avec la propriété que chaque algorithme de diffusion exige un temps linéaire pour certains graphes de cette classe. À cause d'une erreur subtile de l'argument, ce résultat s'avère incorrect. Nous construisons un algorithme qui travaille en temps logarithmique pour chaque graphe de cette classe. En plus, nous montrons comment faire la diffusion en temps sous-linéaire pour tous les graphes à n noeuds de profondeur o(\log \log n). D'autre part nous construisons une classe de graphes de diamètre 4, telle que chaque algorithme de diffusion exige un temps Omega (sqrt [4] {n}) pour un certain graphe de cette classe.
Titre: Diffusion déterministe plus rapide dans les réseaux radio ad hoc.
Auteurs: Dariusz Kowalski, Andrzej Pelc
Résumé:
Nous considérons des réseaux radio ad hoc modélisés par des graphes orientés. Chaque noeud connaît seulement sa propre identité et une borne linéaire sur la grandeur du réseau, mais ne connaît pas la topologie du réseau ni même son propre voisinage. L'algorithme de diffusion le plus rapide connu jusqu'ici, travaillant pour des réseaux radio ad hoc arbitraires, avait le temps de fonctionnement O(n log 2 n). Notre résultat principal est un algorithme de diffusion travaillant en temps O(n log n log D) pour les réseaux arbitraires de n noeuds et de profondeur D.
Titre: Exploration des arbres par des robots avec petite mémoire
Auteurs: K. Diks, P. Fraigniaud, E. Kranakis, A. Pelc
Résumé:
Un robot avec mémoire de k bits doit explorer un réseau à topologie d'arbre dont les noeuds n'ont pas d'étiquettes et les portes sont étiquetées localement dans chaque noeud. Le robot n'a pas de connaissance à priori de la topologie de l'arbre ni de sa grandeur et son but est de traverser tous les liens. Alors que O(log Delta) bits de mémoire suffisent pour explorer chaque arbre de degré maximal Delta si l'arrêt n'est pas exigé, nous montrons qu'une mémoire bornée n'est pas suffisante pour explorer avec arrêt tous les arbres de degré borné. Pour la tâche plus exigeante, où il faut s'arrêter au point du départ après l'exploration, nous montrons la borne inférieure Omega(log n) sur la grandeur nécessaire de la mémoire et nous montrons un algorithme pour compléter cette tâche avec O(log 2 n) bits de mémoire, pour tous les arbres avec n noeuds.
Titre: Exploration optimale des réseaux sans disponibilité de bonnes cartes.
Auteurs: A. Dessmark, A. Pelc
Résumé:
Un robot doit visiter tous les noeuds et traverser toutes les arêtes d'un graphe connexe inconnu, en utilisant aussi peu de traversées d'arêtes que possible. La qualité d'un algorithme d'exploration est mesurée en comparant son coût (nombre de traversées d'arêtes) au coût de l'algorithme optimal qui a la pleine connaissance du graphe. La proportion entre ses coûts maximisée par rapport à tous les points du départ et tous les graphes d'une classe, s'appelle la pénalité de l'algorithme pour cette classe. Nous considérons trois scénarios, fournissant au robot diverses quantités d'information concernant le réseau. Pour chacun d'eux, nous proposons des algorithmes optimaux d'exploration (avec pénalité minimale) et nous établissons des bornes inférieures qui prouvent l'optimalité de ces algorithmes.
Titre: Election du chef dans les anneaux avec étiquettes répétitives.
Auteurs: S. Dobrev, A. Pelc
Résumé:
Nous considérons le problème de l'élection du chef dans un anneau dont les noeuds ont des étiquettes qui peuvent se répéter. Chaque noeud connaît à priori sa propre étiquette et deux entiers m et M qui sont, respectivement, la borne inférieure et supérieure sur la grandeur inconnue de l'anneau. Le but est de décider si l'élection du chef est possible et de l'exécuter, le cas échéant. Dans la version synchrone du problème, nous présentons un algorithme qui utilise O(n log n) messages et travaille en temps O(M). En plus, notre algorithme utilise O(n) messages si tous les identificateurs sont distincts. Dans la version asynchrone, nous montrons une borne inférieure Omega (nM) sur le nombre de messages nécessaire et nous présentons un algorithme qui utilise O(nM) messages.
Titre: La balance entre le niveau de connaissance et le temps
de communication dans les réseaux radio géométriques.
Auteurs: A. Dessmark, A. Pelc
Résumé:
Nous considérons le problème de diffusion déterministe dans les réseaux radio géométriques (RRG) dont les noeuds connaissent seulement une partie limitée du réseau. Les noeuds d'un RRG sont situés dans un plan et chacun d'eux est équipé d'un transmetteur de rayon r. Un signal provenant de ce noeud peut atteindre tous les noeuds à distance au plus r de lui, mais si un noeud est situé à l'intérieur du rayon de transmission de deux noeuds qui transmettent simultanément, il ne peut recevoir aucun message. Chaque noeud connaît la partie du réseau à l'intérieur du rayon de connaissance s, c'est-à-dire il connaît les positions, les rayons de transmission et les étiquettes de tous les noeuds à distance au plus s.
Le but de ce projet est l'étude de la balance entre le rayon de connaissance s et le temps de diffusion déterministe dans un RRG avec n noeuds et eccentricité D de la source.
Titre: Spécification des comportements incertains des environnements
des applications distribuées complexes.
Auteur: Ilham Benyahia
Résumé:
L'une des difficultés reliées au bon fonctionnement des applications complexes distribuées est dûe au fait que ces applications intéragissent avec des environnements dont le comportement demeure mal connu et incertain. Plusieurs travaux de recherche reliés à ces applications ont cherché à modéliser les comportements de leurs environnements mais en considérant plus leurs spécifications formelles et validations de ces spécifications. Nos travaux dans ce contexte considèrent le critère incertain et non déterministe de ces comportements. Notre objectif est de s'approcher de plus en plus à des modèles à comportements réalistes. Nous définissons alors des méthodologies de spécification et de modélisation en considérant les approches évolutives afin de réduire au maximum les aspects inconnus de ces comportements.
Titre: Conception d'une architecture adaptative pour les applications complexes distribuées.
Auteur: Ilham Benyahia
Résumé:
L'ingénierie des applications distribuées complexes demeure l'une des tâches les plus difficiles à réaliser au niveau du développement des logiciels actuels. Cette difficulté est principalement reliée à l'aspect dynamique des composantes. Ces applications doivent s'adapter à de nouvelles situations souvent non prévues tout en continuant à garantir des contraintes de temps et de performance. Nous concentrons nos travaux de recherche sur l'étude de nouvelles méthodes de développement de ces applications en considérant essentiellement la conception de leurs architectures. Nos travaux sont particulièrement illustrés par des applications dans le domaine des transports et des télécommunications. Un projet en collaboration avec le Prof. Jean-Yves Potvin au CRT (Centre de Recherches sur les Transports) est en cours. Nous étudions dans ce projet l'impact des résultats de nos travaux sur des problèmes dans le domaine des transports.
Titre: Conception de systèmes distribués orientés-objet.
Auteur: Karim El Guemhioui
Résumé:
Nous considérons la tâche d'attribuer des entités de conception orientés-objet aux ressources informatiques réparties. Nous adoptons une approche quantitative. Le concept de couplage est examiné et une classification est proposée. Un cadre de conception est développé qui implante les concepts et l'approche quantitative proposée.