Séminaires AND et extérieurs

L'objectif principal des travaux est de minimiser le temps d'exécution des applications itératives asynchrones dans des environnements pair-à-pair. Il faut favoriser au maximum l'exécution en parallèle des tâches de l'application tout en essayant de faire que les tâches s'exécutent le plus possible dans le même temps. Ceci implique qu'il faut trouver des machines « similaires » ainsi que les liens les plus performants entre elles.

Dans le cas des applications itératives asynchrones, le nombre d'itérations n'est pas connu à l'avance et varie d'une exécution à une autre, car ces applications sont très dépendantes des conditions de la plate-forme d'exécution (charge des machines et du réseau) et de l'environnement logiciel (un thread de traitement qui ne rend pas la main au bon moment). Ainsi, par rapport à du « mapping » traditionnel, le modèle que nous utilisons est différent, bien que reposant sur des « TIG » (graphe de dépendances des tâches), pour tenir compte de l'asynchronisme -- et dans une autre mesure, la tolérance aux pannes pour la plate-forme JaceP2P.

Le but va donc être de trouver l'environnement le plus propice, en termes de machines et de réseau, à l'exécution des applications itératives asynchrones, en garantissant un temps d'exécution minimal.

Les informations manipulées par les ordinateurs peuvent être de grande taille mais sont in fine toujours finies. Les systèmes numériques et bio-inspirés travaillant sur ces domaines finis itèrent généralement sur un temps discret : les systèmes peuvent être observés à travers leurs configurations à chaque pas de temps discret. Ce type de systèmes à configurations discrètes et temps discret est appelé système dynamique discret.

Dans ce contexte, il est nécessaire de s'assurer que le système possède des propriétés élémentaires. Par exemple, un système qui calcule un résultat doit se stabiliser sur un point fixe en un temps fini. Cela est identifié à une convergence du système, contrairement à la divergence pour laquelle des cycles apparaissent.

Prouver que de tels systèmes convergent est une tâche longue, difficile et sujette à l'erreur en raison du nombre de cas, sous cas qui peuvent apparaître en fonction des stratégies et délais notamment. Dans ce travail, nous montrerons qu'il est possible d'obtenir automatiquement une preuve formelle de convergence/divergence de tels systèmes pour les itérations synchrones et asynchrones dont les délais sont bornés.

Les aspects théoriques et pratiques sont étudiés : d'une part nous avons prouvé que la démarche est correcte et complète, d'autre part la complexité de la démarche est calculée et quelques expérimentations montrent l'intérêt de l'approche. Un exemple jouet illustre la présentation.

Grâce à l'approche proposée, on dispose gratuitement d'une preuve correcte.

Cette thèse propose des modèles multi-agents réactifs fondés sur un cadre formel pour la vérification de propriétés et les valider par la simulation et l'expérimentation en considérant la navigation multi-véhicules comme domaine d'application. La navigation multi-véhicules soulève plusieurs problématiques : perception de l'environnement, communication inter-véhicule, évitement d'obstacle, … Dans ce contexte, nous avons abordé plus particulièrement les aspects suivants :

• Concernant la navigation multi-véhicules nous avons abordé deux problèmes spécifiques : la conduite en convoi ou platooning et la navigation autonome. En ce qui concerne la navigation autonome, nous avons mis l'accent sur l'évitement d'obstacles.
• Concernant l'approche proposée : nous adoptons les systèmes multi-agents réactifs, dont les interac- tions sont inspirée de la physique. Pour la conduite en convoi, nous proposons un modèle d'interaction basé sur la physique classique. En ce qui concerne l'évitement d'obstacles, nous adoptant un modèle inspiré de la physique statistique.
• Nous plaçons les systèmes multi-agents réactifs dans un cadre formel pour la vérification des pro- priétés, compte-tenu des contraintes de sécurité imposées par la classe d'applications cible. Pour faire face à la complexité des modèles, nous proposons une règle et une méthode de vérification compo- sitionnelle. Cela nous a permis de vérifier la satisfaction d'une propriété de sûreté essentielle : la non-collision entre véhicules lors de la conduite en convoi.
• Nous abordons également la question de la validation du système multi-agents par la simulation et l'expérimentation : nous avons contribué au développement d'un simulateur de la conduite en convoi et la navigation autonome. Le simulateur prend en compte les caractéristiques physiques des véhicules et est couplé à un outil de visualisation 3D. Nous avons aussi expérimenté nos modèles sur des véhicules tels que le Cycab et le GEM Car.

Les réseaux de capteurs autonomes sans fils permettent de mesurer et/ou de capturer des informations concernant l'environnement immédiat sur une large échelle. Ces réseaux de capteurs soulèvent un intérêt grandissant de la part des industriels ou d'organisations civiles où la surveillance et la reconnaissance de phénomène physique est une priorité. Ces applications ont des besoins spécifiques du fait de leur criticité. La prise en compte de cette criticité peut se faire à plusieurs niveaux et de plusieurs manières, souvent complémentaires: applicatif, organisation, routage, contrôle de congestion, accès au support, couche physique, matériel, système d'exploitation, middleware, architecture logicielle et orientée service, adaptation, modèles, … Dans cette présentation, nous présenterons les défis que réprésentent le déploiement d'applications critiques de surveillance, notamment ceux liés à la prise en compte de cette forte criticité.

Avec l'émergence de ressources de calcul massivement distribuées, telles les architectures de clusters distribués ou les grilles, la programmation parallèle est utilisée afin de bénéficier de telles architectures et exécuter des problèmes de grande taille. Il a été démontré que le modèle asynchrone, appelé AIAC, est une solution efficace pour l'exécution d'applications dans des milieux hétérogènes et volatils. Le placement intelligent des tâches des applications est essentiel en vue de réduire leur temps d'exécution. Les travaux présentés mettront en lumière un nouvel algorithme de placement appelé MAHEVE (pour Mapping Algorithm for HEterogenous and Volatile Environments), qui se veut efficace sur des architectures hétérogènes et volatiles. Ce nouvel algorithme intègre des mécanismes permettant de gérer les pannes de machines, afin de réaffecter au mieux les tâches étant placées sur celles-ci.

Les expériences que nous avons menées montrent des gains, sur le temps d'exécution d'une application typique du modèle AIAC, de l'ordre de 55%. Ces expériences ont été réalisées sur des architectures de clusters distribués, comportant plus de 400 coeurs de calcul, à l'aide de l'environnement JaceP2P-V2.

Wireless sensor networks are now in widespread use to monitor regions, detect events and acquire information. To reduce the amount of sending data, an aggregation approach can be applied along the path from sensors to the sink. However, usually the carried information contains confidential data. Therefore, an end-to-end secure aggregation approach is required to ensure a healthy data reception. End-to-end encryption schemes that support operations over cypher-text have been proved important for private party sensor network implementations. Unfortunately, nowadays these methods are very complex and not suitable for sensor nodes having limited resources. In this paper, we propose a secure end-to-end encrypted-data aggregation scheme. It is based on elliptic curve cryptography that exploits a smaller key size. Additionally, it allows the use of higher number of operations on cypher-texts and prevents the distinction between two identical texts from their cryptograms. These properties permit to our approach to achieve higher security levels than existing cryptosystems in sensor networks. Our experiments show that our proposed secure aggregation method significantly reduces computation and communication overhead and can be practically implemented in on-the-shelf sensor platforms. By using homomorphic encryption on elliptic curves, we thus have realized an efficient and secure data aggregation in sensor networks.