INTRODUCTION Enpc 1

Systèmes distribuésC. Delporte-Gallet (ESIEE-IGM)(cd@liafa.jussieu.fr)

H. Fauconnier (LIAFA Université Paris 7)(hf@liafa.jussieu.fr)

INTRODUCTION Enpc 2

Plan du cours:1. Introduction générale2. Réseaux

Principes généraux, TCP-IP, mise en œuvre3. Algorithmique distribuée

Horloges logiques, snapshots, état global, cohérence, transactions4. Introduction au calcul parallèle

PVM, mise en œuvre5. Applications distribuées et services

OMG Corba6. Tolérance aux pannes

Types de défaillances, problèmes d’accord7. Grande échelle

P2P, grilles de calcul

INTRODUCTION Enpc 3

Introduction Diversité des systèmes distribués:

Quelques exemples Systèmes embarqués: ex avionique aérospatiale

Coopération faible Fortement « synchrone » Tolérance aux pannes (safety critical) Durée de vie Pas de problème de confidentailité

Client(s)/serveur(s) Modèle assez général ( ≠ pair à pair) Généralement asynchrone Des réseaux locaux au réseaux de grande taille Continuité du service: réplication

(assurer la cohérence!) Problème de sécurité et de confidentialité

INTRODUCTION Enpc 4

Diversité… suite Système de réservation et base de données

distribuées: répartition Assurer la concurrence : cohérence des données,

transaction Tolérance aux pannes par réplication Nombreux sites Autres propriétés: sécurité (confidentialité) et équité

Pair à pair: (kazaa, gnutella, emule…) Partage et répartition de données Recherche des données (ex DHT) Pas de problème de cohérence (?) Plusieurs millions de sites Confidentialité (?)

INTRODUCTION Enpc 5

Diversité… Grille de calcul

Calculs parallèles Efficacité, algorithmique Plusieurs centaines de milliers de sites

Le web comme système à image unique Stockage réparti Puissance de calcul arbitrairement grande

INTRODUCTION Enpc 6

Distribués…Quelques critères: Nombre de sites et répartition

Dizaine pour avionique Plusieurs millions P2P

Mémoire partagée ou communication par messages Partage de bus TCP sur le web

Communication Fiabilité Connecté (TCP) ou non (UDP) Synchrone / asynchrone

(ici synchrone = il existe une borne connue sur les délais de communication)

Point à point ou diffusion Graphe de communication (routage) …

INTRODUCTION Enpc 7

Critères… Processeurs synchrones ou asynchrones, horloges globales ou

locales (ici synchrone = le temps pour effectuer un pas de calcul est connu) Exemple:

calcul parallèle : à chaque top tous les processeurs font un pas de calcul, les échanges se font pas partage de la mémoire: PRAM. Problème de la gestion des conflits d’accès

Tolérances aux pannes: Quel type de défaillances?

Processeurs / communication La redondance

Active Passive

Sécurité (confidentialité) Cryptographie

…

INTRODUCTION Enpc 8

Le cours: objectifs La réalité de base: le réseau Calculs parallèles: comment

implémenter des algorithmes parallèles (exemple PRAM) sur des réseaux de processeurs -> PVM

Définir des standards et des classes d’applications distribuées (exemples client/serveur, modèles de la répartition) -> OMG Corba

INTRODUCTION Enpc 9

Le cours: objectifs Algorithmes:

Spécificité de l’algorithmique distribuée

INTRODUCTION Enpc 10

Algorithmique Une algorithmique « différente »

Parallélisme: répartir les calculs localement -> d’autres algorithmes

Distribué: état local accessible, état global du système difficile (ou impossible) à obtenir

Tolérance aux pannes: types de défaillances. Problèmes d’accords.

INTRODUCTION Enpc 11

Deux exemples…

INTRODUCTION Enpc 12

Terminaison distribuée Chaque employé est dans un bureau:

Un téléphone Une pile de dossiers à traiter

Il peut (de façon imprévisible) Traiter des dossiers et peut être amené à

donner du travail aux autres Recevoir du travail à faire des autres Il sait s’il a fini (localement) son travail (mais

attention même dans ce cas il peut encore recevoir du travail)

INTRODUCTION Enpc 13

Terminaison distribuéeObjectif:

au lieu d’appliquer les 35 heures, les employés peuvent rentrer chez eux si tout le travail est terminé.

Solution(s)?

INTRODUCTION Enpc 14

Chaque employéFait de façon non déterministe:

