Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Algorithmique r´epartie Philippe Bidinger Universit´ e Joseph Fourier 20/03/2014 Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Outline 1 Complexit´e 2 Variantes AST 3 Arbre de recouvrement minimal 4 Temps dans les syst`emes asynchrones Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Evaluation des algorithmes Complexit´e deux grandeurs importanes Nombre de messages envoy´es Temps d’ex´ecution Notation O(...), fonction de param`etres du graphe : Nombre de noeuds, d’arˆetes, diam`etre Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Temps d’ex´ecution Soit une trace α = π0 ...πn ... On associe `a chaque ´evenement un temps t α = π0t0 ...πntn ... (tn ) est une suite croissante qui repr´esente l’instant d’ex´ecution de chaque action. (tn ) doit v´erifier les contraintes suivantes. le temps maximum qu’une action de sortie d’un processus peut-ˆetre possible avant d’ˆetre ex´ecut´ee est inf´erieur `a une constante l le temps maximum qu’une action de sortie d’un canal peut-ˆetre en attente avant d’ˆetre ex´ecut´ee est inf´erieur `a une constante d Le temps d’arriv´ee ´evenement est la borne sup´erieure de son temps dans toutes les ex´ecutions possibles Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Temps d’ex´ecution En r´esum´e, on consid`ere l’ex´ecution la plus d´efavorable On mesure le temps d’arriv´ee d’un ´evenement particulier (ex : action leader) Le temps pass´e par un message dans un canal est d Le temps d’ex´ecution d’une action est l (ind´ependamment du nombre d’action possibles) Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Complexit´e de l’algorithme LCR - messages Anneau unidirectionnel de taille n Messages : Pire cas : UINs d´ecroissants 1 + ... + n = Complexit´e : O(n2 ). n∗(n+1) 2 Temps d’ex´ecution : n(d + l) + l Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Complexit´e de l’algorithme AST Graphe G = (V ,E ) (Vertice = noeuds, Edge = arˆetes) Messages : O(|E |) (au plus un message par arˆete dans chaque direction) Temps d’ex´ecution : diam ∗ (l + d) + l Certains chemins de l’AST peuvent ˆetre plus grands que le diam`etre du graphe. N´eanmoins, le temps d’ex´ecution s’exprime en fonction du diam`etre En effet, dans une ex´ecution, le temps pour qu’un noeud re¸coive son premier message depuis i0 ne peut pas ˆetre plus grand que le plus mauvais temps par le plus court chemin. Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Outline 1 Complexit´e 2 Variantes AST 3 Arbre de recouvrement minimal 4 Temps dans les syst`emes asynchrones Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Retour sur l’algorithme AST L’arbre calcul´e est diff´erent pour chaque trace ie. de l’ordonnancement des ´ev`enements Pas forc´ement minimal Rappel : Un arbre minimal est tel que le chemin entre la racine et un noeud est le plus court possible. Exemples Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Variantes et applications de l’algorithme AST Diffusion : enrichissement des messages (piggybacking) pour diffuser (broadcast) une information `a tous les noeuds Accus´es de r´eception (Algo ASTAck) Chaque feuille ou noeud qui poss`ede d´ej`a un p`ere renvoie un accus´e de r´eception (ack) `a l’emetteur d’un message Chaque noeud interne attend les ack des voisins Lorsqu’ils sont tous arriv´es, ils envoient un ack au p`ere L’algorithme se termine quand la racine re¸coit tous les acks attendus Cet algorithme est parfois appel´e Vague Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Complexit´e de ASTAck Messages O(|E |) Comme pour AST, un message d’ack pour chaque message envoy´e Temps d’ex´ecution O(n ∗ (l + d)) Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Variantes et applications de l’algorithme AST Convergecast Les ack peuvent ˆetre enrichis pour faire remonter une information vers la racine Ex : calcul du nombre de noeuds du graphe (TP2) Pointeurs sur les enfants : lors de la MAJ du p`ere, un noeud peut r´epondre `a l’´emetteur avec un message parent ou !nonparent!. l’´emetteur met `a jour sa liste d’enfants en fonction AST comme pr´ecalcul La cr´eation d’un arbre de recouvrement (avec pointeurs sur les enfants) est souvent une premi`ere ´etape L’arbre peut-ˆetre utilis´e plusieurs fois pour diffuser ou ”convergecaster” des informations Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Variantes et applications de l’algorithme AST Application `a l’´election de leader (cf. TP 3) Utilisation d’UID Chaque processus initie un ”broadcast-convergecast” pour d´eterminer le plus grand UID du syst`eme Le plus grand UID sera le leader On a besoin de pouvoir faire des vagues multiples Remarque : ne pas confondre Id (adresse) et UID (valeur utilis´ee pour les besoin de l’algorithme). Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Outline 1 Complexit´e 2 Variantes AST 3 Arbre de recouvrement minimal 4 Temps dans les syst`emes asynchrones Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones ASTMin Id´ee : modifier AST pour construire un arbre de recouvrement minimal Chaque noeud m´emorise la distance courante depuis la racine, 0 pour l’initiateur, infinie pour les autres. L’initiateur envoie la distance 1 `a ses voisins. Lorsqu’un noeud obtient une distance plus petite que la sienne, il met `a jour son p`ere, et transmet cette nouvelle distance `a ses voisins. Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones ASTMin : Limitation D`es qu’un processus a un p`ere, il a un chemin vers la racine, mais pas forc´ement le plus court Ce sera le cas quand l’algorithme sera termin´e Mais comment les noeuds peuvent savoir quand il n’y aura plus de corrections `a faire? Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Complexit´e Messages : O(n|E |) Chaque noeud peut obtenir au plus n proposition de distance A chaque changement de distance, au plus O(|E|) messages sont ´emis. Temps d’ex´ecution : O(diam.(l + d)) Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Outline 1 Complexit´e 2 Variantes AST 3 Arbre de recouvrement minimal 4 Temps dans les syst`emes asynchrones Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Absence d’horloge globale Dans un syst`eme asynchrone, les processus n’ont pas acc`es `a une horloge commune. Temps de communication inconnus =⇒ impossibilit´e de synchroniser les horloges. Cons´equence : impossible d’ordonner les messages en fonction de leur moment d’´emission Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Exemple Forum de discussion r´eparti (question / r´eponse) Chaque participant poss`ede une copie locale des discussions Chaque intervention (question ou r´eponse) diffus´ee aux autres participants Q P1 Q Q A P2 A A P3 Probl`eme : le processus P3 re¸coit une r´eponse avant la question. On ne peut pas utiliser les temps d’´emission pour les r´eordonner Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Temps logique Leslie Lamport ”Time, Clocks, and the Ordering of Events in a Distributed System”. 1978. Notion de temps logique. Utile dans de nombreux algorithmes Contexte : Syst`eme asynchrone, send/receive ou broadcast, canaux FIFO. Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Diagramme d’´evenements Q P1 Q Q A P2 A A P3 On appelle une telle figure un diagramme d’´ev`enements C’est une repr´esentation graphique d’une trace Chaque ligne horizontale repr´esente l’´evolution un processus Temps croissant de gauche `a droite Even`ements (send, ´eventuellement !broadcast!, receive, actions internes...) mat´erialis´es sur la ligne send (ou !broadcast!) et receive correspondant reli´es par une ligne Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Relation de causalit´e Soit une trace α On d´efinit la relation de causalit´e → comme suit : Si π1 et π2 sont des actions de α, on a π1 → π2 s’il existe un chemin de π1 vers π2 dans le sens du temps dans le diagramme d’´evenements correpondant `a α. Informellement, π1 → π2 signifie que π1 a pu provoquer π2 . Propri´et´e : Si α est une trace ´equitable d’un syst`eme, alors tout r´eordonnancement des actions de α compatible avec → est encore une trace ´equitable. Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Temps logique D´efinition Un temps logique est une fonction ltime des evenements d’une trace α dans T (un ensemble totalement ordonn´e, en g´en´eral les entiers) tel que : Tous les ´evenements ont un TL diff´erent Les TL des ´evenements d’un processus croissent strictement en fonction du temps Les TL croissent strictement le long d’un chemin dans le sens du temps Propri´et´e : Si α est une trace ´equitable d’un syst`eme, alors il existe une trace α0 telle que : α0 contient les mˆeme ´ev`enements que α les ´ev`enements de α0 apparaissent dans le mˆeme ordre que leur LT l’ordre des ´ev`enements est respect´e pour chaque processus Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Transformation de Lamport Transformation qui peut s’appliquer de mani`ere transparente `a n’importe quelle algorithme Autrement dit, elle d´efinit des r`egles de modification d’un algorithme sans changer son fonctionnement Permet d’attribuer des TL `a chaque ´ev`enement Chaque processus a un compteur local c , initialement 0 T est l’ensemble des paires (c,i) ordonn´ees lexicographiquement c est une valeur de compteur, i l’indice d’un processus. i sert `a departager deux valeurs de compteur identiques Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Principe de la transformation Le compteur est increment´e d’au moins 1 `a chaque action Le TL associ´e `a un ´evenement est la valeur du compteur juste apr`es l’´ev`enement, associ´ee `a l’indice du processus (pour d´epartager les ´evenement avec une mˆeme valeur de c). Lors d’une action send(m), le processus calcule la nouvelle valeur de c et envoie le (timestamp) (c,i) avec le message m (idem pour broadcast(m)) Lors d’une r´eception de message, le processus met `a jour son compteur avec une valeur strictement sup´erieure `a sa valeur pr´ec´edente, mais aussi au TL du message. Propri´et´e : les valeurs ainsi associ´es aux ´evenements v´erifient les propri´et´es d’un temps logique Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Applications Tr`es nombreuses applications Algorithme d’exclusion mutuelle Capture d’´etat global Diffusion ”causale” Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Retour sur l’exemple initial On applique la transformation de Lamport Lors de la r´eception d’un message <m,tm>, le processus s’assure qu’il n’y aura plus de message plus ancien avant de le traiter Il m´emorise le dernier temps logique connu de ses voisins (ti ,i ∈ V ) en fonction des messages qu’il re¸coit D`es que ∀i ∈ V ,tm <= ti , le message m est retransmis. En pratique, on peut rajouter des messages artificiels pour limiter l’attente Chaque processus diffuse un ”heartbeat” p´eriodiquement Philippe Bidinger Algorithmique r´ epartie Complexit´ e Variantes AST Arbre de recouvrement minimal Temps dans les syst` emes asynchrones Diffusion causale On peut abstraire cet algorithme sous la forme d’une primitive de communication appel´ee diffusion causale Philippe Bidinger Algorithmique r´ epartie
© Copyright 2024 ExpyDoc
