Résolution d’un graphe de relations de mise à jour

L’utilisation des liens de mise à jour d’objets est utilisé dans des cas biens spécifiques mais revêt une grande importance par exemple dans la mise à jour de programmes. Cela a notamment des implications sur la sécurité des programmes gérés sous forme d’objets.

Les liens de mise à jour n’ont pas de contraintes et peuvent donc créer des graphes de liens entre objets de forme quelconque. Cependant, l’usage de ces liens dans nebule nécessite que pour un objet donné on obtienne un unique autre objet. Cet objet doit être disponible puisque l’on est dans le cas d’un usage, c’est à dire de son utilisation immédiate.

La résolution d’un graphe de liens permet d’obtenir l’identifiant un objet dérivé unique et disponible pour un objet de départ en tenant compte de la validité des liens. Cette résolution est spécifique à nebule et se fait sous forme arborescente en ne tenant compte de des liens descendants et non bouclés.

Table des matières :

  1. Lien de mise à jour
  2. Remplacement de lien de mise à jour
  3. Mise à jour arborescente
  4. Gestion des objets manquants
  5. Résolution des boucles

Cette méthode de résolution va maintenant être expérimentée grandeur nature dans sylabe pour la gestion des versions des programmes.

favicon

1. Lien de mise à jour

Le lien de type u permet de définir qu’un objet a été mis à jour. C’est à dire qu’un (nouvel) objet remplace un autre objet. Voir la documentation nebule v1.1 lien u.

On ne prend en compte que les liens descendant, c’est à dire les liens qui ont en source l’objet sur lequel on est positionné dans la recherche.

20140116 nebule - dérivés arborescents - 1

Prenons l’exemple d’un programme. Il y a une version du programme reconnue comme étant la dernière en date, l’objet A. Si on souhaite diffuser une nouvelle version, l’objet B, on crée le lien de type u entre A et B. Ce lien u1 est définit avec une date.

favicon

2. Remplacement de lien de mise à jour

Il n’est pas interdit de définir un nouveau lien de mise à jour vers un autre objet. Le mieux est de marquer comme supprimé le précédent lien de mise à jour. Mais cette suppression n’est pas toujours possible ou souhaitable si les liens sont générés (et signés) par des entités différentes.

Chaque lien a une validité propre avec sa signature et une validité sociale en fonction de la confiance que l’on accorde à l’entité signataire. Certains liens peuvent donc ne pas être reconnus comme valides socialement et donc ne pas être pris en compte lors du parcours de l’arborescence. La validation sociale sera traité ultérieurement, elle indique un état social valide ou non et le cas échéant un niveau de validité sociale.

Si il y a plusieurs liens valides mais d’entités différentes, il doit toujours être tenu compte du lien dont la validité sociale est la plus forte.

Ensuite, si il y a plusieurs liens de mise à jours valides et socialement équivalents, il doit être tenu compte du lien le plus récent.

20140116 nebule - dérivés arborescents - 2

Dans notre exemple du programme, la mise à jour vers la version la plus récente, objet C, est assuré par un lien de mise à jour u2 plus récent que le lien u1. Si ce lien u2 avait été généré par une entité peu fiable, il n’aurait pas été pris en compte.

favicon

3. Mise à jour arborescente

Un objet peut être mis à jour vers un autre objet, lui-même peut aussi être mis à jour vers encore un autre objet. C’est un schéma de mise à jour arborescent. Il faut être capable de résoudre cette arborescence pour un objet de départ définit, c’est à dire de parcourir l’arborescence de façon à obtenir un seul objet. Le nombre de possibilités offertes par une arborescence doit donc être réduite par des règles de parcours de l’arborescence.

Localement dans l’arborescence, la résolution de la branche à suivre ne tient compte que des liens immédiats. Cela exclut donc tous les liens plus loin dans les branches quel qu’en soit leur validité sociale, leur nombre ou leur date de création.

20140116 nebule - dérivés arborescents - 3

Le cas des objets absents est traité en bout de branche mais pas sur un embranchement. Cependant, une branche peut être désactivée si la résolution a échouée à trouver un objet valide. Dans ce cas la résolution de l’embranchement est refaite dans tenir compte de la (les) branche(s) désactivée(s). Si il ne reste aucune branche valide, le cas doit être traité comme un bout de branche.

Il est toléré qu’une branche court-circuite une autre branche. La résolution locale du parcours des branches fera que les deux branches qui se rejoignent seront traitées comme deux branches indépendantes.

20140116 nebule - dérivés arborescents - 4

