SDR

Diffusion

Olivier Lemer

Élections - Introduction

Élections ?

Le problème de l'élection

Étant donné un groupe de processus.

Chacun a une aptitude, pas nécessairement statique.

On veut élire celui qui a la meilleure aptitude.

Par exemple :

  • Algorithme à jeton : régénérer un jeton après perte
  • Architecture manager/worker : désigner un nouveau manager
  • Répartition de charge : sélectionner le serveur le moins chargé

Propriétés souhaitées

  • Sureté : un seul processus ne peut être élu
  • Progrès : il doit y avoir un élu un jour
  • Validité : l'élu doit être le participant correct à la plus grande aptitude
  • Résilience :
    • Un processus en panne ne doit pas être élu, même s'il redémarre.
    • Si le réseau est scindé en deux, un élu doit exister par partition.

Différence avec Mutex

Mutex

Élection

Essaie d'être équitable

Partage l'accès à une section

Tout demandeur sera accepté

Bloquant si SC est prise

Choisit la meilleure aptitude

Partage le droit au titre d'élu

Un demandeur peut ne jamais être élu

Non-bloquant si un autre est élu

Là où la Mutex assure que tout le monde aura droit à son moment,

l'élection sert uniquement à décider à qui attribuer un titre spécial d'élu.

Rappel

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 synchrone : délai d'envoi de T maximum

Algorithme du Bully

a.k.a. un algorithme naïf

Bully Algorithm

Idée

"tout le monde doit tout savoir"

J'envoie mon aptitude à tout le monde.

Je reçois l'aptitude de tout le monde.

Le plus fort gagne.

Une élection commence

Deux événements

Je broadcast mon aptitude.

J'attends 2T pour tout recevoir.

Je détermine l'élu.

Réception d'une aptitude

Si je ne suis pas déjà en élection,

    j'entre en élection.

Si une élection est en cours quand une nouvelle est demandée, elle est différée à la fin de celle en cours.

Bully Algorithm

Exemple

B

A

3

apt=15

apt=3

C

apt=9

3

A

B

C

3

Bully Algorithm

Entrée en élection

9

A

B

C

3

9

Entrée en élection

15

A

B

C

3

15

A

B

C

3

9

A

B

C

3

9

15

A

B

C

3

9

15

A

B

C

3

9

15

A est élu !

A est élu !

A est élu !

Problème ?

Problème

B

A

apt=15

apt=3

C

apt=9

Bully Algorithm

Entrée en élection

Entrée en élection

3

3

A

B

C

3

9

A

B

C

3

9

A

B

C

3

9

A

B

C

3

9

15

A

B

C

3

9

15

A

B

C

3

9

15

15

A

B

C

3

15

B est élu !

A est élu !

A est élu !

17

17

Nouvelle

aptitude : 17

A

B

C

17

9

15

Solution : Attendre au moins 1T avant toute nouvelle élection.

Performance

Communication

O(N^2) messages par élection

Durée d'une élection

Jusqu'à 4T

Bully Algorithm

