Ce projet de recherche doctorale est publié a été réalisé par Anne Fladenmuller

Description d'un projet de recherche doctoral

Algorithmes d’accord répartis dans les réseaux de capteurs

Mots clés : algorithmes d'accord répartis   réseaux de capteurs   économie d'énergie   réseaux dynamiques  

Résumé du projet de recherche (Langue 1)

Contexte

Cette thèse vise à étudier des algorithmes d’accord qui sont au cœur des applications réparties s’exécutant sur les réseaux dynamiques. On retrouve ces algorithmes dans la plupart des services permettant de répliquer et partager des données entre utilisateurs. Le plus fondamental des problèmes d’accord est celui du consensus [1,2]: il s’agit à terme que tous les utilisateurs du système décident une et une seule valeur parmi un ensemble de valeurs proposées. Le consensus permet de répliquer de manière cohérente de données. Il est ainsi massivement utilisé dans les systèmes de bases de données répartis.   Le plus célèbre des algorithmes de consensus est Paxos [3] proposé par Leslie Lamport (prix Turing 2014) et utilisé par Google pour maintenir la cohérence dans ses index répliqués.

La dynamicité et les contraintes énergétiques sont des propriétés clé de ces nouvelles infrastructures réparties : les périphériques physiques ont des ressources énergétiques limitées, peuvent arriver et partir à tout moment, être sujet à des fautes ou encore se déplacer. Cela pose des nouveaux défis pour les algorithmes répartis qui prennent peu en compte les aspects énergétiques et considèrent des topologies connues et statiques

Objectifs

L’objectif de cette thèse est d’adapter les algorithmes d’accord (dont le consensus) aux contraintes de ses réseaux en adaptant une approche « cross-layer » qui exploite les informations issues des couches réseau-liaison de données [4]. L’idée est de limiter au maximum les échanges de messages afin de préserver l’énergie. Le principal défi est de construire une algorithmique fiable à partir d’informations parcellaires, locales et éventuellement erronées produites par les couches basses.

Les objectifs de la thèse sont doubles :

·       D’un point de vue algorithmique : il s’agit de définir des algorithmes adaptés aux topologies dynamiques s’appuyant sur des modèles de graphe dynamique inspiré des TVG (Time Varying Graph) [5]

·       D’un point de vue expérimental, une des originalités de cette thèse est d’allier aux aspects théoriques des validations expérimentales. Les algorithmes proposés seront validés dans des environnements simulés tels que OMNet++ ainsi que sur des testbeds réels de réseaux de capteurs dans le cadre de la plateforme Scylex.


Informations complémentaires (Langue 1)

Références

[1] Dwork, C., Lynch, N.A., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288–323 (1988)

[2] Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)

[3] Leslie Lamport. 1998. The part-time parliament. ACM Trans. Comput. Syst. 16, 2 (May 1998), 133-169.

[4] Beshr Al Nahas, Simon Duquennoy, Olaf Landsiedel: Network-wide Consensus Utilizing the Capture Effect in Low-power Wireless Networks. SenSys 2017: 1:1-1:14

[5] Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. In: Adhoc-Now Conference. (2011) 346–359