Ana səhifə

Rapport d’activité n°2 (18 mois) A. Identification


Yüklə 69.5 Kb.
tarix24.06.2016
ölçüsü69.5 Kb.

Projet ANR-05-SSIA- 0016-01



Rapport d’activité n°2 (18 mois)

A. Identification

Programme – année

ARA – SSIA - 2005

Projet (acronyme)

SOGEA

Nom du coordonnateur du projet et affiliation (société/organisme - laboratoire ou entité de rattachement)

Olivier BOURNEZ (INRIA, LORIA)




Référence convention ou décision

ANR-05-SSIA-0016-01

Projet :

date de début – date de fin



1ier Décembre 2005 au 1ier Décembre 2008.

Période faisant l’objet du rapport d’activité (date début – date fin)

30 Novembre 2006 au 20 Juillet 2007

Rédacteur de ce rapport : nom

BOURNEZ Olivier

téléphone

03 54 95 84 18

adresse électronique

bournez@loria.fr

Date du rapport

20 Juillet 2007

B. Rappel des tâches allouées par partenaire pour l’ensemble du projet (partir du planning généralement fourni dans le projet. Ce document est à remplir par le coordonnateur du projet à partir des informations fournies par chacun des partenaires)

Le document scientifique soumis ne promettait pas formellement de délivrables, mais faisait une liste d’un certain nombre de tâches à effectuer.

Nous reprenons ici les informations de la partie scientifique du projet:

Dans la période concernant ce rapport (1.5ière année), il avait été promis de contribuer aux tâches 1.1, 1.2, 1.3, 1.4, 1.5, 1.6. 2.1, 2.2, 2.4., 2.5. Seules les taches 1.1, 1.2, 1.3, 1.4, 1.5, 1.6 devaient êtres terminées à 18 mois.

Intitulés (partenaires entre parenthèses).


  1. Tache 1.1: « Notions de stabilité » (LORIA, LRI, PRISM)

  2. Tache 1.2: « Modèle du routage inter-domaine » (LORIA, PRISM)

  3. Tache 1.3: « Competitive Self-Stabilization » (LRI, LORIA)

  4. Tache 1.4: « Aspects Dynamiques » (LORIA, PRISM)

  5. Tache 1.5: « Techniques de preuves associées » (LORIA, PRISM)

  6. Tache 1.6: « Autostabilisation résistante aux comportements maléfiques » (LRI)

  7. Tache 2.1 : « Algorithmes distribués pour le routage interdomaine avec aspects économiques». (LRI, LORIA, PRISM)

  8. Tache 2.2 : « Algorithmes séquentiels pour réseaux de capteurs » (LORIA, LRI)

  9. Tache 2.4 : « Algorithmes distribués malicieux » (LRI, PRISM)

  10. Tache 2.5 : « Algorithmes distribués d’autostabilisation compétitive » (LORIA, LRI, PRISM)

Coordinateurs: Olivier Bournez pour le LORIA, Dominique Barth pour le PRISM, Sylvie Delaët pour le LRI.

Etat d'avancement: le calendrier est respecté à ce jour (voir plus bas).




Eléments qualitatifs
C. Description des travaux effectués pour la période concernée et conformité de l’avancement aux prévisions (15 à 50 lignes maximum suivant le nombre de partenaires)
Les travaux suivant ont été effectués. Les numéros entre parenthèses désignent les tâches en rapport. Les numéros entre accolades désignent des références aux publications mentionnées dans la section F.
Nous avons complété un modèle du routage interdomaine, en présence de partenaires économiques, par la prise en compte de différents aspects (1.2), [6,14,15,16]. La participation d’un partenaire au projet RNRT ACTRICE ayant pour but l’introduction de concepts économique dans la gestion de la qualité de service dans un réseau interdomaine a permis de dégager au sein de SOGEA de proposer un modèle algorithmique et économique de réseau (1.2), modèle validé par les partenaires industriels d’ACTRICE. En particulier, la politique de gestion des prix de ressources réseaux envisagée mêlent des stratégies de joueurs fictifs et techniques d’apprentissage réparti.

