Examen dalgorithmique distribuée PDF

Corrigé - Algorithmes distribués

Corrigé - Algorithmes distribués. M1 ILC ISI

Algorithmique Distribuée

Algorithme Distribué. Exemple : Calcul d'un arbre couvrant. Algorithmique Distribuée. 58. Page 59. • Entrées réparÅes. Algorithme Distribué. Exemple : Calcul d'

Examen semestriel Algorithmique et Systèmes distribués (Corrigé) 1

Algorithmique et Systèmes distribués (Corrigé). 1 H30. Exercice 1 (08 points) L'algorithme utilisé est celui de Lamport. Justification : dans la file des ...

Algorithmes Distribués

Oct 26 2023 L'Exercice 1 propose de détailler la version distribué de cet algorithme. ... ties 1-orientées; et (3) corriger les arêtes non orientées ...

Untitled

Exercice 2. (12 points). Soit l'algorithme distribué donné ci-après

Corrigé

Examen semestriel. Algorithmique et Systèmes distribués. 1 H30. Corrigé. Exercice 1 (8 points) : On considère un système réparti à trois sites S1 S2

APD 3.Distribué (suite)

en distribué solutions souvent basées sur Horloges logiques. Quelques algorithmes distribués d'exclusion mutuelle : Algorithme de Lamport 1978 amélioré par

Examen semestriel Algorithmique et Systèmes dexploitation

Algorithmique et Systèmes d'exploitation distribués (Corrigé). 1 H30. Exercice On utilise l'algorithme RicartAgrawala. Question 1 : Que fait le site 2 ...

Module de Algorithmique et Systèmes dexploitation Distribués Corrigé

Les messages de type Release n'existent pas dans l'algorithme de Ricart – Agrawala . (2.5 Points). Exercice 2 : On considère un système distribué constitué

Untitled

Exercice 2. (12 points). Soit l'algorithme distribué donné ci-après

Corrigé - Algorithmes distribués

On associe un estampillage vectoriel de Lamport aux événements du scénario de l'exercice 1. Indiquer les valeurs de toutes estampilles. e. 1 e. 5.

Examen semestriel Algorithmique et Systèmes dexploitation

Algorithmique et Systèmes d'exploitation distribués (Corrigé). 1 H30. Exercice 1 (06 points) : La détection de la terminaison d'un calcul est l'un des

Examen semestriel Algorithmique et Systèmes distribués (Corrigé) 1

