Introduction

Système réparti: Ensemble interconnecté d’entités autonomes qui communiquent via un médium de
communication.
Caractérisation: Non Sequentiel, Non centralisé et Non déterministe.
Problèmes Classique: Consensus, Ordonnancement des Tâches, Synchronisation d’Horloge, Exclusion
Mutuelle, Détéction de la Terminaison, Résistance aux Pannes, Election, Obtention de l’Etat du Systeme...
Critères d’Evaluation: Compléxité en Messages et Complexité en Temps.
Topologies d’un Graphe: (Structure) Anneau, Etoile, Graphe Complet, Hypercube et Arbre.
Paramêtres d’un Graphe: Sommet, Arêtes, Diamètre et Degré.
Modèles de Fautes: Fautes Logicielles, Fautes Matérielles ou Piratage.
Composants Impactés: Processus, Calculateurs ou Canaux de Communication.
Classification des Fautes:
— Faute Franche : arrêt définitif du composant, qui ne répond plus ou ne transmet plus.
— Faute d’Omission : un résultat ou un message n’est transitoirement pas délivré.
— Faute Temporelle : un résultat ou un message est délivré trop tard ou trop tôt.
— Faute byzantine : inclut tous les types de fautes, y compris le fait de délivrer un message erroné.
Modèles Temporels:
— Système Synchrone : Modèle Délais/écarts Bornés Connus (DBC) - Détéction Parfaite de Faute.
— Système Partiellement Synchrone : Modèle Délais/écarts Bornés Inconnus (DBI).
— Système Asynchrone : Modèle Délais/écarts Non Bornés (DNB).
Consensus:
— Terminaison : Tout processus correct finit par décider.
— Accord : Deux processus ne peuvent décider différemment.
— Intégrité : Un processus décide au plus une fois.
— Validité : si v est la valeur décidée, alors v est une des vi.

MPI
MPI (Message Passing Interface): Une API standard permettant de faire communiquer par messages
des processus distants sur un ensemble de machines hétérogènes ne partageant pas de mémoire pour des
applicatons écrites en C, C++ ou Fortran.
Communication MPI: Fiables, FIFO et Collectives.
Primitives de Bases:
— Bibliothèque : #include<mpi.h>
— Initialisation : int MPI_Init(int* argc, char*** argv) ;
— Finalisation : int MPI_Finalize() ;
— Types de Données : MPI_CHAR, MPI_INT, MPI_FLOAT, MPI_DOUBLE...
— Communicateur : MPI_COMM_WORLD.
— Nombre de Processus : int MPI_Comm_size(MPI_Comm c, int *size) ;
— Numero de Processus : int MPI_Comm_rank(MPI_Comm c, int *rank) ;
— Status (Obtenir des Info sur un Message) : Valeur du TAG -> status.MPI_TAG, Identité
Emetteur -> status.MPI_SOURCE.
— Emission Bloquante (Asynchrone) : int MPI_Send(void *buf, int count, MPI_Datatype d,
int dest, int tag, MPI_Comm c) ;
— Reception Bloquante (Asynchrone) : int MPI_Recv(void *buf, int count, MPI_Datatype d,
int src, int tag, MPI_Comm c, MPI_Status *status) ;
— Emission Bloquantes (Syncrhone) : int MPI_Ssend(void *buf, int count, MPI_Datatype da-
tatype, int dest, int tag, MPI_Comm comm) ;
— Non Bloquante : MPI_Isend, MPI_Irecv et MPI_Issend.
— Jokers : MPI_ANY_Source, MPI_ANY_TAG.

1
 — Tester le Buffer (Bloquante) : int MPI_Probe(int src, int tag, MPI_Comm m, MPI_Status
*status) ;
— Tester le Buffer (Non-Bloquante) : int MPI_Iprobe(int src, int tag, MPI_Comm m, int *flag,
MPI_Status *status) ;
flag : retourne 0 s’il n’y a pas de message sinon 1.
— Diffusion : int MPI_Bcast(void *buffer, int count, MPI_Datatype d, int root, MPI_Comm c) ;
— Multithread : int MPI_Init_thread(int *argc, char ***argv, int required, int *provided) ;