Nous avons formalisé certaines notions de politiques de stratégies et les propriétés attendues sur le modèle global (1.1,1.2). Il a été prouvé que le modèle n'admet pas d'équilibre de Nash pur (1.2, 1.1). Cette preuve permet d'extraire un sous-système simple, qui constitue un cas d'étude, sur lequel il est possible de prouver la convergence dans certains cas (1.4,1.5). Enfin, quelques politiques ont été intégrées et simulées au sein d’un simulateur de réseau interdomaine développé par une doctorante participant au projet (1.4), [6,14,15,16].


Nous avons étudié les différents modèles du dynamisme de la littérature en théorie des jeux, en particulier les modèles de la théorie évolutionnaire des jeux (1.4). Nous avons présenté leur utilisation pour la réalisation de calculs distribués dans [3] et [7]. Les modèles de la théorie évolutionnaire des jeux sont des modèles particuliers de dynamiques à temps continu. Nous avons présenté un survol des propriétés calculatoires des systèmes à temps continu dans [1]. La théorie évolutionnaire des jeux propose des notions simples de stabilité, comme la notion d’équilibre évolutionnairement stable (1.1). Nous nous sommes intéressés dans ce contexte à la théorie de l’apprentissage des équilibres (1.1,1.4,1.5). En particulier, nous investiguons l’utilisation de cette théorie pour la conception d’algorithmes d’apprentissage convergeant dans le cas des routages de Wardrop (1.4,1.5, 2.3), en lien avec le travail d’Octave Boussaton, recruté par le projet.
L’étude des liens entre certains jeux et des modèles de calculs distribués, nous a mené à nous intéresser aux modèles des protocoles de populations. Ce modèle de réseaux de capteurs (2.3) introduit par Angluin et Al. s’avère un cadre naturel pour comprendre les modèles et les propriétés étudiées par différents partenaires du projet, en permettant de discuter les aspects dynamiques, les problèmes de complexité, et les aspects autostabilisants dans un cadre unique. Nous avons proposé une extension continue, proche des modèles de la théorie évolutionnaire des jeux (1.4,1.5,2.3). Nous avons montré que cette extension permettait le calcul distribué de quantités algébriques irrationnelles [13]. Nous continuons à nous intéresser à l’étude de la convergence de tels protocoles, en utilisant des arguments proches de ceux qui sont utilisés en théorie de l’apprentissage des équilibres de Nash (1.5,2.3) : voir aussi [14]. Un des intérêts de ce modèle est qu’il permet naturellement de modéliser la présence d’une proportion d’agents maléfiques (2.4).
D'autre part, nous nous sommes intéressés à l'autostabilisation en présence de partenaires économiques. Nous avons défini le problème de l'autostabilisation égoïste (1.3), et étudié un premier exemple de protocole dans ce cadre (1.3). Ce protocole réalise la construction d'un arbre couvrant, comme les protocoles utilisés pour le routage interdomaine, mais en présence de partenaires aux intérêts distincts (1.3, 2.1), [8]. Nous avons approfondi ce cadre par d’autres études de cas, autour de problèmes de construction d’arbres de plus courts chemins dans [17] (2.2, 2.3). Nous avons ainsi montré que s’il y avait deux types de joueurs, un équilibre de Nash pur existe toujours, et est calculable en temps polynomial. Nous avons montré que pour trois types de joueurs, le problème de l’existence d’un équilibre de Nash pur est NP-complet [17]. Lorsqu’un équilibre de Nash pur existe, une solution stabilisante existe pour le calculer [8,17]. Nous poursuivons actuellement les investigations autour des fondements théoriques de l’autostabilisation égoïstes. En particulier, via le travail de Mariusz Rokicki, post-doc recruté en mars par le projet.
Autour de la tâche spécifique (1.6), nous nous sommes intéressés à l'autostabilisation en présence d'acteurs byzantins, en introduisant le concept de stabilisation forte. Nous avons présenté des protocoles fortement stabilisant dans ce sens (1.6), [11]. Un état de l’art du domaine a été réalisé dans [2]. Nous avons aussi exploré la détection de fautes transcientes dans les systèmes distribués (1.6), [5]. Nous avons étudié le problème du consensus en présence de processeurs non-fiables : il est bien connu que dans un environnement classique asynchrone, où les entités sont connues, le problème en présence de la défaillance même d’un seul processus. Le problème s’avère encore plus difficile dans les systèmes stabilisants, puisque l’ensemble et l’identité des participants ne sont pas connus. Nous avons établi des conditions nécessaires et suffisantes pour que le problème soit résoluble dans [10].
Les modèles du dynamisme en théorie des jeux basés sur les jeux répétés mènent à devoir discuter les familles de stratégies, qui peuvent se coder par des mots et des arbres (1.4). La recherche de solutions approchées au problème de la comparaison de stratégies nous a mené à étudié une notion de comparaison approchée pour les stratégies définies par automates, en prouvant que la distance d’édition avec déplacements était testable au sens de la théorie du test de propriétés (property testing) (1.4, 1.5), [9]. Nous nous sommes aussi intéressés au problème de l’échange de données. Dans ce problème, une source envoie de l’information à une destination en respectant des schémas. Le problème peut se voir comme un jeu entre la source et la destination qui doivent tomber d’accord sur un message. Puisque les problèmes de décision approchés sont intractables (par ex : la vérification de type est PSPACE-complet), nous avons proposé des solutions polynomiales dans un cadre approché, inspiré par le test de propriétés. (1.5), [12].
En lien avec les aspects de complexité (3.1) et (1.5), nous investiguons l’utilisation du principe de la coinductiosn pour la preuve de propriétés dans le contexte des jeux. D. Kozen a proposé une réinterprétation de ce principe qui permet de prouver qu’un point fixe d’une équation vérifie une propriété en montrant que la propriété est vérifiée par l’équation. Cette idée s’applique à la preuve de propriétés combinatoires, ou de propriétés de processus stochastiques. Nous cherchons à comprendre si cela peut s’appliquer à la preuve de propriétés sur les propriétés dynamiques d’un jeu (1.5, 3.1).