Exercice 1 (08 points) : La figure suivante montre une partie des messages échangés entre 3 processus. (P1 P2

Algorithmes Distribués

4 mars 2022 2.4 Exercices . ... exécuter sur un système distribué A un algorithme conçu pour un système B avec

Autour des algorithmes distribués

8 mars 2017 15.3 Analyse des algorithmes distribués probabilistes . ... 15.5 Un premier exemple : un algorithme distribué probabiliste pour élire dans ...

Examen de rattrapage (Corrigé) Algorithmique et Systèmes répartis

Exercice 1 (7 points) : On considère un système réparti à trois (3) sites : 1 Question 1 : En appliquant l'algorithme de synchronisation de Lamport

Algorithmique Distribuée

L'algorithme 1 résout l'exclusion mutuelle dans un anneau unidirecfionnel. Remarque 2. Si on lève l'une des hypothèses la preuve ne marche plus ! 95.

Examen semestriel Algorithmique et Systèmes dexploitation

Examen semestriel. Algorithmique et Systèmes d'exploitation distribués (Corrigé) Exercice 2 (10 points) : On considère l'algorithme d'élection de ...

Examen semestriel Algorithmique et Systèmes distribués 1 H30

Corrigé. Exercice 1 (8 points) : Un processus du site 2 d'un système Q1/ Quel est l'algorithme (vu en cours) qui est utilisé dans ce cas pour la gestion ...

Quels sont les exercices corrigés d’algorithmique?

Exercices Corrigés d’Algorithmique – 1ére Année MI 5 EXERCICE 1 Ecrire un algorithme qui demande un nombre à l’utilisateur, puis calcule et affiche le carré de ce nombre. Algorithme Carre ; Var X,X2 :reel ; Début Ecrire(‘Donner un reel’) ; Lire(X) ; X2?X*X ; Ecrire(‘Le carré de ’, X,’ est: ’,X2) ; Fin.

Comment faire un exercice algorithme corrigé les tableaux ?

Exercice algorithme corrigé les tableaux (Partie III), tutoriel & guide de travaux pratiques en pdf. Ecrivez un algorithme qui permette la saisie d’un nombre quelconque de valeurs, sur le principe de l’ex 8 (dans la série Les Tableau (Partie 2)). Toutes les valeurs doivent être ensuite augmentées de 1, et le nouveau tableau sera affiché à l’écran..

Quels sont les principes utilisés pour les algorithmes distribués ?

Nous allons décrire ici deux principes utilisés pour ces algorithmes distribués : — la patate chaude ou routage par saut qui sont trai tés dans le paragraphe 7.3.1. routage adaptatif, — l’inondation ou routage par la source qui sont tra ités dans le paragraphe 7.3.2. sur l’inondation .

Examen d"algorithmique distribuée

EPITA ING1 2011 S2; A. DURET-LUTZ

Durée : 1 heure 30

Juin 2009Corrigé

Consignes

T ousles documents (su rpapier) sont autorisés. Les calculatrices, téléphones, PSP et autres engins électroniques ne le sont pas. Répondez sur le suje tdans les cadr esprévus à cet ef fet,ainsi que sur les figur es.

Il y a 5 pages d"énoncé.

Rappelez votre nom en haut de chaque feuilleau cas où elles se mélangeraient. Le barème est indicat ifet corr espondà une note sur 27.

1 Horloges de Lamport et causalité (9 points)

On considère un système distribué constitué de 4 sitesP1,P2,P3,P4, s"envoyant des messages de façon

asynchrone comme représenté par la figure suivante. Les événements d"un processus, représentés par

des gros points noirs, sont soit des événements locaux (étapes d"un calcul), soit des envois ou des

réceptions de messages. Ces événements sont datés par un système d"horloges de Lamport, initialisées

à 0 dans chaque état initial.P

4P 3P 2P

10120120101

a bc d

456893456789103567102678

1.(2 points)Indiquez au dessus de chaque point de la figure, la valeur de l"horloge du processus

où se produit l"événement correspondant.

2.(2 points)On considère les événementsa,b,cetdde la figure. Cochez toutes les formules justes :

a!ba!cb!ca!d b!ac!ac!bd!a akbakcbkcakd 1 On considère les deux coupures désignéesC1etC2dans la figure ci-dessous (qui reproduit les communications de la figure précédente) :P 4P 3P 2P 1C 1C

23.(2 points)Les coupuresC1etC2sont-elles cohérentes? Justifiez vos réponses.

(N"hésitez pas à nommer des états sur la figure pour vous aider à vous justifier.)

Réponse :C

1est cohérente : tous les messages reçus dans la coupures ont étés envoyés dans la coupure.

2n"est pas cohérente :P1a reçu un message qui a été envoyé après la coupure.4.(3 points)Supposons que l"état de chaque processus ait été sauvegardé au moment de la coupure.

Les valeurs des horloges de Lamport sauvegardées avec chaque processus suffisent-elles pour

décider si la combinaison de ces états locaux forme un état global cohérent? Comment peut-on

détecter ces incohérences autrement? Réponse :Les horloges de Lamport ne suffisent pas. Ce n"est pas parce qu"on aHL(a)de tous les autres sites. Pour vérifier qu"une sauvegarde est cohérente il faut alors consulter

ces compteurs pour s"assurer qu"un sitePin"a pas reçu d"un sitePjplus de messages que le sitePjne lui en a envoyé.2 Horloges matricielles (9 points)

On considère maintenant un système distribué constitué de trois sites nommésP1,P2etP3, utilisant des

horloges matricielles pour dater les événements de chaque processus.

L"étatinitialduchaqueprocessusest2

40 0 0

0 0 0

0 0 03

5 n"a eu lieu dans l"état initial.

Après quelques instants d"exécution, les horloges des processusP1,P2etP3indiquent les dates sui-

vantes : HM 1=2

43 0 1

1 1 0

1 0 23

5 HM2=2

40 0 0

1 2 1

0 0 03

5 HM3=2

42 0 1

1 2 1

1 0 33

Page 2

Pour la suite on supposera que tous les messages envoyés ont été délivrés au plus tard aux dates

indiquées. C"est-à-dire qu"aucun message n"est en transit.

1.(1 point)Au total, combien de messages ont été échangés?

Réponse :Il y a eu quatre message échangés. Les horloges indiquent queP1a envoyé un message au

processusP3(HM3[1,3]),P2a envoyé un message à chaque autre processus (HM3[2,1]) et

(HM3[2,3]), etP3a envoyé un message au processusP1(HM3[3,1]).2.(1 point)Au total, combien d"événements ont eu lieu?

Réponse :Il y a eu 8=HM1[1,1] +HM2[2,2] +HM3[3,3]événements.3.(1 point)Au total, combien d"événements locaux ont eu lieu? (c"est-à-dire sans compter les évé-

nement correspondants à des émissions ou des réceptions de messages, ni l"état initial)

Réponse :8 événements permettent de faire 4 émissions et 4 réceptions. Comme 4 messages ont étés

échangés, il n"y a eu aucun événement local.4.(2 points)Dans quel ordre ont été envoyés les messages deP2? (Justifiez votre réponse.)

Réponse :P

2a envoyé deux messages : l"un versP1et l"un versP3. D"autre partHM2[2,2]nous dit qu"il

n"a exécuté que deux événements. S"il avait envoyé le message versP1en deuxième on aurait

(121)comme seconde ligne deHM1.

Un parking possèdepportes par lesquelles des voitures peuvent entrer ou sortir. Le parking ne doit

jamais contenir plus deNvoitures. À chaque porte se trouve un gardien; les gardiens communiquent

Page 3

en s"envoyant des messages (de façon asynchrone, par exemple à l"aide de pigeons voyageurs supposés

fiables); ils doivent faire en sorte que la capacité du parking ne soit jamais dépassée. Il faut par ailleurs

que, s"il y a régulièrement des sorties, toute voiture qui attend pour entrerpar la porte de son choixy

parvienne en un temps fini.

Décrire un algorithme réparti, qui sera appliqué par chacun des gardiens, afin résoudre le problème.

Cet algorithme utilisera des principes présentés en cours. Le nombre de messages échangés entre deux

entrées de voitures devra être borné.

Mises en gardes :

Une idée (incorr ecte)serait de partager initialement les Nplaces du parking enplots deN/pplaces,

à la responsabilité de chaque gardien. Dans ce cas le gardien peut laisser rentrerN/pvoitures, plus

autant de voitures qu"il a laissé sortir. Cependant, avec ce schéma si toutes les voiture sortent par

la même porte, cette dernière porte devient la seule entrée possible et les voitures qui cherchent à

rentrer par une autre porte y restent bloquées (ce qu"on ne veut pas)

Une autr eidée (tout aussi incorr ecte)serait d"imagi nerque les gar dienstentent de gar derle compte

des places libres en diffusant (aux autres gardiens) des messages "entrée" ou "sortie" à chaque fois

qu"une voiture entre ou sort par leur porte. Le problème est que ces diffusions ne sont pas délivrées

instantanément et qu"elles peuvent aussi se croiser. Cela devient critique lorsqu"il n"y a plus beau-

coup de places libres. Par exemple s"il ne reste plus qu"une place libre, deux gardiens pourraient simultanément laisser rentrer chacun une voiture.

Réponse :On peut utiliser une variante des algorithmes d"exclusion mutuelle à jetons vus en cours. On

stocke sur le jeton le nombre de places disponibles (en plus des informations nécessaires au pro-

tocole de d"exclusion). Un gardien ne peut laisser rentrer ou sortir une voiture que s"il a le jeton et

qu"il peut mettre à jour le nombre de places libres.

cune place n"est libre, il ne fera pas rentrer la voiture et redemandera le jeton aussitôt qu"il l"aura

cédé à un autre gardien.Page 4quotesdbs_dbs4.pdfusesText_8

[PDF] Examen dalgorithmique distribuée

Quels sont les exercices corrigés d’algorithmique?

Comment faire un exercice algorithme corrigé les tableaux ?

Quels sont les principes utilisés pour les algorithmes distribués ?

Examen d"algorithmique distribuée

EPITA ING1 2011 S2; A. DURET-LUTZ

Durée : 1 heure 30

Juin 2009Corrigé

Consignes

Il y a 5 pages d"énoncé.

1 Horloges de Lamport et causalité (9 points)

à 0 dans chaque état initial.P

10120120101

456893456789103567102678

1.(2 points)Indiquez au dessus de chaque point de la figure, la valeur de l"horloge du processus

2.(2 points)On considère les événementsa,b,cetdde la figure. Cochez toutes les formules justes :

23.(2 points)Les coupuresC1etC2sont-elles cohérentes? Justifiez vos réponses.

Réponse :C

1est cohérente : tous les messages reçus dans la coupures ont étés envoyés dans la coupure.

2n"est pas cohérente :P1a reçu un message qui a été envoyé après la coupure.4.(3 points)Supposons que l"état de chaque processus ait été sauvegardé au moment de la coupure.

L"étatinitialduchaqueprocessusest2

40 0 0

0 0 03

43 0 1

1 0 23

40 0 0

0 0 03

42 0 1

1 0 33

Page 2

1.(1 point)Au total, combien de messages ont été échangés?

Réponse :P

2a envoyé deux messages : l"un versP1et l"un versP3. D"autre partHM2[2,2]nous dit qu"il

40 0 0

0 0 03

40 0 0

0 0 03

40 0 0

0 0 03

41 0 0

0 0 03

42 0 1

0 0 03

43 0 1

1 0 23

40 0 0

0 0 03

40 0 0

0 0 03

42 0 1

0 0 13

42 0 1

1 0 23

42 0 1

1 0 33

53 Un Parking (9 points)

Page 3

Mises en gardes :