(1T d'attente, 2T de timeout, 1T de transit)

Algorithme du Bully

Pseudocode

Pseudocode

Variables

self

entier, constant

mon numéro de processus

inElection

booléen, init false

ssi une élection est en cours

apt_self

entier

mon aptitude

n

entier, constant

nombre de processus

apts

tableau d'entiers

aptitudes de tous les processus

T

entier, constant

durée maximale d'une transmission

isReqPending

booléen, init false

ssi une élection est en attente

élu

entier

id du processus élu

Écouter infiniment les événements suivants :

Demande d'élection par la couche applicative

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

Demande de changement d'aptitude à new_apt

Réception de l'aptitude apt_i de i

Timeout

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

Initialisation

Pseudocode

Demande de changement d'aptitude à new_apt

apt_self ← new_apt

Attendre pendant 1T

Démarrer une élection

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

Retourner elu

Demande d'élection de la couche applicative

Attendre pendant 1T

Démarrer une élection

Pseudocode

Pseudocode

Démarrer une élection

Si inElection

    isReqPending ← true

Sinon

    inElection ← true

    apts[j] ← -inf pour tout j

    apts[self] ← apt_self

    Envoi de apt_self à tous les autres processus

    Lancer un timer de 2T

Réception de l'aptitude apt_i de i

Si pas inElection

    Démarrer une élection

apts[i] ← apt_i

Pseudocode

Timeout

élu ← i tel que apts[i] est le premier maximum de apts.

inElection ← false

Si isReqPending

    isReqPending ← false

    Attendre pendant 1T

    Démarrer une élection

Algorithme du Bully

Pseudocode++ (avec deux routines)

Pseudocode à 2 routines

Diffuseur

Collecteur

Permet de tirer profit de la concurrence.

Responsable de déclencher les élections et communiquer avec l'application.

Responsable de collecter les aptitudes.

Variables partagées

self

entier, constant

mon numéro de processus

n

entier, constant

nombre de processus

T

entier, constant

durée maximale d'une transmission

Pseudocode à 2 routines

Pseudocode à 2 routines

Routine 1 - Diffuseur

Écouter infiniment les événements suivants :

Demande d'entrée en élection

Demande de changement d'aptitude à new_apt

Demande de l'élu par la couche applicative

Initialisation

Variables de la routine 1

élu

entier

id du processus élu

apts

tableau d'entiers

aptitudes de tous les processus

apt_self

entier, constant

mon aptitude

apt_self ← new_apt

Exécuter entrer en élection

Demande de changement d'aptitude à new_apt

Demande d'entrée en élection

Pseudocode à 2 routines

Routine 1 - Diffuseur

Demande de l'élu par la couche applicative

Exécuter entrer en élection

Retourner elu

Attente bloquante durant 1T

Envoi de apt_self à tous les autres processus

Envoi de apt_self à la routine Collecteur

Attente bloquante durant 2T

Obtention de apts de la routine Collecteur

élu ← i tel que apts[i] est le premier maximum de apts

Entrer en élection

Pseudocode à 2 routines

Routine 1 - Diffuseur

Boucle sur l'attente de réception de apt_i de la part de i

Initialisation

apts ← Tableau de taille n initialisé à -inf

apts[i] ← apt_i

Si i != self

    Demander une élection à Diffuseur

Boucle sur l'attente de

    Réception de apt_i de i

        apts[i] ← apt_i

    Demande de apts par Diffuseur

        Retourner apts

        Sortir de cette boucle

Pseudocode à 2 routines

Routine 2 - Collecteur

Algorithme du Bully

En cas de panne ?

Gestion des pannes

Un processus ne tombe jamais en panne pendant l'envoi de messages en batch.

Seul danger : Pendant une élection qu'il allait gagner.

On suppose alors un détecteur de panne chez les autres, surveillant l'élu :

Si je détecte une panne de l'élu, je demande une nouvelle élection.

Supposition

Soit il envoie tout, soit il n'envoie rien.

Gestion de telles pannes

Détecteur parfait ou un jour ?

Un jour suffit : si suspicion annulée, relancer une élection.

(Il existe des protocoles de communication qui garantissent cela)

En cas de faux positif, le même élu sera à nouveau choisit.

Exercice

Algorithme du Bully

Exercice

On suppose :

  • 2s de transit pour chaque message.
  • Si une demande d'élection est rejetée, le processus réessaie une fois l'élection courante terminée.
  • Les pannes ne sont pas détectées.

 

Trois processus

  • A, avec aptitude initiale de 15
  • B, avec aptitude initiale de 15
  • C, avec aptitude initiale de 20

 

 

Les événements suivants ont lieu

  • T=1 : A demande une élection
  • T=2 : l'aptitude de B devient 25
  • T=2 : B demande une élection
  • T=5 : l'aptitude de C devient 10
  • T=5 : C demande une élection
  • T=7 : B tombe en panne

Algorithme du Bully

Exercice - Solution