D. Résultats obtenus pour la période concernée, dégager notamment les faits marquants (15 à 50 lignes maximum) Décrire les résultats obtenus et préciser éventuellement les livrables déjà réalisés en interne au projet.

Nous estimons que les faits marquants sont les publications obtenues.


Factuellement:
Concernant les tâches promises à cette date  (1.1, 1.2, 1.6) :
Comme nous avons tenté de le montrer plus haut, le travail sur ces tâches est dans les temps. Nous pouvons citer ainsi par exemple les publications [6,14,15,16] pour 1.1 et 1.2, et [11] pour 1.6.
Pour les autres tâches, en cours (2.1, 2.2, 2.4, 2.5) :
Comme nous avons tenté de le montrer plus haut, le travail est bien amorcé, avec pour plusieurs d’entre elles, déjà des publications significatives.


E. Difficultés rencontrées et solutions de remplacement envisagées (15 à 50 lignes maximum) ex : impasse technique, abandon d’un partenaire ou d’un sous traitant, maîtrise des délais, maîtrise des budgets. Faut-il revoir le contenu du projet ? Faut-il revoir le calendrier du projet ?

Globalement le travail autour des thématiques du projet progresse.


Une des difficultés est que ce projet vise à réunir des personnes de cultures différentes (exemple: complexité, algorithmique autostabilisante, algorithmique pour les réseaux), intéressées par la thématique globale du projet. Après une phase importante de discussion lors de la première année, la vision de chacun est maintenant relativement claire et bien comprise par les participants avec une répartition des tâches bien établie, même si la communication entre participants de cultures différentes, parfois avec des attentes différentes, n’est pas toujours facile.
D’autre part, comme cela avait été mentionné par les referees, le projet initial était très ambitieux. Bien que nous contribuions à des travaux en rapport avec les tâches annoncées, le découpage précis en tâches du projet initial s’avère parfois assez arbitraire. Plusieurs travaux sont difficiles à classer comme clairement relevant d’une tâche plutôt qu’une autre.
D’autre part, il s’avère que certaines des tâches, comme par exemple 1.4, 1.5 sont clairement au cœur de la problématique de plusieurs tâches présentées comme ultérieures dans le document initial. C’est pourquoi il nous semble fondamental de ne pas considérer comme terminées les tâches en rapport avec les aspects les plus fondamentaux (exemple 1.4, 1.5).