Horloge Logique
Horloge Logique: Ordonne les événements dans un système distribué sans nécessiter une synchronisation
globale des horloges physiques.
Causalité: e → e’ ⇒ C(e) < C(e’)
Dépendence Causale: send(m) → send(m’) et dest(m) = dest(m’) ⇒ receive(m) → receive(m’)
Délivrance Causale: send(m) → send(m’) et dest(m) = dest(m’) ⇒ delivre(m) → delivre(m’)
Besoin de l’Application:
— Consistance simple ? Horloge Scalaire : Ordre cohérent, mais peut varier entre processus.
— Consistance forte ? Horloge Vectorielle : Même ordre d’opérations pour tous les processus.
— Ordre causal des messages ? Horloge Matricielle : assure la logique des interactions.

Horloge Scalaire (Lamport): Attribue un numéro d’horloge à chaque événement.

— Evenement Local ou d’Envoie : Ci = Ci + d
— Evenement de Reception : Ci = max(Ci , Cmsg ) et Ci = Ci + d

Horloge Vectorielle: Attribue un vecteur de compteur à chaque événement.

— Evenement Local ou d’Envoie : V Ci [i] = V Ci [i] + 1
— Evenement de Reception : V Ci [x] = max(V Ci [x], m.V C[x]) et V Ci [i] = V Ci [i] + 1

2
Horloge Matricielle: Attribue une matrice de compteur à chaque événement.
— Evenement Local : M Ci [i][i] = M Ci [i][i] + 1
— Evenement d’Envoie : M Ci [i][k] = M Ci [i][k] + 1 et M Ci [i][i] = M Ci [i][i] + 1
— Evenement Reception : M Ci [x][x] = max(M Ci [x][x], m.M C[x][x]) et M Ci [i][i] = M Ci [i][i] + 1

Algorithme à Vagues
Algorithme à Vagues: Diffuse des informations dans un réseau, découvre sa topologie, et rassemble des
données. Chaque nœud communique avec ses voisins, et tous les nœuds participent avant de prendre une
décision.
— Noeud Initiateur : Décide de démarrer l’algorithme.
— Noeud Non-Initiateur : Exécute après avoir reçu un message.
Propriétés:
— Terminaison : Toute exécution est finie.
— Décision : Une décision doit être prise à terme par au moins un processus.
— Dépendance : Une décision est précédée causalement par un événement de chaque processus.
Caractéristiques:
— Symétrie : Symétrique ou Asymetrique (Noeud initiateur et non initiateur ont le même algorithme
ou pas).
— Initialisation du Calcul : Centralisé ou Décentralisé (Algorithme est démarré par exactement un
initiateur ou par plusieurs).
Algorithme Total: Sur un réseau de N nœuds, il y a au moins N-1 échanges de messages.
Exemple d’Algorithme: Soit N (Noeuds), M (Liens) et D (Diamètre).

3
 Exclusion Mutuelle
Exclusion Mutuelle: garantit qu’un seul processus à la fois peut accéder à une ressource partagée, même
dans un système distribué où la communication se fait par messages.
Doit Garantir: Pas d’interblocage et Pas de famine.
Propriétés:
— Sûreté : à tout instant il y a au plus un processus dans la section critique.
— Vivacité : Tout processus qui demande la section critique doit l’obtenir au bout d’un temps fini.
Type d’Algorithme: Centralisé et Réparties.
Algortihme Centralisé: Les processus demandent l’accès à une section critique auprès d’un coordinateur,
qui maintient une file d’attente pour gérer les demandes dans l’ordre.

Algorithme Réparties:
A base de permission : Les processus doivent obtenir des permissions pour accéder à la section
critique. Exemple :
— Lamport.
— Ricart-Agrawala.
— Maekawa (Quorum).
A base de jeton : Seul le processus possédant le jeton peut accéder à la section critique. Exemple :
— Anneau : Martin.
— Graphe Complet : Susuki/Kasami.
— Arbre : Raymond (statique) et Naimi-Trehel (dynamique).

