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

Entrée en élection

apt=15

apt=3

B

apt=9

3

Entrée en élection

9

15

A

B

C

3

A

B

C

3

9

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 !

Bully Algorithm

Performance

Communication

O(N^2) messages par élection

Durée d'une élection

3T

Bully Algorithm

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

é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

Demander une élection

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

Retourner élu

Demande d'élection de la couche applicative

Si inElection

    Refuser la demande

Sinon

    Démarrer l'élection

Pseudocode

Timeout

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

inElection ← false

Pseudocode

Réception de l'aptitude apt_i de i

Si pas inElection

    Démarrer l'élection

apts[i] ← apt_i

Démarrer l'élection

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

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

É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

Retourner élu

Demande de l'élu par la couche applicative

Exécuter entrer en élection

Si inElection

    Refuser la demande

Sinon

    Envoi de apt_self à tous les autres processus

    Envoi de apt_self à la routine Collecteur

    Attente 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

Boucle sur l'attente de réception de apt_i par 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

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 :

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)

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