F. Livrables externes réalisés (15 à 50 lignes maximum)

Pour les articles et communications écrites, préciser s’il s’agit d’articles dans des revues à comité de lecture / d’ouvrages ou chapitres d’ouvrage / d’articles dans d’autres revues / de communications dans des colloques ou des congrès / de dépôt de brevet… Référencer selon les normes habituelles. Mentionner également s’ils peuvent ou non faire l’objet de communications externes par l’ANR et son unité support


Indiquer, Le cas échéant, les thèses démarrées, en cours et/ou soutenues en relation directe avec le projet :

Préciser le titre, date de soutenance (prévue ou réelle), soutien financier, devenir des étudiants pour les thèses soutenues.
Chapitres de livres


  1. Olivier Bournez and Manuel Campagnolo. A survey on Continuous Time Computations. Chapter of the book « New Computational Paradigms », Springer. To appear.

  2. Sébastien Tixeuil. Fault-tolerant distributed algorithms for scalable systems. Chapter of the book « Wireless Ad Hoc and Sensor Networks ». ISTE, 2007. To appear.



Habilitations à diriger les recherches :


  1. Olivier Bournez. Modèles continus. Calculs. Algorithmique Distribuée. 7 Décembre 2006.

  2. Sébastien Tixeuil. Vers l’autostabilisation des systèmes à grande échelle. Mai 2006.



Revues



  1. Joffroy Beauquier, Sylvie Delaët, Shlomi Dolev and Sébastien Tixeuil. Transient Fault Detectors. Distributed Computing. Springer 2007. A paraître.

Conférences d’audence internationale avec comité de sélection.


  1. Dominique Barth, Johanne Cohen, Loubna Echabbi and Chahinez Hamlaoui. Transit prices negotiation : Combined repeated game and distributed algorithmic approach. NEtwork Control and OPtimisation (NETCOP’2007) , Lecture Notes in Computer Science, vol. 4465, pages 266-275, 2007.

  2. Olivier Bournez and Emmanuel Hainry. On the Computational Properties of Some Systems. Machines Computations and Universality MCU’2007, Orléans, September 2007. Lecture Notes in Computer Science, page to appear

  3. Anurag Dasgupta, Sukumar Ghosh, and Sébastien Tixeuil. Selfish stabilization. In Ajoy K. Datta and Maria Gradinariu, editors, Eighth International Symposium on Stabilization, Safety, and Security on Distributed Systems (SSS 2006), Lecture Notes in Computer Science, volume 4280, page 231-243, Dallas, Texas, November 2006. Springer Verlag.

  4. Eldar Fischer, Frédéric Magniez, and Michel de Rougemont. « Approximate Satisfiability and Equivalence ». Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science, LICS’2006. IEEE Computer Society, pages 421-430

  5. Fabiola Greve and Sébastien Tixeuil. Knowledge Connectivity vs. Synchrony Requirements for Fault-Tolerant Agreement in Unknown Networks. IEEE International Conference on Dependable Systems and networks (DSN 2007). IEEE 2007.

  6. Toshimitsu Masuzawa and Sébastien Tixeuil. Bounding the impact of unbounded attacks in stabilization. In Ajoy K. Datta and Maria Gradinariu, editors, Eighth International Symposium on Stabilization, Safety, and Security on Distributed Systems (SSS 2006), Lecture Notes in Computer Science, volume 4280, page 440-453, Dallas, Texas, November 2006. Springer Verlag.

  7. Michel de Rougemont and Adrien Vielleribière. Approximate Data Exchange, 11th International Conference on Database Theory (ICDT’2007). Barcelona, Spain, January 2007. Lecture Notes in Computer Science, volume 4353, page 44-58.


Rapports de stages :


  1. Rapport de stage ENS Paris 1ière année. Protocoles de Population Continus. Xavier Koegler. Septembre 2006.


