Diffusion

Chang et Roberts

Pour envoyer moins de messages

Chang et Roberts, 1979

A

5

4

3

7

2

Chang et Roberts, 1979

Le demandeur envoie son aptitude et son id.

Si je reçois une aptitude

    Je la compare à la mienne

    Je propage la plus grande des deux

A

5

4

3

7

2

"A est plus apte que moi..."

d'un autre

Chang et Roberts, 1979

Le demandeur envoie son aptitude et son id.

Si je reçois une aptitude

    Je la compare à la mienne

    Je propage la plus grande des deux

d'un autre

A

5

4

3

7

2

"A est plus apte que moi..."

Chang et Roberts, 1979

Le demandeur envoie son aptitude et son id.

Si je reçois une aptitude

    Je la compare à la mienne

    Je propage la plus grande des deux

d'un autre

A

5

4

3

7

2

"Je suis plus apte que A !"

Chang et Roberts, 1979

Le demandeur envoie son aptitude et son id.

Si je reçois une aptitude

    Je la compare à la mienne

    Je propage la plus grande des deux

d'un autre

A

5

4

3

7

2

"D est plus apte que moi..."

Chang et Roberts, 1979

Le demandeur envoie son aptitude et son id.

Si je reçois une aptitude

    Je la compare à la mienne

    Je propage la plus grande des deux

d'un autre

A

5

4

3

7

2

"D est plus apte que moi..."

Chang et Roberts, 1979

Le demandeur envoie son aptitude et son id.

Si je reçois une aptitude

    Je la compare à la mienne

    Je propage la plus grande des deux

d'un autre

A

5

4

3

7

2

"C'est ma requête, je suis élu !"

Chang et Roberts, 1979

Le demandeur envoie son aptitude et son id.

Si je reçois une aptitude

    Je la compare à la mienne

    Je propage la plus grande des deux

Si je reçois ma propre aptitude

    La demande a fait le tour, je suis élu !

d'un autre

Je propage le résultat

Si je reçois un résultat

Je le propage

A

5

4

3

7

2

"Ah, c'est D qui a gagné !"

Chang et Roberts, 1979

Le demandeur envoie son aptitude et son id.

Si je reçois une aptitude

    Je la compare à la mienne

    Je propage la plus grande des deux

Si je reçois ma propre aptitude

    La demande a fait le tour, je suis élu !

d'un autre

Je propage le résultat

Si je reçois un résultat

Je le propage si ce n'est pas le mien

Sinon, l'élection est finie, je suis l'élu

A

5

4

3

7

2

"Tout le monde sait, c'est officiel !"

Chang et Roberts, 1979

Le demandeur envoie son aptitude et son id.

Si je reçois une aptitude

    Je la compare à la mienne

    Je propage la plus grande des deux

Si je reçois ma propre aptitude

    La demande a fait le tour, je suis élu !

d'un autre

Je propage le résultat

Si je reçois un résultat

Je le propage si ce n'est pas le mien

Sinon, l'élection est finie, je suis l'élu

A

5

4

3

7

2

Chang et Roberts

Gestion de demandes concurrentes

Demandes concurrentes

A

5

4

3

7

2

Demande d'élection

A

5

4

3

7

2

Demande d'élection

Demandes concurrentes

A

5

4

3

7

2

Demande d'élection

Demandes concurrentes

A

5

4

3

7

2

Demande d'élection

"Une élection est déjà en cours, et cette nouvelle élection n'a pas trouvé mieux, je l'ignore."

Demandes concurrentes

A

5

4

3

7

2

Demande d'élection

Demandes concurrentes

Quand je suis déjà en cours d'élection,

    Si je reçois une aptitude plus basse, je l'ignore

(Sinon, l'algorithme normal s'applique)

Demandes concurrentes

Chang et Roberts

Résumé et Performances

Résumé

• J'entre en élection

Demande d'élection

Réception d'une aptitude

• Je compare l'aptitude reçue avec la mienne

• Je propage la plus grande, avec l'ID associé

• Je compare l'aptitude reçue avec la mienne

• Je propage celle reçue ssi elle est plus grande.

• Si c'est la mienne

• J'envoie le résultat

• Si ce n'est pas la mienne

Réception d'un résultat

• Je suis l'élu

• Je note et je propage

• J'envoie mon aptitude et mon ID

• Je sors d'élection

• Je sors d'élection

Performances

Communication

Durée d'une élection

Chang et Roberts

Pseudocode

Variables

Pseudocode

Remarques

Plus besoin de stocker les aptitudes de tous les autres.

Plus besoin de dépendre de T.

Tous les envois se feront à suivant.

Écouter infiniment les événements suivants :

Demande d'élection

Demande d'obtention de l'élu par la couche applicative

Réception d'une annonce {i, apt_i}

Réception d'un résultat {i}

Note : les traitements de ces événements sont faits de manière séquentielle.

Initialisation

Pseudocode

(On omet la mise à jour de l'aptitude, qui déclenche simplement une élection)

Si inElection

    Refuser la demande

Sinon

    Envoi d'une annonce {self, apt_self}

    inElection ← true

Demande d'élection

élu ← i

inElection ← false

Si élu != self

    Envoi de résultat {i}

Réception d'un résultat {i}

Pseudocode

Si (apt_self, self) > (apt_i, i)

    Si pas inElection

        Demande d'élection

Sinon, si i == self

    Envoi de résultat {i}

    inElection ← false

Sinon

    Envoi d'annonce {i, apt_i}

    inElection ← true

Réception d'une annonce {i, apt_i}

Retourner élu.

Demande d'obtention de l'élu

Pseudocode

Exercices

Exercice 1

On suppose 1s de transit pour chaque message

Cinq processus, formant un anneau dans le sens suivant

• A, avec aptitude initiale de 2
• B, avec aptitude initiale de 5
• C, avec aptitude initiale de 8
• D, avec aptitude initiale de 2
• E, avec aptitude initiale de 7

Les événements suivants ont lieu

• T=1 : C demande une élection
• T=1 : D demande une élection

A

Exercice 1 - Solution

Que se passe-t-il en cas de panne d'un processus ?

• Répondez pour chaque état dans lequel un processus peut se trouver (en élection ou non, phase d'annonce ou de résultat, élu ou non)

Réfléchissez à des solutions pour chaque problème.

Exercice 2