Master 2018 2019
Stages de la spécialité SAR
Algorithmes de diffusion causale dans les systèmes répartis dynamique


Site : Trac-Algorithmes de diffusion causale dans les systèmes répartis dynamique
Lieu : Equipe DELYS LIP6
Encadrant : Luciana Arantes, Pierre Sens (Prenom.Nom@lip6.fr)
Dates :du 01/03/2019 au 31/08/2019
Rémunération :580 euros par mois

Cliquer ici pour vous authentifier


Description

La diffusion causale [1] est un élément essentiel dans les systèmes répartis. Elle est à la base de nombreux mécanismes pour maintenir la cohérence entre des copies répliquées [2], disséminer une information cohérente dans les réseaux sociaux [3] ou encore pour réaliser des systèmes de publications/abonnements [4]. Il s’agit alors de propager une information à un ensemble de nœuds tout en respectant les contraintes de causalité entre les informations.

La diffusion causale a été largement étudiée dans des systèmes répartis statiques [1]. Cependant, la dynamicité est une propriété clé des nouvelles infrastructures distribuées : dans l’internet des objets, les nœuds physiques peuvent arriver et partir à tout moment, être sujet à des fautes ou encore se déplacer.

Ce stage vise à étudier la diffusion causale dans le cadre de ces systèmes où la topologie est fortement dynamique et les ressources des nœuds limitées. La plupart des algorithmes existant repose sur des vecteurs d’horloges de Lamport de taille N [5] (N étant les nombre de processus du système) pour capturer les informations de causalité. Ces vecteurs, éventuellement compressés, sont transportés dans les messages. De tels implémentations sont coûteuses, ne passent pas à l’échelle et ne permettent pas de gérer la dynamicité. D’autres implémentations réduisent les informations transmises mais reposent sur l’hypothèses fortes de canaux de communications FIFO [6].

L’objectif de ce stage est de proposer et implémenter un nouvel algorithme de diffusion causal prenant en compte les caractéristiques d’un réseau de capteurs. Cet algorithme devra être ensuite déployé sur un ensemble de raspberry pi et testé dans l’environnement de simulation OMNet++.

Bibliographie

[1] Vassos Hadzilacos and Sam Toueg. A modular approach to fault-tolerant broadcasts and related problems. Technical report, Ithaca, NY, USA, 1994

[2] Manuel Bravo, Lu´ ıs Rodrigues, and Peter Van Roy. Saturn : A distributed metadata service for causal consistency. In Proceedings of the Twelfth European Conference on Computer Systems, EuroSys ’17, pages 111–126, New York, NY, USA, 2017. ACM.

[3] Dhruba Borthakur. Petabyte scale databases and storage systems at facebook. In Proceedings of the 2013ACM SIGMOD International Conference on Management of Data, SIGMOD ’13, pages 1267–1268, New York, NY, USA, 2013. ACM.

[4] João Paulo de Araujo, Luciana Arantes, Elias Procópio Duarte Jr., Luiz A. Rodrigues, Pierre Sens. VCube-PS : A causal broadcast topic-based publish/subscribe system. J. Parallel Distrib. Comput. 125 : 18-30 (2019)

[5] Friedemann Mattern. Virtual time and global states of distributed systems. Parallel and Distributed Algorithms.

[6] Brice Nédelec, Pascal Molli, Achour Mostéfaoui. Breaking the Scalability Barrier of Causal Broadcast for Large and Dynamic Systems. SRDS 2018 : 51-601(23):215–226, 1989