Rapports de recherche soumis


  1. Dominique Barth, Loubna Echabbi, Chahinez Hamlaoui . Transit prices negotiation :decentralized learning of optimal strategies with incomplete information. A soumettre.

  2. Dominique Barth and Chahinez Hamlaoui. Impact of the selfishness of pricing strategies on the QoS provisioning in interdomain networks submitted à Conext 2007.

  3. Dominique Barth and Chahinez Hamlaoui. Modèle deGestion de laQoS dans les réseaux interdomaine basé sur les jeux répété. Soumis à Gres 2007.

  4. Johanne Cohen, Anurag Dasgupta, Sukumar Ghosh and Sébastien Tixeuil. An exercice in Selfish Stabilization. Soumis à une revue.

(toutes ces communications écrites peuvent faire l’objet de communications externes par l’ANR et son unité support. Elles sont pour l’essentiel disponibles sur le site du projet sur http://sogea.loria.fr/publications.html)

G. Autres commentaires


Eléments quantitatifs



H. Liste des réunions/séminaires/colloques organisés durant la période et des missions à l’étranger

(préciser la date, le lieu, l’objet, le nombre des participants)


Les réunions en présence de tous les partenaires lors de la première année ayant aboutis à un partage clair des taches, le rythme de telles réunions s’est espacé lors des 6 derniers mois, en se focalisant sur des réunions de présentation d’avancement des travaux respectifs + discussions. Des missions entre partenaires sur des aspects précis des taches, non-reprises sur ce document, ont toutefois lieu régulièrement.
Le détail exact des journées, lieus, exposants peut se trouver sur la page http://sogea.loria.fr. Chaque réunion correspond à une journée. La plupart des exposés sont en ligne. Certains sont en accès privé, mais accessibles avec le login: "sogea" et le mot de passe "game".


  1. Réunion le 6 Décembre 2005, au LRI: exposé d'Olivier Bournez + Discussions.

  2. Réunion le 23 Janvier 2006, au LRI: exposé de Johanne Cohen + Discussions.

  3. Réunion le 2 Février 2006, au LRI: exposés de Michel de Rougemont et exposé de Loubna Echabbi + Discussions

  4. Journée d'exposés invités (de membres francais extérieurs au projet) le 28 Février 2006, au LORIA: Exposés de a- T. Pénard, b- M. Bouhtou, c- Y. Hayel, d- Y. Gabuthi, e- P. Maillé

  5. Réunion le 23 Mars 2006, au PRISM: exposés de Chahinez Hamlaoui, exposé d'Olivier Bournez, exposé de Sébastien Tixeuil, exposé de Sébastien Hémon

  6. Journée d'exposés invités (de membres étrangers, extérieurs au projet) le 16 Mai 2002, à l'Université Paris II: exposés de a- Daniel Lehmann, b- Berthold Voecking, c- Marios Mavronicolas, d- Roger Wattenhofer, e- Sukumar Ghosh

  7. Habilitation de Sébastien Tixeuil le 22 mai 2006

  8. Réunion le 2 Juin 2006, au LRI: exposé de Dominique Barth + Discussions

  9. Réunion le 11 Septembre 2006, au LRI: exposés de Sébastien Tixeuil et exposé de Xavier Koegler + Discussions.

  10. Réunion le 16 Octobre 2006, au LRI: exposés de Sébastien Tixeuil, exposé d'Octave Boussaton, exposé de Daniel Villa Monteiro + Discussions.

  11. Réunion lors des journées PARISTIC, au LORIA: Discussions.

  12. Réunion le 16 Février 2007, au LRI : exposés de Michel de Rougemont, exposé de Sébastien Hémon, exposé de Fanny Pascual + Discussions.

  13. Réunion le 20 mars 2007, au LORIA : exposés invités de Jean-Pierre Hubaux et Tansu Alpcan. Cours dans le cadre de l’Ecole Jeunes Chercheurs Informatique Mathématique sur théorie des jeux et applications au réseaux + Discussions.

  14. Réunion le 23 mai 2007, au LORIA: exposé de Chahinez Hamlaoui, exposé de Julien Clément, exposé de Olivier Bournez, exposé de Octave Boussaton, exposé de Sébastien Tixeuil + Discussions.



  1. Par rubrique et par partenaire, établir la consommation des dépenses financées par l’ANR, depuis le démarrage du projet.


Partenaire

Fonct. (Keuros)

Equipement (préciser nature)

Equip. (Keuros)

LRI (Orsay)

31559


Ordinateurs

11711

LORIA (Nancy)

17819

Ordinateurs

7964

PRISM (Versailles)

10622




0

Total projet

60000




19675



J. Le cas échéant, préciser les travaux réalisés par les partenaires étrangers associés au projet sans aide de l’ANR
Sans objet

K. Liste des personnels recrutés en CDD par des établissements publics dans le cadre du projet sur l’aide allouée par l’ANR


Nom

Prénom

Qualifications

Date de recrutement

Durée du contrat (en mois)

Boussaton

Octave

DEA Informatique, actuellement ingénieur expert dans le projet

1/10/2006

36

Rokicki

Mariusz

Docteur, actuellement postdoc dans le projet

18/3/2007

12 mois

Indiquer leur devenir postérieur à leur participation au projet : intégration comme chercheur, enseignant-chercheur, ingénieur, emploi dans le privé, chômeur, etc.…
À ce jour, tous les personnels recrutés sont encore en contrat dans le projet.

L. Le cas échéant, indiquer les différents types d’aides complémentaires obtenues grâce à ce projet.

(Il peut s’agir de ressources financières, ressources humaines, allocations de recherche,…)



Sans objet



M. Le cas échéant, modalités d’utilisation du complément de financement « pôles de compétitivité » (15 lignes maximum)

Rappel : ceci ne s’applique pas aux entreprises, mais seulement aux laboratoires publics et autres structures non soumises à l’encadrement communautaire des aides d’Etat à la R&D. Le complément de financement est destiné à couvrir des frais supplémentaires liés à la participation aux activités du pôle : ingénierie de projets partenariaux publics-privés, recherche de partenaires ; valorisation de la recherche ; relations inter-pôles et internationales…
Sans objet


N. CADRE RESERVE AU COORDONNATEUR DU PROJET (15 à 50 lignes maximum)

Commentaire général sur l’état d’avancement du projet, les interactions entre les différents partenaires, les efforts particuliers en matière d’interdisciplinarité, l’ouverture internationale, etc.

Le document scientifique soumis était, (comme cela a été observé par les referees) très ambitieux, en s'intéressant à de multiples aspects autour de la théorie algorithmique des jeux et ses applications à des problèmes de routage, ou de réseaux de capteurs.


Une des difficultés est que ce projet vise à réunir des personnes de cultures différentes (exemple: complexité, algorithmique autostabilisante, algorithmique pour les réseaux), intéressées par la thématique globale du projet.
Les points forts de la réussite de ce projet à cette date sont :

  • Des publications internationales de qualité,

  • De réelles nouvelles collaborations entre certains membres du projet,

  • Un rayonnement international par exemple par organisation de journées d’exposés invités et de cours avec des orateurs de renom, ou de cours aux jeunes chercheurs.

  • Un réel potentiel pour des travaux de premier plan scientifique pour la suite du projet.

Le coordinateur est optimiste sur la suite de ce projet à cette date.





CADRE RESERVE A l’USAR

Nom du coordinateur scientifique de l’USAR :



Date :




Glossaire


Livrable : tout composant matérialisant le résultat de la prestation de réalisation. Toute production émise par le titulaire au cours du projet : document, courrier revêtant un caractère officiel , module de code logiciel, dossiers de tests, application intégrée, objet, dispositif…
Livrable interne : réalisé au sein du programme et non communiqué à l'extérieur du programme.
Livrable externe : élément diffusé ou livré hors de la communauté du projet de recherche..
Faits marquants : élément non nécessairement quantifiable mais significatif pour le projet.

 Le canevas pour ce premier rapport dit « à 12 mois » sera également à utiliser pour les rapports semestriels suivants

page /


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©atelim.com 2016
rəhbərliyinə müraciət