SDR

Diffusion

Olivier Lemer

Algorithme de Chang et Roberts

Suppositions

Pour l'instant, on supposera

  • Pas de perte de message
  • Pas de duplication de message
  • Pas de changement d'ordre de messages
  • Pas de panne serveur

 

  • Système asynchrone : délai d'envoi non borné

Chang et Roberts

Pour envoyer moins de messages

Chang et Roberts, 1979

L'initiateur envoie son aptitude et son id.

Nouvelle aptitude

A

5

B

E

C

D

4

3

7

2

A-5

En élection

Connait l'élu

Chang et Roberts, 1979

L'initiateur 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

B

E

C

D

4

3

7

2

En élection

Connait l'élu

A-5

"A est plus apte que moi..."

d'un autre

Chang et Roberts, 1979

L'initiateur 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

B

E

C

D

4

3

7

2

En élection

Connait l'élu

A-5

"A est plus apte que moi..."

Chang et Roberts, 1979

L'initiateur 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

B

E

C

D

4

3

7

2

En élection

Connait l'élu

D-7

"Je suis plus apte que A !"

Chang et Roberts, 1979

L'initiateur 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

B

E

C

D

4

3

7

2

En élection

Connait l'élu

"D est plus apte que moi..."

D-7

Chang et Roberts, 1979

L'initiateur 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

B

E

C

D

4

3

7

2

En élection

Connait l'élu

D-7

"D est plus apte que moi..."

D-7

Chang et Roberts, 1979

L'initiateur envoie son aptitude et son id.

Tour d'annonce

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

    L'annonce a fait le tour, je suis élu !

d'un autre

Je propage le résultat

A

5

B

E

C

D

4

3

7

2

En élection

Connait l'élu

"C'est mon annonce, je suis élu !"

D-7

D-7

Chang et Roberts, 1979

L'initiateur envoie son aptitude et son id.

Tour d'annonce

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

    L'annonce 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

B

E

C

D

4

3

7

2

En élection

Connait l'élu

D-7

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

Chang et Roberts, 1979

L'initiateur envoie son aptitude et son id.

Tour d'annonce

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

    L'annonce 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

B

E

C

D

4

3

7

2

En élection

Connait l'élu

D-7

D-7

D-7

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

Chang et Roberts, 1979

L'initiateur envoie son aptitude et son id.

Tour d'annonce

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

    L'annonce 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

B

E

C

D

4

3

7

2

En élection

Connait l'élu

Est l'élu

Tour de résultat

Chang et Roberts

Gestion d'élections concurrentes

Élections concurrentes

A

5

B

E

C

D

4

3

7

2

En élection

Connait l'élu

Est l'élu

Nouvelle aptitude

B-4

A

5

B

E

C

D

4

3

7

2

En élection

Connait l'élu

Est l'élu

B-4

Nouvelle aptitude

A-5

Élections concurrentes

A

5

B

E

C

D

4

3

7

2

En élection

Connait l'élu

Est l'élu

Nouvelle aptitude

D-7

A-5

Élections concurrentes

A

5

B

E

C

D

4

3

7

2

En élection

Connait l'élu

Est l'élu

Nouvelle aptitude

D-7

A-5

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

Élections concurrentes

A

5

B

E

C

D

4

3

7

2

En élection

Connait l'élu

Est l'élu

Nouvelle aptitude

D-7

Élections 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)

Élections concurrentes

Chang et Roberts

Résumé et Performances

Résumé

  • J'adopte la nouvelle aptitude
  • J'entre en élection

Changement d'aptitude

Si je ne suis pas en cours d'élection

Réception d'une aptitude

  • J'entre en élection
  • Je compare l'aptitude reçue avec la mienne
  • Je propage la plus grande, avec l'ID associé

Si je suis en cours d'élection

  • 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

Si c'est moi

Réception d'un résultat

  • Je suis l'élu

Si ce n'est pas moi

  • Je note et je propage

Si je ne suis pas en cours d'élection

Si je suis en cours d'élection

  • Je la mets de côté
  • J'envoie mon aptitude et mon ID

Pourquoi pas un problème de ne rien envoyer sinon ?

(je l'adopterai en sortant d'élection)

  • Je sors d'élection
  • Je sors d'élection

Performances

Communication

3N messages par élection

Durée d'une élection

~3NT pour T la durée de transit max

Chang et Roberts

Pseudocode

Variables

self

entier, constant

mon numéro de processus

inElection

booléen, init false

ssi une élection est en cours

élu

entier

id du processus élu

apt_self

entier

mon aptitude

apt_pending

entier, init ⊥

aptitude mise de côté

Pseudocode

suivant

entier, constant

numéro du suivant dans l'anneau

Remarques

Plus besoin de stocker les aptitudes de tous les autres.

Plus besoin de dépendre de T.

Tous les envois se feront à suivant.

Démarrer une élection

Écouter infiniment les événements suivants :

Demande de changement d'aptitude à new_apt

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

Si inElection

    apt_pending ← new_apt

Sinon

    apt_self ← new_apt

    Démarrer une élection

Demande de changement d'aptitude à new_apt

élu ← i

Si élu != self

    Envoi de résultat {i}

Sortir d'élection

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

Pseudocode

Envoi d'une annonce {self, apt_self}

inElection ← true

Démarrer une élection

inElection ← false

Si apt_pending ≠ ⊥ et apt_pending ≠ apt_self

    apt_self ← apt_pending

    Démarrer une élection

apt_pending ← ⊥

Sortir d'élection

Pseudocode

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

    Si pas inElection

        Démarrer une élection

Sinon, si i == self

    Envoi de résultat {i}

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 1
  • D, avec aptitude initiale de 1
  • E, avec aptitude initiale de 7

 

Une première élection a déjà eu lieu : E est l'élu.

Les événements suivants ont lieu

  • T=1 : l'aptitude de C devient 8
  • T=1 : l'aptitude de D devient 2

A

B

E

C

D

Exercice 1 - Solution

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

  • Pensez bien à 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