Dans notre exemple du programme, cela peut-être utile pour accélérer la résolution de l’arborescence. La sortie d’une nouvelle version majeur du programme, l’objet D, peut être lié à la précédente version majeur et court-circuiter toutes les versions intermédiaires.

Évidemment, la recherche peut avoir comme point de départ un objet au milieu de l’arborescence et non l’objet le plus ancien. C’est dans ce cas plus rapide et toutes modifications des liens avant l’objet de départ seront ignorées.

La résolution de l’arborescence s’arrête quand on est arrivé à un bout de branche, c’est à dire quand il n’y à plus de branche descendante valide ou que les branches restantes de débouchent sur aucun objet présent. Ce peut être l’objet de départ, dans ce cas il n’y à pas de mise à jour, même si l’objet n’est pas présent.

favicon

4. Gestion des objets manquants

Lors du parcours de l’arborescence, on peut arriver sur un bout de branche dont l’objet n’est pas disponible. Dans ce cas, on remonte d’un niveau et on ré-analyse l’embranchement sans cet objet absent.

20140116 nebule - dérivés arborescents - 5

Il est possible que lors du parcours de l’arborescence, plusieurs objets ne soient pas disponibles, on remontera autant que nécessaire jusqu’à trouver un objet valide ou le point de départ. Si un objet manque en cours de parcours, ce n’est pas gênant si l’objet en bout de branche est présent. Les liens restent valides que les objets soient présents ou non.

20140116 nebule - dérivés arborescents - 6

Il est possible dans certains cas de résoudre l’arborescence des mises à jours sans vérifier la présence des objets. C’est par exemple le cas si on veut obtenir la mise à jour la plus récente d’un objet. Cette résolution donne l’identifiant de l’objet qui devra être trouvé par ailleurs (téléchargement). Cette recherche peut être complexe à mettre en place puisqu’elle peut impliquer le téléchargement des liens des objets au fur et à mesure que l’on parcours et découvre l’arborescence.

Dans notre exemple du programme, une recherche préalable a montré que la dernière version, l’objet E, n’était pas présent. Il a été téléchargé et est maintenant pleinement utilisable.

Il existe un cas non traité ici et qui nécessitera plus de recherches, c’est lorsqu’un objet n’est pas présent mais qu’il existe en version protégé (chiffré). Suivant si l’usage est public ou non, il en sera tenu compte ou pas.

favicon

5. Résolution des boucles

On est partit avec une résolution d’un graphe en utilisant une méthode de parcours d’une arborescence. Mais il faut prendre en compte le cas hypothétique où il y a des retours dans les liens, des boucles. La résolution doit pouvoir fonctionner quoi qu’il arrive.

Parcourir plus d’une fois une boucle n’a pas d’intérêt puisque l’analyse des embranchements se fera de la même façon. Il est donc inutile de prendre en compte un embranchement déjà traité, donc un objet déjà traité. Il faut tenir à jour une table des objets qui ont déjà été traités lors du parcours de l’arborescence pour ne plus en tenir compte. Les objets des branches invalidées peuvent rester dans cette table, ils ne seront pris en compte même si des liens court-circuitent les branches invalidées.

20140116 nebule - dérivés arborescents - 7

Dans notre exemple du programme, un lien de mise à jour u6 vers une version antérieur, l’objet A, n’a pas de justification, il n’est pas pris en compte parce que l’objet A est déjà dans l’arborescence traitée. Si on veut annuler une mise à jour, il faut marquer à supprimer le lien de mise à jour, ici les liens u1, u2 et u5.

4 Responses to “Résolution d’un graphe de relations de mise à jour”

  1. nebule » Blog Archive » Détournement de liens de mise à jour Says:

    […] (Re)Découvrir votre nébuleuse de l'information « Résolution d’un graphe de relations de mise à jour […]

  2. sylabe » Blog Archive » Détournement de liens de mise à jour Says:

    […] nebule en php, qui est utilisée par sylabe, intègre depuis ce matin le code nécessaire à la résolution des graphes des liens de mise à jour d’un objet. Ce bout de code est encore en cours de […]

  3. nebule » Blog Archive » Auto déploiement répliqué d’un code Says:

    […] La librairie nebule de référence en php gère maintenant les liens de mise à jour d’objets conformément à la méthode décrite dans l’article sur la Résolution d’un graphe de relations de mise à jour. […]

  4. sylabe » Blog Archive » Avancement Says:

    […] 2 jours, le code du bootstrap est profondément remanié pour intégrer la résolution d’un graphe de relations de mise à jour des objets et surtout l’auto déploiement répliqué d’un code. Il intègre une version […]