Election du Chef
Election: Désigner un chef dans un ensemble de processus.
Propriétés:
— Sûreté : Le chef doit être unique.
— Vivacité : La désignation doit se faire en un temps fini.
Application: Mise en place d’un contrôle centralise, Recouvrement de défaillance, Consensus, Résolution
de situations de blocage ...
Algorithme:
Topologie Anneau :
— Anneau unidirectionnel asynchrone : Chang-Roberts.
— Anneau unidirectionnel synchrone anonyme : Itai-Rodeh.
— Anneau bidirectionnel asynchrone : Hirschberg-Sinclair.
Topologie quelconque avec hypothèses :
— Diffusion avec identifiants.
— Diffusion anonyme basée sur des candidatures aléatoires.
Election vs Exclusion Mutuelle:
— Élection : Les processus peuvent transférer leur rôle et le nouvel élu est annoncé.
— Exclusion Mutuelle : Les processus se disputent l’accès et l’identité du processus en SC n’a pas
d’importance.

4
 Promela/Spin
Spin: Analyse la logique des systèmes concurrents écrits en Promela, permettant la simulation et la géné-
ration de vérificateurs en C pour tester des propriétés de correction.
Ttpe de Donnees: bit, bool, byte, short, int, mtype, typedef...
Declaration:
— Instruction : Le ; et -> sert de séparateur.
— Condition Bool : est bloquante si la condition est fausse et exécutable si la condition est vraie.
— Processus : proctype Nom_proc( Parametre ) { Instruction }
— Instanciation : init { run Nom_proc( Parametre ) }.
— Assert : indique une erreur si la condition est fausse : assert( Condition )
— Canal : chan canal1 = [ Taille ] of { Type_de_Message }
— Condition : if : : Condition_Bool -> Instruction ; ... else Instruction ; fi
— Boucle : do : : Condition_Bool -> Instruction ; ... od
— Emission : canal ! val / canal ! mtype (val1 , val2 ...)
— Reception : canal ? val / canal ? mtype (val1 , val2 ...)

Détection Répartie de la Terminaison

Détection de Terminaison: Déterminer quand un ensemble de processus a terminé leur exécution.
Propriétés:
— Sûreté : Détection si un processus la détecte.
— Vivacité : Détection garantie si la terminaison est réelle.
Problème: Construction d’une couche de contrôle pour détecter la terminaison d’une application répartie.
Conditions de Terminaison:
— Modèle à Communication Instantanée : Tous les processus sont inactifs.
— Modèle Atomique : Tous les canaux de communication sont vides.
États et Messages:
— États : Actif (action interne ou émission possible) et Inactif (absence d’action).
— Messages : Applicatif et Contrôle pour la détection de terminaison.
Algorithme:
— Anneau logique avec jeton : Misra.
Modèle à communication instantanée :
— Anneau logique avec contrôles : Rana.
— Anneau logique avec jeton coloré : Dijkstra.
Modèle atomique :
— Algorithme des Quatre Compteurs : Mattern.

Etat Global
Etat Global: Capture de l’état d’un système réparti (Cohérent) à un moment donné, comprenant les
états de tous les processus et canaux de communication.
Coupure Cohérente:
— Si un événement d’émission est inclus dans la coupure, alors soit l’événement de réception corres-
pondant est également inclus dans la coupure, soit il est postérieur à la coupure dans le temps.
— Si un événement de réception est inclus dans la coupure alors son événement d’émission l’est aussi.
Propriétés: Terminaison, Complétude et Cohérence.
Algorithme: L’algorithme de Chandy et Lamport (Caneaux FIFO).
Algorithme Total: un algorithme qui assure trois propriétés fondamentales :
— Décision : Il doit produire une réponse claire et précise en fonction de l’entrée reçue.
— Terminaison : Il doit produire une réponse claire et précise en fonction de l’entrée reçue.
— Dépendance : Son exécution ne doit dépendre que de l’entrée fournie.