*[ ¬fini -> travail□ ¬fini -> envoyer message pour donner du travail □ ¬fini -> fini = true□ reçu message -> fini = false] Terminaison locale: finiTerminaison distribuée: pour tout processus p finip

INTRODUCTION Enpc 15

Terminaison distribuée

Tout le travail est terminé= Terminaison distribuée (≠ Terminaison locale)

La solution ne doit pas modifier le déroulement normal du travail

La solution doit assurer1. Sûreté: si l’algorithme dit que la terminaison

distribuée est atteinte, c’est vrai!2. Vivacité: si à un instant donné la terminaison

distribuée est vraie, l’algorithme le détectera (peut-être plus tard).

INTRODUCTION Enpc 16

Remarques : La terminaison distribuée est la

conjonction des terminaisons locales La terminaison distribuée est une

propriété stable. Si TD est vraie à l’instant t, TD sera

vraie pour tout t’>t(condition du problème)(importance du téléphone!)

INTRODUCTION Enpc 17

Terminaison distribuée Une solution:

Si quelqu’un a terminé localement, il lance un parcours de jeton v1 (consultation séquentielle de tout le monde) en demandant si on a terminé

Quand v1 arrive chez moi, je garde le jeton jusqu’à ce que j’ai terminé localement

Si l’initiateur du jeton reçoit v1, il lance un parcours de jeton v2,

Quand v2 arrive chez moi, si j’ai terminé localement ET je n’ai rien fait depuis v1 alors je transmets le jeton au suivant

Si l’initiateur reçoit v2, la terminaison distribuée est atteinte.

INTRODUCTION Enpc 18

Principe Soit Up l’instant où v1 arrive en p et Dp

l’instant où v2 arrive en p. On a: Terminaison locale de p entre Up et Dp

Comme v1 visite tous les sites et v2 commence après la fin de v1, si i est l’initiateur, on a: Terminaison locale de tous les p entre Di et Dp

=> en Di terminaison locale de tous les p et donc terminaison distribuée en Di

La terminaison distribuée est stable donc pour tout t>Di on a encore la terminaison distribuée

Sûrete

INTRODUCTION Enpc 19

Principe… La vivacité: Supposons que la terminaison distribuée

soit réalisée: Soit p le dernier processus ayant atteint la

terminaison locale, les jetons v1 et v2 qu’il lance lui reviendront et la terminaison distribuée est bien détectée

(on peut bien sûr améliorer cet « algorithme » en gérant mieux les jetons, on peut généraliser à des « vagues » (consultation de tous et on sait quand tout le monde a été consulté))…

INTRODUCTION Enpc 20

Deuxième exemple… Accord byzantin:

Armée byzantine: Généraux traîtres et généraux honnêtes Un traître peut faire n’importe quoi

(adversaire) Un général honnête respecte son code

Communication synchrone par messages Un général en chef donne un ordre

(attaque ou repli stratégique)

INTRODUCTION Enpc 21

Accord byzantin Assurer que tous les généraux honnêtes

prennent la même décision et que cette décision est l’ordre donné par le général en chef (si ce dernier est honnête!)

Décision irrévocable telle que: Accord: si p et q sont honnêtes p et q ne

peuvent décider différemment Terminaison: si p est honnête il décidera (une

seule fois) Validité: si le général en chef est honnête, la

seule décision possible est son ordre

INTRODUCTION Enpc 22

Exemple: 4 généraux dont au plus un traître: Ronde 1: le général en chef envoie à tous

son ordre. Ronde 2: les autres échangent les valeurs

reçues en ronde 1 (chaque général (honnête) a 3 valeurs: celle

qu’il s’est envoyé lui-même (= celle qu’il a reçu en ronde 1 et la valeur de chacun des deux autres)

Choisir la valeur majoritaire

INTRODUCTION Enpc 23

Suite Si le général en chef est honnête:

À la fin de la ronde 1, tous les généraux ont son ordre v,

Dans la ronde 2 au plus un général est un traître: Tous généraux honnêtes récupèrent au

moins 2 fois v et au plus une fois une valeur différente

Décision v!

INTRODUCTION Enpc 24

Fin Si le général en chef est un traître,

en ronde 2 il n’y a plus que des généraux honnêtes!

À la fin de la ronde 2 ils ont tous les mêmes valeurs ce qui assure l’accord!

Généralisation?

INTRODUCTION Enpc 25

Et s’il n’y a que trois généraux dont 2 sont honnêtes?

A B: 1

C :1

A :0 B :0

C

A 0 B

C 1

Décision 1 Décision 0 Décision ?

Intuition…