On fait de la modélisation distribuée pour travailler à plusieurs sur un même modèle, ce modèle n'étant pas stocké de manière centralisé.
On veut pouvoir travailler en mode déconnecté.
On veut avoir les mises à jours tout en gardant une vue cohérente des données.
Les buts de cette modélisation distribuée asynchrone sont de construire un système de fichier ou une base de données cohérent à partir d'échanges ponctuels d'information entre les participants.
La centralisation pose les problèmes suivants :
Si le serveur central tombe en panne on ne peut plus rien faire.
L'accès au serveur doit être fiable.
Le serveur peut être surchargé.
Les données peuvent être censurées.
Parce que l'accès réseau n'est pas fiable.
Parce que la synchronisation induit des délais longs, il est difficile de travailler intéractivement.
La cohérence du modèle.
Les solutions classiques imposent que le modèle soit toujours cohérent.
Dans la réalité, si l'on travaille à plusieurs c'est que le modèle est complexe. Il y a donc peu de chances que des modifications contradictoires soient faites simultanément sur la même partie du modèle.
En cas de problème (rarissime) l'être humain le résoud.
C'est l'optique des systèmes de gestion de version de sources.
Non Networked File System.
Outil permettant d'avoir un système de fichier identique sur des machines n'étant pas connectée entres elles.
Les fichiers peuvent être modifiés sur n'importe quelle machine.
Un medium passe de machine en machine pour faire les mises à jour.
En cas de conflit, si NNFS a fait un ``mauvais´´ choix, l'utilisateur a accès à l'autre version.
Le modèle géométrique était modifié en utilisant l'algorithme RCU.
Marche très bien la plupart du temps.
Le dernier à modifier gagne.
Pas de blocage, mais pas asynchrone car en mode connecté.
Simplification du noyau Dereve.
Vue fichier du graphe
Noeuds permettant la communication vers des noeuds sur d'autres machines.
Donc pas d'accès au modèle total si pas d'accès au réseau.
TOMUSS permet à plusieurs personnes de saisir des notes en mode déconnecté.
Les données sont toutes chargées dans le navigateur, la connexion n'est plus nécessaire ensuite sauf pour les sauvegardes et mises à jour.
L'astuce pour éviter les conflits est de nommer les entités créées avec un identificateur dépendant de la session.
Aucune donnée ne peut être créée avec le même identifiant.
Quand on synchronise deux machines, il faut que pour chaque donnée :
S'il n'y a pas de conflit, on change la version courante.
S'il y a un conflit, la version locale gagne afin que la vue de l'utilisateur soit inchangée.
S'il y a un conflit pour une liste cohérente, alors on considère qu'il y a un conflit pour toutes les valeurs de la liste cohérente.
Par exemple dans (x, y), si une personne modifie 'x' et l'autre 'y' en même temps, l'entité (nx, ny) n'a pas de sens car aucun des 2 ne l'a créée.
Le temps est relatif : on ne peut pas ordonner des événements temporels se situant dans des lieux différents.
La session est un identificateur unique que l'on peut créer comme la concaténation :
du nom de la machine.
de la date de lancement du processus.
du numéro du processus.
Cette création est locale et ne nécessite pas de serveur.
Il y a normalement une seule session par machine. L'utilisateur peut la suspendre et la reprendre.
L'identificateur de valeur est le couple :
Session ID
Nombre de valeurs précédemment créées par la session.
La version d'une valeur est la liste ordonnée de tous les Sessions ID ayant modifié la valeur depuis sa création.
Une donnée peut être de différents types :
Un type de base : entier, flottant, chaine, point, matrice...
Une donnée détruite (très important comme type)
Une liste de Value ID permettant de construire des arbres et graphes.
Une liste cohérente de couple Value ID, Version ID.
Le système ne résoud pas les conflits. Il faut donc qu'une même valeur puisse avoir plusieurs versions.
Une valeur contient :
Une liste de couple : Version ID, Data
Le Version ID que l'utilisateur désire voir sur son écran.
L'algorithme est simple au final, mais il est loin d'être trivial.
On fait les trois étapes suivantes :
Pour mettre à jour S1 à partir des données de S2 :
Toutes les valeurs présentes dans S2 n'existant pas dans S1 sont recopiées (change l'affichage).
Pour toutes les valeurs de S2 présentes dans S1 on ajoute les versions de la valeur non connues par S1. Cela ne change pas l'affichage.
Trois étapes successives :
Pour toutes les valeurs, indique que la version n'est pas calculée.
Pour toutes les valeurs ne faisant pas partie d'une liste cohérente et ne pouvant être mise à jour : on fige la version récursivement.
Pour toutes les valeurs ne faisant pas partie d'une liste cohérente : on change la version récursivement pour la mettre à la nouvelle version.
Pour figer/changer la version récursivement de la valeur :
Si elle est déjà calculée : stop
Note la version comme déjà calculée.
Change la version courante.
Si la version courante de la valeur est une liste cohérente, change la version récursivement pour tous les éléments de la liste cohérente.
Pour toutes les listes cohérentes utilisant l'ancienne valeur et pour lesquelles la version n'est pas calculée : change la version récursivement de la liste pour qu'elle utilise la nouvelle version de la valeur.
Pour choisir la version courante dans une liste de versions plus récentes possible :
Fonctions récursives haut/bas.
Pour chaque version de chaque valeur :
Nécessaire si courante.
Nécessaire si pas ancienne.
Quand on marque une donnée nécessaire :
On marque les éléments de liste cohérentes nécessaire.
On marque les listes cohérentes qui utilisent la donnée comme nécessaire. Le minimum possible
Tant qu'une version inutile a put être enlevée :
Pour chaque valeur, enlève les versions qui respectent les conditions suivantes :
pas utilisées par une liste cohérente.
n'est pas nécessaire.
L'implémentation est écrite en Python et fonctionne en simulant plusieurs sessions avec un seul processus.
Les valeurs détruites doivent rester dans le modèle afin d'indiquer aux sessions qui ne sont pas au courant qu'il faut détruire la valeur.
Il faut clairement une liste de machines.
Avoir une liste des machines avec la date de synchronisation ne fonctionne pas car on ne connait pas l'état du système à une date passée.
Donc chaque machine indique dans la donnée détruite qu'elle est d'accord. La donnée est détruite quand tout le monde est d'accord.
L'application affiche le modèle avec son interface utilisateur classique auquel on ajoute :
Choix du travail en mode connecté ou déconnecté.
Des alertes visuelles non intrusives pour indiquer les changements venant d'autres sessions.
Un indicateur de conflit permettant facilement de choisir la version cohérente que l'on veut voir.
Il faut un algorithme permettant de minimiser le traffic réseau lors d'un mise à jour.
Utiliser un journal ?
Signer les versions que l'on diffuse.
On ne peut garantir que quelqu'un censure un donnée afin de ne pas la diffuser.
Qui veut écrire un article sur le sujet ?