Evaluation des algorithmes distribués Analyse, complexité, méthodes (coll. Informatique)

Publié par

Ce livre propose un tour d'horizon de l'état de la complexité des algorithmes et de ses méthodes. Il présente l'analyse de la quasi-totalité des algorithmes fondamentaux du domaine. Les douze chapitres sont assortis de nombreux exercices corrigés et de notes bibliographiques.
Notations et définitions Partie 1. Concepts fondamentaux 1. Systèmes distribués et algorithmes distribués 2. Complexité des algorithmes distribués Partie 2. Les réseaux avec identités 3. L'élection sur les anneaux avec identités 4. L'élection dans les réseaux complets 5. Élection et arbres de recouvrement dans les réseaux quelconques 6. Analyse d'un algorithme distribué d'exclusion mutuelle 7. Graphes et algorithmes distribués sur les graphes 8. Algorithmes distribués de tri et de sélection Partie 3. Les réseaux anonymes 9. Introduction aux algorithmes probabilistes - application aux anneaux anonymes 10. L'élection sur les anneaux anonymes 11. Protocoles et élection dans les réseaux anonymes 12. Information et complexité distribuées Formulaire - Annexes I. Généralités sur les permutations II. Démonstrations de l'identité harmonique III. Nombre moyen de pics d'une permutation Correction des exercices Bibliographie
Publié le : mercredi 5 février 2014
Lecture(s) : 148
Licence : Tous droits réservés
EAN13 : 9782746234505
Voir plus Voir moins
30 jours d'essai offerts
Ce livre et des milliers d'autres sont disponibles en abonnement pour 9,90€/mois

collection informatique
Evaluation
des algorithmes
distribués
analyse, complexité, méthodes
Christian Lavault
HERMES collection dirigée
par
Ivan Lavallée Évaluation des algorithmes distribués CHE Z LE MÊM E ÉDITEU R (extrait du catalogue)
Michae l GRIFFITHS et Michel VAYSSADE, Architecture des systèmes d'exploitation,
E199 0 (2 édition) .
Habi b ABDULRAB, de Common Lisp à la programmation objet, 1990.
Rober t OGOR et Robert RANNOU, langage ADA et algorithmique, 1990 et 1993 pour
Ela 2 édition revue et corrigée.
Ivan LAVALLÉE, Algorithmique parallèle et distribuée, 1990 .
Jean-Pierr e CHARDON et Dominique BISSEY, Télécommunications d'entreprise —
Etechniques et organisation, 1990 et 199 2 pour la 2 éditio n revue et complétée.
Victor SANDOVAL, Technologie de l'EDI, 1990 .
Xavie r MARSAULT, Compression et cryptage en informatique, 1992 .
Christia n PÉLISSIER, Guide de sécurité des systèmes UNIX, 1993 .
Jean-Loui s JACQUEMIN, Informatique parallèle et systèmes multiprocesseurs, 1993 .
Michel ADIBA et Christine COLLET, Objets et bases de données — le SGBDÛ2, 1993 .
Rad u HORAUD et Olivier MONGA, Vision par ordinateur — outils fondamentaux,
1993.
Richar d LASSAIGNE et Michel de ROUGEMONT, Logique et fondements de l'informa­
tique — logique du premier ordre, calculabilité et lambda-calcul, 1993 .
Philipp e COIFFET et Grigore BURDEA, La réalité virtuelle, 1993.
Lauren t TOUTAIN, Technique des réseaux locaux sous Unix — des protocoles à
l'interconnexion, 1994 .
EPatric e BOURSIER et Pierre-Antoine TAUFOUR, La technologie multimédia, 2 édi­
tion revue et augmentée, 1994.
Christia n VAN HOUCKE, Le multimédia en entreprise, 1994.
Gérar d DUPOIRIER, Technologie de la GED — l'édition électronique, 1994 .
Jean-Françoi s JODOUIN, Réseaux neuromimétiques — modèles et applications,
1994 . s JODOUIN, Les réseaux de neurones — principes et définitions, 1994.
Victor SANDOVAL, SGML — un outil pour la gestion électronique de documents,
1994 .
Gu y JACOB, Le reengineering de l'entreprise — l'entreprise reconfigurée, 1994.
Daniel CALI et Gabriel ZANY, Technologie de l'interconnexion de réseaux — métho­
dologies, marchés et évolutions, 1994.
Jea n PELLAUMAIL, Pierre BOYER et Patrice LEGUESDRON, Réseaux ATM et P-simu-
lation, 1994.
eChristia n PÉLISSIER, UNIX— Utilisation, Administration système et réseau, 2 édi­
tion revue et augmentée, 1995.
Victor SANDOVAL, Les autoroutes de l'information, 1995 .
George s ZÉNATTI, CD-Rom et Vidéo-CD, 1995.
Philippe Coiffet, Mondes imaginaires — les arcanes de la réalité virtuelle, 1995 . Christian Lavault
Évaluation
des algorithmes
distribués
analyse, complexité, méthodes
HERME S Le Code de la propriété intellectuelle n'autorisant, aux termes de l'article L. 122-5, d'une
part, que les "copies ou reproductions strictement réservées à l'usage privé du copiste et non
destinées à une utilisation collective" et, d'autre part, que les analyses et les courtes citations
dans un but d'exemple et d'illustration, "toute représentation ou reproduction intégrale, ou
partielle, faite sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4).
Cette représentation ou reproduction, par quelque procédé que ce soit, constituerait donc
une contrefaçon sanctionnée par les articles L. 335-2 et suivants du Code de la propriété
intellectuelle.
© Hermès, Paris, 1995
Editions Hermès
14, rue Lantiez
7501 7 Paris
ISB N 2-86601-460-X
ISS N 0993-5037 Table des matières
Avant-propos 13
Notations et définitions7
PREMIÈR E PARTIE. Concepts fondamentaux
Chapitre I. Systèmes distribués et algorithmes distribués 2
1. Le parallèle et le distribué 2
2. Le modèle4
3. La notion d'algorithme distribué
4. Hypothèses sur les propriétés du réseau 31
5. Systèmes et algorithmes synchrones
5.1. Synchronicité
5.2. Synchroniseurs6
6. Synchronisation logique7
6.1n virtuelle
6.2 Algorithme distribué dirigé par réception de messages 38
7. Discussion du modèle 40
8. Notes bibliographiques3
Chapitre II. Complexité des algorithmes distribués 4
1. Les différents modèles
2. Hypothèses et définitions8
3. Mesures de complexité en communication 52
4.s deé en temps3
4.1. Complexité en temps idéal3
4.2.é ens unitaire4
4.3.é en temps par chaîne5
5. Complexité en moyenne6
6.é amortie 58
7.é dépendante des délais9
60 8. Optimalité
9. Commentaires sur ces mesures de complexité 62
10. Un exemple : la diffusion5
10.1. Algorithme de diffusion en profondeur et en largeur5 6 Evaluation des algorithmes distribués
10.2. Algorithme de diffusion (PI) 67
10.3.e den (P1R)6
11. Exercices
12. Notes bibliographiques8
DEUXIÈME PARTIE. Les réseaux avec identités
Chapitre III. L'élection sur les anneaux avec identités 73
1. Introduction 74
2. Deux algorithmes distribués asynchrones d'élection sur un anneau4
2.1. L'algorithme de Chang-Roberts (CR) :
l'élection sur un anneau unidirectionnel6
2.1.1. Description de l'algorithme (CR) 77
2.1.2. Analyse dee (CR)9
2.2. L'algorithme de Franklin : l'élection sur un anneau bidirectionnel 90
2.2.1. Description de l'algorithme 91
2.2.2. Analyse dee3
3. Borne inférieure en Çl(n logn) sur les anneaux asynchrones 95
4. Un algorithme d'élection optimal sur les anneaux synchrones 10
4.1 . L'algorithme de Bodlaender-Tel 10
4.2. Analyse de l'algorithme
5. Une conclusion provisoire : l'élection sur les anneaux8
6. Exercices 109
7. Notes bibliographiques 112
Chapitre IV. L'élection dans les réseaux complets 115
1. Introduction
2. Un algorithme d'élection asynchrone dans un réseau complet6
2.1. L'algorithme Élection(P)>
2.2. Analyse de l'algorithme Élection(P)
3. Borne inférieure de complexité des algorithmes globaux 120
3.1. Définitions et propriétés 121
3.2. Calcul de la borne inférieure £l(n logn)3
4. Un algorithme d'élection synchrone optimal en Q(n)6
4.1 . L'algorithme de Chan-Chin
4.2. Analyse de l'algorithme8
4.2.1. Complexité en messages dans le pire des cas 12
4.2.2.é en temps de l'algorithme
4.2.3.é moyenne en messages
4.2.4. Optimalité ene 129
5. Un algorithme d'élection asynchrone optimal
avec le sens de la direction 130
5.1. L'algorithme de Loui, Matsushita et West (LMW) 131
5.2. Analyse d e l'algorithme (LMW)2
6. Exercices5
7. Notes bibliographiques6 Table des matières 7
Chapitre V. Élection et arbres de recouvrement
dans les réseaux quelconques 139
1. Introduction et généralités
1.1. Les problèmes 140
1.2. La complexité de ces problèmes2
2. Un algorithme asynchrone d'élection optimal en temps 143
2.1. L'algorithme de la phase4
2.2. Complexité de l'algorithme de la phase5
3. Optimalité en messages de la classe (ARM)6
23.1. Borne inférieure en £î(n ) dans un réseau complet7
3.2. Bornee en Ci(m + n logn) dans un réseau quelconque 150
3.3. L'algorithme optimal en messages de Gallager, Humblet et Spira1
3.3.1. Présentation de l'algorithme (GHS) 153
3.3.2. Complexité dee
4. Algorithmes d'élection et d'arbre de recouvrement
4.1.s de parcours
4.2. L'algorithme modulaire de Korach, Kutten et Moran9
4.2.1. Définitions et description
de l'algorithme général modulaire (KKM) 160
4.2.2. Complexité en messages
dee général d'élection (KKM)4
4.2.3. Application aux réseaux quelconques7
5. Construction d'un arbre de recouvrement de diamètre minimal 17
5.1. Le problème (ARDM) 17
5.2. L'algorithme de Bui et Butelle1
5.2.1. Présentation de l'algorithme
5.2.2. Complexité dee5
6. Exercices8
7. Notes bibliographiques 180
Chapitre VI. Analyse d'un algorithme distribué d'exclusion mutuelle 183
1. Introduction et hypothèses
2. L'algorithme de Naïmi-Tréhel4
3. Trois méthodes d'analyse en moyenne7
3.1. Files de priorité, arbres tournois et permutations 18
3.2. Coût moyen de l'inversion de chemin et coût moyen en messages 190
3.2.1. Longueur moyenne d'une branche d'un arbre tournoi 191
3.2.2. Résolution directe d'une équation récurrente simple2
3.2.3. Premiers moments et fonctions génératrices de probabilité
4. Complexité en messages dans le pire des cas 196
5.é en temps dans le pire des cas
6. Exercices 199
7. Notes bibliographiques8 Evaluation des algorithmes distribués
Chapitre VII. Graphes et algorithmes distribués sur les graphes 201
1. Introduction 20
2. Le modèle, hypothèses et notations2
3. Réseau synchrone en arbre3
3.1. Description de l'algorithme fondamental 20
3.2. Propriétés fondamentales de l'algorithme5
3.3. Détermination d'un centre d'un arbre6
3.3.1. Propriétéss
3.3.2. L'algorithme (CA)7
3.4. Analyse de la complexité de l'algorithme (CA)8
3.5. Détermination d'une médiane d'un arbre9
3.5.1. Propriétés fondamentales 20
3.5.2. L'algorithme (MA) 211
3.6. Analyse de la complexité de l'algorithme (MA) 21
3.7. Bornes inférieures et optimalité2
4. Réseaux synchrones quelconques4
4.1. Description des algorithmes fondamentaux
4.2. Algorithme de détermination des centres (CG)5
4.3. Analyse de la complexité de l'algorithme6
4.4.e den d'une médiane (MG)8
5. Le modèle de réseau asynchrone
6. Propriétés des médianes d'un graphe9
6.1. Généralités
6.2. Caractérisation des médianes d'u n arbre 22
6.3.n dess d'u n graphe quelconque4
7. Exercices 22
8. Notes bibliographiques7
Chapitre VIII. Algorithmes distribués de tri et de sélection 22
1. Introduction au problème et définitions9
2. Le tri distribué dynamique 230
2.1. Description de l'algorithme2
2.2. Analyse dee4
2.3. Optimalité dee5
3. Complexité en communication du tri et de la sélection 236
3.1. Retour sur les problèmes de tri et de sélection distribués
3.1.1. Modèle et hypothèses
3.1.2. Le tri et la sélection distribués
3.2. Bornes inférieures d'algorithmes de tri et de sélection distribués 237
3.3 Discussion sur la nature des problèmes de tri et de sélection9
4. Exercices 24
5. Notes bibliographiquesTable des matières 9
TROISIÈM E PARTIE. Les réseaux anonymes
Chapitre IX. Introduction aux algorithmes probabilistes —
application aux anneaux anonymes 245
1. Généralités sur les algorithmes probabilistes
2. Qu'est-ce qu'un algorithme probabiliste ?8
2.1. Les nombres aléatoires 24
2.2. Exemples 251
2.3. Monte-Carlo ou Las Vegas
3. Complexité des algorithmes probabilistes9
4. Algorithmes d'élection anonyme 26
4.1. Terminaison par processus ou par messages3
4.2. Résultats fondamentaux. Théorèmes d'impossibilité4
5. Calculabilité sur les anneaux anonymes6
5.1. Calcul de fonctions simples
5.2. Orientation d'un anneau7
5.3. Complexité distribuée des anneaux anonymes asynchrones 275
6. Exercices 27
7. Notes bibliographiques
Chapitre X. L'élection sur les anneaux anonymes 279
1. L'élection sur un anneau anonyme avec connaissance exacte de l'ordre 27
1.1. Un schéma général d'algorithme d'élection 280
1.1.1. Hypothèses et description du schéma général
1.1.2. Probabilité de terminaison et amélioration du schéma général 281
1.2. L'élection sur un anneau anonyme synchrone3
1.2.1. Un algorithme distribué de Las Vegas Ai4
1.2.2. Uneé de Lass amélioré A\8
1.3. L'élection sur un anneau anonyme asynchrone 29
1.3.1. Un algorithme distribué de Las Vegas A 2
1.3.2. Uneé de Las Vegas amélioré A2' 302
2. L'élection sur un anneau synchrone avec connaissance partielle de l'ordre 30
2.1. Description de l'algorithme A3 30
2.2. Analyse de la complexité de l'algorithme A 3 310
3. Un algorithme d'évaluation de l'ordre d'un anneau anonyme6
4. Exercices 318
6. Notes bibliographiques 32
Chapitre XI. Protocoles et élection dans les réseaux anonymes 321
1. Introduction
2. Retour sur la terminaison anonyme3
3. L'élection dans des réseaux anonymes quelconques 324
3.1. Réseaux anonymes d'ordre inconnu5
3.1.1. L'algorithme Anelect de Afek et Matias6
3.1.2. Analyse de l'algorithme8
3.1.3. Optimalité dee 332
3.2. Réseaux anonymes dont l'ordre est partiellement connu 33
3.2.1. Connaissance d'un minorant de l'ordre du réseau10 Evaluation des algorithmes distribués
3.2.2. Connaissance d'un majorant de l'ordre du réseau 335
3.3. Élection anonyme avec détection de la terminaison7
3.3.1. Un algorithme de Monte-Carlo 33
3.3.2. Une de Las Vegas 340
3.4. L'élection dans les réseaux anonymes complets2
4. Protocoles de communication multipartie3
4.1 . Test d'égalité de deux mots par témoin
4.2. La communication bipartie et multipartie5
5. Exercices 347
6. Notes bibliographiques
Chapitre XII. Information et complexité distribuées 349
1. Introduction : l'information structurelle
2. Connaissance et apprentissage 350
3. La connaissance de l'ordre d'un anneau2
4. Lae dee d'un réseau quelconque 353
4.1. Jeu de devinette et calcul de minimum4
4.2. Jeux dee tous azimuts6
4.2.1. Les jeux de type [*,t,b]7
4.2.2. Les jeux de type [*,*,b] 361
4.2.3. Majorants pour le calcul de minimum anonyme et l'élection 363
5. Sens de la direction dans les réseaux5
5.1. Étiquetage et sens de la direction
5.1.1. Étiquetage local des arêtes
5.1.2. Étiquetage local des sommets et vue locale
5.1.3. Sens de la direction8
5.2. Différents types de sens de la directio n 370
5.2.1. Sens cartographique de lan
5.2.2. Sens de la direction par cordes
5.2.3. Sens dimensionnel de la direction2
5.2.4. Sens de la direction par voisinage3
5.3. Sens de la direction dans diverses topologies4
5.3.1. Propriétés générales
5.3.2. L'anneau 375
5.3.3. Le tore7
5.3.4. L'hypercube
5.3.5. Autres réseaux à degré borné 381
5.3.6. Les graphes planaires6
6. Sens de la direction et élection — de Q(m + n logn) à Q(n) 38
6.1. L'élection sur un anneau orienté gauche/droite
6.1.1. La variante bidirectionnelle de l'algorithme de Chang-Roberts 387
6.1.2. Comportement de l'algorithme (CRB) 390
6.1.3. Tableau récapitulatif
6.2. L'élection dans un réseau complet orienté par cordes2
6.3. L'élection dans un hypercube avec un (SD) dimensionnel5
6.3.1. Description de l'algorithme de Tel
6.3.2. Analyse de la complexité de l'algorithme9
6.3.3. Version probabiliste dee pour un d-hypercube anonyme .... 40
6.4. Application aux réseaux quelconques avec un sens de la direction 403
6.4.1. La construction en profondeur d'un arbre de recouvrement4
6.4.2. La diffusion dans un réseau quelconque avec un sens de la direction ... 405 Table des matières 11
6.4.3. L'élection dans un réseau quelconque avec un sens de la direction 406
6.4.4. Sens de la direction et défaillances dans les réseaux quelconques8
6.4.5. Tableau récapitulatif 40
6.5. Calculabilité et sens de la direction 410
6.6. En guise de conclusion sur le sens de la direction
7. La synchronicité 412
7.1. Influence de la synchronicité sur les anneaux3
7.2.e de laé dans les réseaux quelconques 416
8. Exercices7
9. Notes bibliographiques 42
Formulaire
Annexes
I. Généralités sur les permutations
II. Démonstrations de « l'identité harmonique » 43
IE. Nombre moyen de pics d'une permutation3
Correction des exercices 435
Bibliographie 459
Liste des symboles 47Avant-propos
L'informatique distribuée se développe depuis maintenant vingt-cinq à trente ans. Les
chercheurs ont conçu de bons modèles théoriques et de nombreux algorithmes distribués
existent pour la plupart des problèmes classiques effectivement résolubles, numériques et
non numériques. Cependant, malgré la qualité et la diversité des recherches effectuées, la
croissance (presque) exponentielle des publications, revues, journaux et congrès, les
ouvrages généraux ou synthétiques traitant des algorithmes distribués se comptent par
unités. Ce n'est pas là un phénomène spécifiquement français puisque, à l'exception du
Chandy-Misra, le premier — et excellent — ouvrage en langue anglaise d'introduction aux
algorithmes distribués n'a été publié que l'an dernier par Gerard Tel. Dans une certaine
mesure, les francophones sont plutôt mieux lotis. Grâce à Françoise Andrée, Jean-Pierre
Banâtre, Cornafion (nom collectif), Jean-Michel Hélary, Daniel Herman, Ivan Lavallée,
Michel Raynal, Jean-Pierre Verjus, les ouvrages en français traitant des algorithmes
distribués sont relativement « plus nombreux » — toutes choses étant égales par ailleurs.
Mais « plus nombreux » reste désespérément peu en l'occurrence !
Dans cette province un peu à l'écart de l'informatique traditionnelle, l'étudiant,
l'ingénieur ou le chercheur se trouvent trop souvent réduits à eux-mêmes et, trop souvent
aussi, écartelés entre le credo de deux chapelles irréductibles, celle de la simulation
expérimentale d'un côté et son contre-pouvoir théorético-mathématique de l'autre. Nous
(informaticiens) français, aimons disserter en agitant le hochet du « danger théorique »,
sans doute justement par manque de très bonne recherche théorique et donc en partie par
mauvaise conscience... la sélection par les maths a encore frappé !
Bonnes raisons économiques, politiques, sociales, idéologiques et mandarinales,
l'évaluation mathématique des algorithmes et des systèmes distribués reste en France un
exercice d'école, une manière d'étude rapide offerte « en prime ». Comme si l'on pouvait
isoler l'évaluation des algorithmes (séquentiels ou distribués) de leur conception et l'ériger
en statue, « ténébreuse affaire théorique » sans grand rapport avec la réalité de 14 Evaluation des algorithmes distribués
l'algorithmique Ainsi, on n'apprend toujours pas — ou si peu — à analyser la
complexité des algorithmes dans les universités françaises. Ce beau jouet est offert aux élus
de la sélection et il faut « faire » telle ou telle grande école pour avoir une chance d'évaluer
la complexité en moyenne d'un algorithme : sélection absurde, mauvaise mathématique.
Bref, des gouffres restent à combler. Le présent ouvrage propose un simple tour
d'horizon des méthodes d'analyse et de comparaison théoriques des algorithmes distribués.
Parmi les problèmes-clés, paradigmatiques, de l'algorithmique distribuée, le problème de
l'élection dans les systèmes distribués occupe une place à part. La raison en est bien
naturelle, presque tous les problèmes de fond se posant en algorithmique distribuée, en
particulier la complexité algorithmique et l'analyse des algorithmes, apparaissent dans
l'élection et ce, avec souvent beaucoup d'acuité et de profondeur.
Ce tour d'horizon, dont le prérequis mathématique est celui d'un Deug scientifique ou
d'une classe préparatoire (assorti du formulaire et annexes du livre), s'adresse aux
étudiants de presque tout niveau, aux ingénieurs désirant approfondir ce domaine, aux
enseignants ainsi qu'aux enseignants-chercheurs, aux chercheurs et curieux de toute nature.
Les remarques, commentaires et notes bibliographiques. Parallèlement aux théorèmes,
démonstrations et autres lemmes, le texte est émaillé de remarques et de commentaires qui
tissent une toile faite des rapports réciproques entre les différentes parties et les variétés de
problèmes abordés. Ils pourront sans doute éclairer le lecteur sur la richesse de l'analyse de
la complexité de l'algorithmique distribuée. En fin de chaque chapitre une note
bibliographique est proposée, qui offre un bref historique des recherches et des points
d'entrée dans la bibliographie générale.
Les exercices, le formulaire et les annexes. Chaque chapitre, à l'exception du premier, se
termine par une série d'exercices dont la plupart sont corrigés en fin de livre. Le formulaire
et les annexes, proposent de très nombreuses identités et formules mathématiques ainsi que
quelques techniques utilisées dans les démonstrations et les exercices ; avec les abondantes
notations et définitions initiales, les légitimes exigences du lecteur devraient être satisfaites.
(
> On entend ici « algorithmique » au sens de [BRASSARD, BRATLEY-88, p. xiii] : "In a
nutshell, algorithmes is the systematic study of the fundamental techniques used to design
and analyse efficient algorithms. " Avant-propos 15
Corrections et suggestions. L'auteur saurait infiniment gré au lecteur qui trouve erreur(s)
ou omission(s) (inévitables) de lui en faire part. De manière générale, toute critique ou
suggestion quant au contenu est aussi la bienvenue, tant sur le fond que sur la forme, la
correction des exercices existants ou la proposition de nouveaux exercices, etc. Le plus
simple est de prendre contact par messagerie électronique.
Remerciements. C'est un peu un truisme que d'affirmer combien un tel travail est à divers
égards une œuvre collective. Les nombreux échanges d'idées avec, parmi tant d'autres,
Bernard Mans et Nicola Santoro de Carleton, Friedemann Mattern de Saarbrticken ou
Shmuel Zaks de Technion ont servi de stimulant. Je tiens également à remercier mes amis et
collègues de l'Institut Galilée et du LIPN, Gérard Plateau notamment : ils m'ont fait
l'honneur d'être des leurs, puis ont montré beaucoup de patience durant le premier semestre
1994-95. Mais cet ouvrage doit surtout aux amis qui ont participé, participent et, je
l'espère, participeront encore à nos activités de recherche, les membres de feu l'action
PARADIS de l'Inria. Marc Bui, Franck Butelle et Ivan Lavallée tout particulièrement savent
ce que ce travail leur doit...
Christian Lavault
(mel<*> : lavault@lipn.univ-parisl3.fr)
(*) « messagerie électronique ». Notations et définitions
On trouvera ci-dessous une liste des notations et conventions qui ne sont pas
explicitement définies dans le texte.
1. Pour tout ensemble E fini ou infini, dénombrable ou non, on notera I E l le cardinal
ou la puissance de E.
2. Dans toute la suite, Ig désigne le logarithme de base 2, ln est le logarithme népérien
de base e et log>, le logarithme de base b (b > 0, b *• 1 ), en particulier dans les notations
asymptotiques 0(\ogn), Q(logn) et 0(logn). Ainsi, lg« = 1,44269... ln/i, puisque
1/In2 = 1,44269... La notation log* désigne la fonction « logarithme itéré » : \og*(n)
représente le nombre d'itérations de la fonction lg nécessaires pour obtenir une
(0, (,) 1 (
valeur inférieure ou égale à 1, i.e. Ig («) = n, lg (") = lg* ~ lg(") pour < > 0 et
( 65536!og*(rt) = min{ il lg ''(n) ^ 1 }• La croissance de log*(n) est très lente, pour n < 2 ,
log*(«)<5 .
*
3. [n] représente l'ensemble {1 n) des entiers de 1 à n (dans N ).
4. Pour tout réel x , I x\ est la valeur absolue de x ; la partie entière par défaut de jr est
notée |_jrj et la partie entière par excès de x est notée \x\ On a donc
\_x\ = n <=> n < x < n + 1 et Fx~] = n <=> n - I < x < n.
5. Pour deux réels x et c, x — c signifie que la valeur de x est proche de c.
6. Soit E un ensemble muni d'une relation d'ordre total notée <.
La relation •< sur Ex£ définie par
(a,b) •< ( a J}') si a < a ' ou si a - a' et b < b'
est une relation d'ordre total, appelée ordre lexicographique sur Ex E. On étend
canoniquement la relation d'ordre lexicographique à E". 18 Evaluation des algorithmes distribués
7. n\ - 1 x2x3x ••• x n est la factorielle de n (par convention, 0 ! = 1). Le développement
asymptotique de n! est dans le formulaire II (formule de Stirling).
8. (£ ) = n\/k\(n-k)\ est le coefficient binomial défini ici pour (njc) e N2, avec
(£ ) = 0 si k > n. On note aussi (^) = n~/k\, où, pour tout réel .t et tout entier k > 0 ,
jr = *( * -1 ) ••• (x - k + 1 ) est la « factorielle descendante » de x . On désigne par
xk = x( x + 1) • •• (x + k - 1) la « factorielle montante » de x.
9. Une permutation a = ( o~\ a i ••• an ) d'un ensemble fini £,I £l = n. est une bijection
de £ dans lui-même. Pour simplifier, l'ensemble des permutations de E, le groupe
symétrique de £ à n\ éléments @(£), est souvent noté <2>„ lorsque |f| =n (voir
annexe I).
n
10. On note Hn = £ 1// le nlème nombre harmonique. Pour tout entier r, on note
1=1
n
Hlr) = £ l/(r = £(r), où £(j) = £ fTJ est la fonction zêta de Riemann, définie dans le
1=1 «>i
demi-plan complexe %,s) > 1. En particulier, H™ = £ 1//2 = Ç(2) = x2/6. Le
développement asymptotique de H „ est dans le formulaire II.
11 . Les nombres de Stirling sans signature de première espèce sont notés [£] (voir
annexe I pour certaines propriétés).
12 . Étant donnée une série génératrice ordinaire f,z) = X/n^"'
ou exponentielle J[z ) = ^_fnt"ln\ , son coefficient / „ est noté [zn]fi,z) (voir annexe III).
«20
13. Un 1 -graphe non orienté G sur un ensemble de sommets X est un sous-ensemble de
XxX dont les éléments sont des arêtes. La notation usuelle est G = (X,U), où U <z Xx X est
les sous-ensemble des arêtes de G. Si A" est fini, on note \x\ = net \ U\ = m ; ne t m sont
appelés respectivement l'ordre et la taille du graphe C . Un digraphe est un graphe
orienté. Un graphe value est noté G = (X,U.w) , où Xet U sont définis comme ci-dessus et
la valuation est une fonction w : U -» IR (par exemple) qui, à toute arête u e U, associe
san (ou poids) R<M) (voir [BERGE-73]). Par extension, la longueur w</i) d'un
chemin n = [x,y] dans un graphe value est ainsi sa « longueur valuée », c'est-à-dire son Notations et définitions 19
poids, ou la somme des poids des arêtes qui le constituent. Cette définition, qui revient à
considérer un graphe non value comme un graphe value avec des poids uniformément
égaux à 1, est bien cohérente avec la définition classique.
14 . Les notations utilisées en probabilité, Pr{£}, E[X] et var(X), sont les notations
usuelles respectives de la probabilité d'un événement £, de l'espérance et de la variance
d'une variable aléatoire (v.a.) X (voir le formulaire III).
15 . Les fonctions dont on étudie le comportement asymptotique étant des mesures de
complexité, mesures de coût ou de dénombrement, il s'agit de fonctions arithmétiques à
valeurs positives, i.e. de N dans ]0,+°°[, les notations asymptotiques sont définies sous la
forme suivante :
Soit / et g deux fonctions arithmétiques à valeurs positives.
•Kn) = oig(n)) <=> \\mfin)lg(n) = 0
~g(n ) «• lim fin)/gin) =1 <=> /(/i) = $(«)( 1 + o(l) ) diddt)
= 0OK/i)) <=> ( 3A e ]0,+~[ ) ( 3n o € N ) /i > no => U«) I ^ A | g(/i) I •fitd5
= £20j(,i)) <=> ( 3p. € ]0.+oo[ ) ( 3/iQ e N ) /i > n0 =» l/t") I S /i |g(/i) I •fitf1
= Qigin)) <=> An ) = Oigin)) A. fin) = i«*(/i)) •/Cnd5)
Remarques
\°fin) = O(gin)) se lit « f(n ) égale O de g(n) », ou « fin ) est en O de g(n) » ; on dit
alors que/es t dans l'ordre de grandeur asymptotique majoré de g, ou encore que/
est dominée asymptotiquement par g. De même, fin) = QÇgin)) se lit « /es t en thêta
(0 ) de g » et on dit alors que /es t dans l'ordre de grandeur asymptotique exact de
S-
2° Ces notations sont dues à Bachman (en 1892), Q exceptée. La définition de Cl est
ici celle de Donald Knuth (en 1976) et est habituellement utilisée en informatique.
La définition originale de Q, due à G.H. Hardy et J.E. Littlewood (en 1914), est
différente ; elle est utilisée en mathématiques : fix) = Qgix) ) <=> fix) * o(g(x)).
y Les valeurs absolues dans la définition des notations 0{g{n)) et Q(g(n)) permettent
de borner la valeur absolue du terme d'erreur et d'éviter l'écriture « ± O(gin)) »,
par exemple dans l'expression x2 + x siru = + CKx). 20 Evaluation des algorithmes distribués
Plus généralement, un développement asymptotique en série se note =,
parexemple, e1 = 1 + z/1 ! + z2/2\ + z^/V- +
ou bien 1/<1—z) = 1 + z + z2 + + z4 + •••
O n préfère en général les notation O, Cl et 0 , dans la mesure où o et - ne rendent
pas compte du taux de convergence des limites en question : il est plus facile et plus utile
d'obtenir une propriété « forte », comme fin) =CX«~1/2), qu'une plus faible comme
fin) = o(l) . En fait, la notation o est plus puissante que la notation correspondante O,
puisqu'on a
An) = aigin)) => (fin) = 0(g(n)) )*(fin) n'est pas en Q(g(n) ).
(voir [FROIDEVAUX. GAUDEL, SORIA-90, p. 512] , très complet pour ces définitions et la
manipulation des notations asymptotiques). PREMIÈRE PARTIE
Concepts fondamentaux Chapitre I
Systèmes distribués et algorithmes distribués
Ce chapitre est une introduction rapide et très générale au modèle de système distribué
et à la notion d'algorithme distribué. Il ne prétend pas à l'exhaustivité mais se contente de
mettre en place les hypothèses et propriétés nécessaires à l'évaluation des algorithmes
distribués et, en particulier, à l'analyse de leur complexité. C'est aussi de ce point de vue
qu'y sont partiellement exposés certains problèmes généraux de l'algorithmique distribuée,
par exemple ceux qui sont liés au concept de temps — synchronicité et asynchronicité,
synchronisation, causalité, etc.
1. Le parallèle et le distribué
S'il est une interrogation qui revient souvent dans les débats, les plans ou projets de
recherche touchant de près ou de loin au « parallélisme » — dans l'acception la plus
générale du terme —, c'est celle de la place respective de sa branche « parallèle » et de sa
branche « distribuée ». la question de leurs rapports mutuels, de leur(s) frontière(s). etc.
Les remarques qui suivent ne constituent qu'une très brève introduction à cette question, de
surcroît considérée ici principalement sous l'angle des performances (ou mesures de
complexité) des algorithmes et de leurs méthodes d'analyse.
À la fin des années 70, les premiers travaux sur les algorithmes distribués se sont
concentrés sur les systèmes asynchrones « à passage de messages » (cf. § 2).
L'algorithmique distribuée couvre désormais un très vaste domaine et traite des systèmes à
mémoire partagée comme des divers niveaux de connaissance globale ou de performance
des réseaux d'interconnexion (information structurelle, synchronisation, etc.). Il est ainsi
presque impossible de tracer une frontière nette — si tant est qu'elle existe — entre
l'informatique parallèle et l'informatique distribuée. Cependant, ces deux domaines restent 24 Concepts fondamentaux
séparés par un certain nombre de caractéristiques qui se perpétuent et persisteront de façon
prévisible à relativement moyen terme. Tout d'abord, la plupart des travaux en
algorithmique parallèle ont pour objectif d'optimiser la solution d'un problème donné :
ainsi, par exemple, les réseaux de tri, les circuits booléens ou les circuits VLSI —
considérés aussi comme une branche de l'informatique parallèle. En revanche, l'étude des
réseaux conduit souvent à résoudre différents problème sur une topologie de réseau fixée :
le routage, l'élection ou le tri distribués sont, par exemple, réalisés sur un réseau donné. En
ce qui nous concerne ici, il est également caractéristique qu'au sommet de l'édifice, les
algorithmes, leurs mesures de complexité et par suite les techniques et les méthodes
d'analyse de ces algorithmes peuvent être souvent radicalement différents d'un domaine à
l'autre. Le concept de complexité en communication par exemple n'est pas habituellement
pris en compte sur une PRAM ("Parallel Random Access Machine"), où les accès à la
mémoire partagée (en lecture et en écriture, mais exclusif(s) ou concurrent(s) selon la
PRAM ) représentent par hypothèse des opérations unitaires. Comme pour un algorithme
séquentiel, les seules ressources mises en œuvre par un algorithme parallèle et, partant, les
seuls coûts vraiment considérés, y sont, en général, les ressources en temps et en espace
mémoire. Les classes de complexité en parallèle (NC, GNC, RNC, SC et PC ; PC et
PC * ; PE et PE*, etc.) ont certes bien du mal à émerger, mais les travaux concernant les
hiérarchies de complexité en distribué sont encore plus inexistants... Disons enfin qu'en
dépit de leurs racines et de leurs préoccupations communes, les deux communautés de
chercheurs, celle « du parallèle » et celle « du distribué », restent relativement séparées.
2. Le modèle
Le modèle de système distribué (ou réparti) S considéré dans la suite — sauf mention
contraire — est une structure logicielle et matérielle distribuée en un réseau point à point
asynchrone d'entités communicantes. Les constituants du réseau d'interconnexion sont les
sites et le système de communication établi entre eux. Cette structure est modélisée par un
graphe G connexe, simple et symétrique, G = (X.U), où X est l'ensemble fini des entités
(sommets, sites ou processus) de S et U celui de ses lignes de communication (ou arêtes de
G) ; dans toute la suite, \X I = n est Xordre du réseau et \il I = m est le nombres de lignes
de communication (ou arêtes de G), i.e. la taille du réseau. Chaque site possède une
mémoire locale non partagée (de capacité bornée c) et au moins un processeur ; deux sites
(ou processus) de S reliés par une ligne de communication sont dits voisins. L'échange
d'information au sein du réseau s'effectue uniquement par messages. Systèmes distribués et algorithmes distribués 25
Les modèles de système à processus le plus clairement distribués (ou répartis) sont
ceux où les processus communiquent par échange ou passage de messages [LAMPORT,
LYNCH-90]. En bref, un processus envoie un message par ajout à une file de messages et
un autre processus le reçoit en le retirant de cette même file. Deux hypothèses
fondamentales caractérisent le modèle de système distribué S « à passage de messages »
( "Message-Passing System") :
1° L'échange de messages constitue le coût d'exécution dominant d'un algorithme sur S.
2° Toute entité du système S (y compris une ligne de communication) peut continuer à
fonctionner correctement de manière indépendante en dépit de la défaillance d'autres
entités de S (y compris des lignes de communication).
La première hypothèse permet de distinguer le processus d'échange de messages,
essentiel en informatique distribuée, de son utilisation comme simple technique de
synchronisation en informatique concurrente non répartie. La seconde hypothèse fonde
cette branche très importante de l'algorithmique distribuée qu'est l'étude de la tolérance aux
défaillances.
Un système dont la communication est ainsi réalisée par passage de messages
constitue une structure formelle cohérente pouvant modéliser divers environnements : les
systèmes distribués, les réseaux de communication, les systèmes parallèles, les
architectures systoliques, les automates cellulaires, etc. Dans une structure de ce type, les
entités du système communiquent avec leur(s) voisin(s) par transmission de suites bornées
de bits, la relation de voisinage ainsi induite définit un graphe modélisant la topologie de la
communication au sein du réseau. Dans la suite, les termes de site, processus, processeur,
sommet, sont utilisés comme synonymes, de même ceux de ligne, lien, arête, ou arc, ainsi
que ceux de réseau et ou graphe, pour autant qu'il n'y ait aucune ambiguïté possible. Une
telle identification se justifie dans la mesure où ces notions se confondent du point de vue
de l'analyse des algorithmes distribués. Dans le chapitre XII cependant, la notion de
familles (ou topologies) de réseau sur laquelle une fonction est calculable — ou un
problème résoluble — et celle de familles de graphes sont définies et utilisées de manière
distincte.
Dans toute la suite, nous supposerons que tout site ou processus de S est caractérisé
par une « valeur d'identification » qui lui est propre, son identité (id). L'identité de chaque
processus est tirée d'un ensemble /, il peut s'agir d'un nombre entier, d'une chaîne de
caractères ou de bits, etc. Sans perte de généralité, on suppose que / est un ensemble 26 Concepts fondamentaux
quelconque non vide, fini ou infini, muni d'un ordre total— l'ordre numérique sur Z,
l'ordre alphabétique ou lexicographique, etc. Les définitions des réseaux avec identités et
anonymes du paragraphe 3 illustrent cette notion d'identité .
Par ailleurs, les autres caractères distinctifs d'un tel système distribué asynchrone S
sont l'absence de toute mémoire partagée et d'horloge globale et l'absence de toute variable
ou état global qui serait perceptible par les composants de S à un « instant » donné — ce
concept d'instant est d'ailleurs exogène à un réseau asynchrone. Les seules classes
d'événements perçus par un processus quelconque sont donc soit les événements produits
par le processus lui-même de façon « spontanée » (par exemple l'envoi d'un message),
soit des événements causés par d'autres processus (par exemple la réception d'un ou
plusieurs messages émis par un ou plusieurs autres processus). Les hypothèses liées à
l'asynchronisme de S sont développées au § 4 de ce chapitre.
Un modèle de réseau est dit point à point s'il possède les trois caractéristiques
suivantes :
• Orientation locale. Tout processus est capable de faire la distinction entre ses portes,
mais les identités des autres processus et, en particulier celles de ses voisins, lui sont
a priori inconnues.
• Communication sans perte de message. Tout message envoyé à un voisin est reçu, si
ni la ligne ni le voisin récepteur ne sont fautifs durant la transmission. Cette
hypothèse n'entraîne pas l'existence d'une borne sur les délais de transmission (cf. §
4), elle stipule seulement qu'en l'absence de défaillance, tout message envoyé est
nécessairement reçu au bout d'un temps fini sans altération ni modification.
• Taille bornée des messages. Pour tout réseau G. tout message transmis dans G
contient au plus s bits, où s est une constante prédéfinie du réseau — ce qui G G
signifie que s est en 0(1) ou en 0(f(n,id)), n étant l'ordre de G et id l'identité G
maximale ou minimale des processus de G. Cette hypothèse entraîne que \blsc\
messages sont nécessaires à la transmission de b bits d'information dans le réseau G.
Elle reflète les limites pratiques qu'on doit imposer à la longueur des paquets — dans
un réseau à commutation de paquets — et à la taille des messages de contrôle —
dans un réseau àn de circuits ou commutation de messages. Systèmes distribués et algorithmes distribués 27
3. La notion d'algorithme distribué
Un algorithme distribué A sur un système distribué S n'est autre que la caractérisation
des transitions locales à réaliser séquentiellement par chaque processus de S à la réception
d'un message, ce processus étant dans un état déterminé. A peut être vu comme une
(, )
collection de processus qui, par échange d'information, participent à la réalisation d'un
but commun tout en conservant leur autonomie, indépendamment de tout langage de
programmation — même s'il en faut un pour mettre en œuvre l'algorithme en question.
Chaque processus peut alors être défini comme une suite d'événements, un ensemble fini
d'états et un ensemble fini de transitions atomiques entre événements ainsi schématisées :
( état, , (événement) , ) > ( état,+ i , (événement)y+i ),
èm e
où (événement), est une j' action atomique du processus. On classe généralement ces
événements en trois catégories : les événements d'envoi, les événements de réception et les s internes. Un événement interne produit seulement un changement d'état, un
événement d'envoi provoque l'envoi asynchrone d'un message (ou éventuellement
d'aucun), et un événement de réception donne lieu à la fois à la réception d'un message (ou
éventuellement d'aucun) et à la mise à jou r de l'état local selon les valeurs due (s'il
existe) — le contenu exact d'un événement interne est ici sans importance. Il faut préciser
que l'hypothèse sous-tendue par ce schéma est conforme à l'existence physique de tampons
non bornés à chaque extrémité d'une ligne de communication reliant deux processeurs
quelconques du système S (cf. propriété (ii) du § 3 et commentaires). Les réceptions ou
émissions de message(s) (aucun, un seul ou plusieurs) aux portes d'un processeur
correspondent ainsi respectivement à la libération ou à la mise en attente de message(s) dans
les tampons (éventuellement vides) des lignes de communications adjacentes à ce
processeur.
Cette modélisation de la notion d'algorithme distribué reste cohérente avec celle
à.'algorithme parallèle. Intuitivement, on peut considérer la mémoire partageable d'une
machine parallèle comme un processus particulier chargé uniquement de la communication,
c'est-à-dire ne pouvant que recevoir et émettre des messages. Ce processus n'effectue
aucun calcul local et ne traite pas les messages en transit qu'il se contente de relayer (voir
[LAVALLÉE-90 , chapitre 1]).
<*) Certains auteurs réservent le terme d'« algorithme » au programme résidant situé en
chaque processeur et utilisent celui de « protocole » pour désigner l'ensemble de ces
algorithmes. Nous ne ferons pas cette distinction, mais nous parlerons plus volontiers de
protocole de routage ou de communication. 28 Concepts fondamentaux
On ne peut donc considérer le concept d'algorithme distribué comme une simple
variante de celui d'algorithme séquentiel ; un algorithme distribué n'est pas un algorithme
séquentiel considéré dans un environnement distribué multiprocesseur. Ces deux concepts
d'algorithmes sont en réalité très différents : l'influence immédiate de l'environnement
parallèle est trop prégnante et les facteurs liés au système et l'algorithme distribué lui-même
s'y entremêlent trop pour que les deux notions puissent être identifiées. Ainsi, A est défini
sur un système distribué S, lequel suppose des processus et des lignes de communication,
un état local et une mémoire locale, etc. Un algorithme distribué est donc d'emblée une
construction où la communication joue un rôle central et où, par conséquent, la causalité
entre événements, la connaissance locale, la connaissance commune et l'apprentissage des
processus, etc. sont des notions à la fois fondamentales et absolument spécifiques à
l'environnement distribué.
Afin d'assurer une réalisation entièrement distribuée des transitions au sein de S, on
suppose que tous les processus y sont symétriques. C'est-à-dire qu'ils possèdent les
mêmes définitions de contexte et exécutent localement le même code d'algorithme
séquentiel. Les processus jouent donc tous le même rôle et, de ce strict point de vue, il n'y
a pas de différence entre eux, même si le seul fait de posséder une identité propre, supposée
distincte de toute autre identité de processus, est déjà une forme de dissymétrie générique :
c'est ainsi que la symétrie totale n'est obtenue que lorsque les processus ne possèdent pas
d'identité, ils sont alors absolument indiscernables, identiques. Le fait que chaque
processus exécute le même code d'algorithme engendre la symétrie (dite « forte »), au
sens où elle est définie habituellement en environnement distribué. Ceci étant, nous verrons
qu e les processus n'exécutent pas forcément toujours tous la même action
« simultanément » — certains pouvant, par exemple, être passifs tandis que d'autres sont
actifs. Dans certains algorithmes même, les processus peuvent avoir des comportements
identiques ou différents selon les messages reçus, selon qu'ils sont des « initiateurs » ou
non (cf. propriété (xiv) du § 4).
Un des paradigmes de l'informatique distribuée est d'ailleurs de briser la symétrie des
processus en octroyant à l'un d'entre eux un privilège. C'est le cas du problème général de
l'exclusion mutuelle. Les célèbres problèmes de Y exclusio n mutuelle simple, des lecteurs-
rédacteurs, du producteur-consommateur et du dîner des philosophes sont diverses
variantes de ce problème paradigmatique dont chacune est définie par des contraintes
d'exclusion mutuelle spécifiques entre processus coopérants. Ainsi en est-il de l'exclusion
mutuelle simple (cf. chapitre VI) : dans un ensemble de processus communicants qui
coopèrent à la réalisation d'un objectif commun, comment attribuer à un seul et unique
processus et à un instant donné, le privilège d'accéder à une ou plusieurs ressources Systèmes distribués et algorithmes distribués 29
partagées (mais non partageables) déterminées ? Par exemple à des fin de lecture,
d'écriture, etc. — sur une mémoire ou une imprimante partagée, sur des disques ou toute
autre ressource commune.
C'est aussi le cas de cet autre problème paradigmatique qu'est l'élection où un
processus unique du système distribué S est privilégié grâce à un choix distribué de tous les s coopérants de S. L'élection dans le système consiste à atteindre une
configuration dans laquelle un seul et unique processus est dans un état prédéterminé, élu,
et tous les autres dans un état prédéterminé différent du précédent, battu (cf. chapitre III,
§ 1). Une fois élu, ce processus privilégié peut jouer ensuite un rôle de coordination et de
contrôle au sein du système. Il est en effet souvent beaucoup plus aisé et rapide de réaliser
des applications distribuées en utilisant un processus centralisateur dans S qui, entre autres,
peut récupérer les calculs et réaliser des transferts de données, de résultats, etc. L'élection
est ainsi à la base de la plupart des méthodes de contrôle et de coordination utilisées en
informatique distribuée centralisée comme l'exclusion mutuelle simple, la synchronisation,
le redémarrage sur panne d'un système informatique, etc.
En se fondant sur les notions ci-dessus, on considère les réseaux de processus
comm e pouvant appartenir à l'une des trois catégories qui suivent, relativement aux
« hypothèses de symétrie » sur les processus : les réseaux centralisés, les réseaux avec
identités et les réseaux anonymes.
Les réseaux centralisés. Un réseau est dit centralisé ("Leader Network") si, dans le
modèle « standard » de système distribué S du paragraphe 2, il existe un seul et
unique processus dans l'état élu , tous les autres se trouvant dans l'état battu.
Les réseaux avec identités. Ce type de réseau ("Named Network") correspond au
modèle « standard » de système distribué S : chaque processus de S y est distingué
par l'attribution d'une identité unique, distincte des autres et connue de lui seul
(cf. ci-dessous).
Les réseaux anonymes. On dit qu'un réseau est anonyme ("Anonymous Network") si
les processus du système distribué S y sont symétriques du point de vue de
l'exécution algorithmique, mais ne possèdent pas d'identités (connues d'eux) :
ils sont alors indiscernables.
Les algorithmes distribués évalués et analysés ici sont considérés exclusivement dans
ces deux dernières catégories de réseaux. Dans la deuxième partie (« Les réseaux avec
identités », chapitre III à VIII), les identités des processus sont tirées du sous-ensemble D 30 Concepts fondamentaux
des suites finies, non vides d'éléments distincts de / : l'ensemble des identités dans S est
ainsi muni d'un ordre total strict et, dans ce modèle, les identités de tous les processus sont
donc, par hypothèse, bien distinctes***. La situation où les processus peuvent posséder, en
tout ou partie, des identités non distinctes (connues d'eux) correspond aux réseaux dits
« pseudo-anonymes », elle se ramène de fait au cas anonyme s'il n'existe aucune
régularité dans l'égalité des identités — une périodicité par exemple. Lorsque les processus
n'ont aucune identité (connue d'eux), situation qui est abordée en troisième partie (« Les
réseaux anonymes », chapitre IX à XII) , le réseau est dit anonyme — les processus y sont
identiques ou indiscernables.
Il faut noter que, dans le modèle de système distribué défini ici, l'exclusion mutuelle
ou l'élection d'un processus n'ont de sens que dans un environnement distribué
« suffisamment » fiable. Il est, par exemple, inutile d'élire un processus centralisateur si
l'on n'est pas assuré qu'il est raisonnablement à l'abri de défaillances, c'est-à-dire si l'on
ne peut pas supposer/a/7?/e la probabilité d'occurrence d'une défaillance quelconque sur
une durée « acceptable » de fonctionnement du système...
Dans tous les problèmes distribués, cette possibilité de défaillance (faute bénigne ou
maligne, concernant un ou plusieurs processus, ou bien une ou plusieurs lignes de
communication du réseau, etc.) contraint les concepteurs à élaborer des algorithmes qui
soient « le plus résistant possible » aux défaillances : en particulier donc, dess
distribués et décentralisés. En ce qui concerne la majorité des algorithmes analysés ici, ils
sont supposés exécutés sur des réseau absolument fiables — ce qui est très loin de la réalité
informatique mais beaucoup plus simple dans une première approche.
En général, la plupart des algorithmes distribués supposent des propriétés des voies
logicielles de communication et de comportement des processus de S, définies comme aux
paragraphes (§ 4, 5 et 6) qui suivent.
( ) Les propriétés de l'ensemble D (l'ordre total strict en particulier) sont utilisées, par
exemple, dans les algorithmes d'élection opérant par comparaisons — le plus souvent des
algorithmes de calcul d'extremum. Dans la deuxième partie, les analyses de complexité et
d'optimalité sont fondées sur ces propriétés (voir le chapitre III) . Systèmes distribués et algorithmes distribués 31
4. Hypothèses sur les propriétés du réseau
Les processus et les voies logicielles de communication (ou réseau de
communication) d'un système distribué S, peuvent ou doivent posséder les unes ou les
autres des propriétés fondamentales suivantes <*> :
(i) Le graphe G sous-jacent au réseau du système S est connexe.
(ii) Les délais d'acheminement des messages le long des lignes de communication sont
finis mais non bornés : un message prend un temps fini mais arbitrairement long
d'un processus P, à un processus voisin Pj (le système est asynchrone).
(iii) Au contraire, le délai d'acheminement de tout message le long de chaque ligne de
communication est borné, majoré par une constante r. On peut alors supposer que
tous les délais sont soit majorés, soit égaux à cette constante r, qui constitue alors une
« unité de temps » de transmission des messages sur les lignes. Dans le premier cas,
le système est dit « asynchrone à délais bornés » ou encore « partiellement
synchrone ».
(iv) Dans ce dernier cas ((iii)), par ailleurs, tout message envoyé à un processus est
instantanément placé dans la file d'attente correspondante et l'ordonnanceur sous-
jacent au réseau de communication se charge seulement de permettre aux processus le
traitement de leurs files d'attente. S'il existe des messages en attente dans les files
d'un ou plusieurs processus (pour réception), l'ordonnanceur doit accorder cette
permission de réception en un délai fini.
(v) Conformément à la définition d'un algorithme distribué (§ 3), un tampon de taille
finie, mais non bornée, est supposé associé à chaque ligne de communication.
(vi) Les messages reçus par un processus sont traités dans leur ordre d'arrivée ; si
plusieurs messages sont reçus concurremment par un processus, ils sont traités dans
un ordre arbitraire, ou bien dans celui des identités des processus émetteurs.
Plusieurs de ces propriétés sont relatives au synchronisme des voies de communications,
tandis que d'autres sont relatives au synchronisme des processus. Il ne faut pas confondre ces
deux notions (cf. § 5.2 à propos des synchroniseurs, par exemple). 32 Concepts fondamentaux
(vii) Pour tout couple de processus communicants, l'ordre de réception des messages est
identique à leur ordre de transmission (pas de déséquencement). Les transmissions
sont « fifo » ("First-ln First-Out").
(viii) Au contraire, l'ordre des messages reçus est éventuellement différent de l'ordre des
messages transmis (il peut y avoir déséquencement). Les transmissions le long des
lignes ne sont pas «fifo ».
(ix) Trois modes de transmission peuvent être utilisés : « simplex », « half-duplex » et
« full-duple x ». Une ligne en simplex est unidirectionnelle ; le mode full-duplex et
le mode half-duplex correspondent, respectivement, à la possibilité ou à
l'impossibilité de croisement de deux messages sur une même ligne
(x) Aucun message n'est créé par le système de routage.
(xi) La transmission se fait sur toute ligne sans duplication de message.
(xii) Au contraire, tout message peut être dupliqué lors de sa transmission.
(xiii) La transmission de tout message s'effectue sans altération ni modification aucune.
(jci'vj Le début d'une exécution quelconque d'un algorithme distribué est enclenché par
« l'éveil spontané » d'un sous-ensemble quelconque, non vide, de l'ensemble des
processus du réseau
(xv) Les seules connaissances et informations initiales d'un processus quelconque (dans
un réseau avec identités) sont constituées, d'une part, de sa propre identité et, d'autre
part, des portes d'entrée/sortie (distinctes) menant à ses voisins, i.e. ses arêtes
adjacentes.
Commentaires sur certaines de ces propriétés fondamentales
(ii) Le caractère asynchrone d'un réseau de n processus implique qu'il n'existe
aucune horloge globale mais seulement n horloges locales aux processus sans relations
entre elles.
(iii) Dans un système asynchrone à délais bornés, la complexité en temps d'un
algorithme distribué est une notion naturelle (voir les définitions du chapitre II, § 2 et 4).
Cette propriété est aussi très importante pour la détection des défaillances simples, en effet,
si la perte d'un message est possible à la suite d'une défaillance simple, alors, au delà de la Systèmes distribués et algorithmes distribués 33
borne r, un message attendu par un processus sera soit reçu soit perdu. Il peut s'agir en
l'occurrence d'une faute à la transmission, à la réception, ou aux deux (faute générale),
mais pas d'une faute « byzantine » (cf. propriété (xiii)).
On peut aussi faire l'hypothèse de délais d'acheminement des messages le long des
lignes de communication majorés par une fonction raisonnable de n, par exemple un
polynôme en n. Cette hypothèse permet de concevoir un autre modèle de système distribué
asynchrone où le délai d'acheminement de tout message le long de chaque ligne de
communication est pris en compte. Des mesures de complexité dites « dépendantes des
délais » ("Cost-Sensitive") peuvent ainsi être définies à partir de ce modèle (cf. chapitre U,
§ 6).
(iv) Ces hypothèses ne supposent aucune forme d'équité particulière de
l'ordonnanceur. Il s'agit seulement de spécifier qu'en présence de message(s) dans la file
d'un processus, l'ordonnanceur ne doit pas les ignorer indéfiniment. Ce dernier point revêt
une importance particulière dans la mesure où, sans cette hypothèse, une situation
d'interblocage est absolument inévitable (voir le § 2 du chapitre U pour plus de détails sur
le rôle d'un ordonnanceur).
(v) Tout message envoyé par un processus P, vers un processus Pj entre dans le
tampon de la ligne (Pi,Pj) et le processus P, attend, pour changer d'état et éventuellement
envoyer un ou des messages, que le plus ancien message en attente soit libéré par le tampon
de (Pj,Pj). Ces hypothèses permettent de définir des mesures de complexité en
communication et « en temps » d'un algorithme distribué sur S (cf. chapitre II, § 2).
(vii), (viii) Dans la suite, nous ferons assez systématiquement l'hypothèse de lignes
de communication fifo — en particulier pour les algorithmes classiques d'élection. En tout
état de cause, si la discipline fifo n'est pas respectée par hypothèse dans un réseau de
communication, il est toujours possible de la simuler grâce à l'ajout d'un compteur (local)
de messages envoyés. Ensuite, pour chaque ligne de communication, il suffit de trier les
messages qui arrivent selon leur numéro d'ordre au compteur.
(xii) La duplication est le seul cas de création de message par le système de routage
lui-même.
(xiii) Cette propriété est alors en contradiction avec l'hypothèse de duplication (xii),
d'une part, et suppose d'autre part un certain type de fiabilité du réseau, l'absence de
défaillances dites « byzantines » (ou « de type byzantin »). 34 Concepts fondamentaux
(xiv) Précisons ici quelques notions qui seront utiles dans la suite. Un processus
initiateur a est un processus qui déclenche l'exécution de son propre algorithme local de
manière spontanée et indépendante, c'est-à-dire activé par telle ou telle condition interne au
processus (« éveil spontané »). Un processus non initiateur est initialement « non
éveillé » et ne peut être engagé dans l'algorithme que par la réception d'un message, lequel
déclenche alors l'exécution de son propre algorithme. Le premier événement d'un
processus initiateur est donc un événement interne ou bien un événement d'envoi, tandis
que le premier événement d'un processus non initiateur est unt de réception.
Dans la suite, nous noterons a le nombre d'initiateurs indépendants (simultanés ou non)
d'un algorithme distribué. Un algorithme centralisé est ainsi un algorithme ayant, dans
toute exécution, un initiateur unique a (a = 1). Il faut noter que cette notion concerne les
exécutions d'un algorithme, elle est donc différente de celle de réseau centralisé définie plus
haut. Si a - n, l'éveil spontané (simultanés ou non) est le fait de l'ensemble de tous les
processus du réseau. Ce problème de l'éveil ("Wake-up Problem") est abordé sous
différents angles et dans différents contextes : au paragraphe 6.1 à propos de la
synchronisation virtuelle, au paragraphe 7 dans la discussion du modèle, au chapitre III
( § 2.1 et 2.2) du point de vue de l'analyse de la complexité en messages d'un algorithme,
au chapitre V (§ 4.1 ) à propos des algorithmes « de parcours », etc.
(xv) En fait, cette propriété est déjà explicitement contenue dans la définition d'un
réseau point à point : aucun processus ne connaît l'identité d'aucun autre dans le réseau.
Cependant, l'absence d'information de tout processus au sein d'un réseau sur l'identité de
ses voisins en particulier est une hypothèse très importante. En effet, elle implique
qu'aucun processus n'est capable, par exemple, de différencier ses arêtes adjacentes non
encore utilisées dans un algorithme distribué : cette cécité permet le calcul des bornes
inférieures de plusieurs classes d'algorithmes, en particulier des algorithmes d'élection au
chapitre IV (§ 3) et de construction d'un arbre de recouvrement au chapitre V (§ 3).
5. Systèmes et algorithmes synchrones
5.1. Synchronicité
Il existe plusieurs classes de systèmes (ou réseaux) synchrones qui correspondent à
des hypothèses de contraintes temporelles de plus en plus fortes au sein du système de
communication de S. Systèmes distribués et algorithmes distribués 35
1° Réseaux archimédiens ([VlTÂNYi-85]). En l'absence de défaillances, il existe des
bornes sur les vitesses relatives des composants du système, mais celles-ci peuvent
être très approximatives et, surtout, elles ne sont pas nécessairement connues des
processus.
2° Synchronicité partielle. En l'absence de défaillance et à tout instant, le délai de
transmission des messages le long de chaque ligne de communication est majoré par
une constante r (voir l'hypothèse (iii) sur les propriétés des lignes de
communication). Le délai de transmission sur une ligne quelconque n'est pas
négligeable devant les temps de calcul locaux et il peut varier d'une ligne de
communication à une autre, mais on prend seulement en compte un majorant des
délais de communication le long de toutes les lignes du réseau : il s'agit du modèle
correspondant à la propriété (iii), paragraphe 4. Par ailleurs, ce majorant Test connu
des processus dont les horloges sont considérées comme synchrones — cette classe
de réseaux asynchrones à délais bornés ou partiellements rejoint la
suivante.
3° Horloges synchrones. On suppose ici comme pour la classe suivante que chaque
processus possède une horloge locale propre. Ces horloges sont alors synchrones si
elles sont toutes incrémentées en même temps au cours de l'algorithme. Par contre,
cette hypothèse seule n'implique pas que ces horloges marquent la même valeur. En
l'absence de défaillance, tout message envoyé par un processus au temps t à un
voisin est reçu et traité par ce voisin au temps / + 1, temps local du processus
envoyeur.
4° Synchronicité totale. Les horloges locales étant synchrones (hypothèse précédente),
elles battent de plus à l'unisson et marquent la même valeur. En l'absence de toute
défaillance, tout message envoyé par un processus au temps t à un voisin est reçu et
traité par ce voisin au temps / + 1, temps global du système, commun aux deux
processus. En particulier, si aucun message n'est reçu par un processus au temps t en
provenance d'un voisin, alors ou bien ce voisin n'a envoyé aucun message au temps
f - 1, ou bien le message a été perdu. Dans un réseau totalement synchrone, tous les
processus commencent simultanément leur activité au signal d'un initiateur global.
Cette dernière classe synchrone se ramène à supposer l'existence d'une horloge
globale au réseau qui synchronise cycle par cycle chaque événement et chaque action de
tout processus de S. Un message est par exemple toujours envoyé avant sa réception, ce
qui n'est pas forcément le cas en l'absence d'horloge globale : un ordre temporel sur les 36 Concepts fondamentaux
événements n'ayant a priori aucun caractère global dans un système distribué, il ne peut être
observé directement qu'entre événements au sein d'un même processus.
Dans un système totalement synchrone, tous les processus ont accès à l'horloge
globale et n'envoient des messages qu'à chaque cycle de cette dernière. Sur une ligne de
communication donnée, chaque processus ne peut envoyer qu'un message au plus à chaque
cycle d'horloge. Par ailleurs, le délai d'acheminement d'un message le long de toute ligne
de communication peut être inférieur ou égal à l'unité de temps de l'horloge globale, ou
bien exactement égal à cette unité de temps, ce qui est une hypothèse plus restrictive
(cf. chapitre II, § 4.2).
Remarqu e
Les classes de synchronicité considérées plus haut se ramènent en fait à trois grandes
classes de réseaux : les réseaux archimédiens, les réseaux asynchrones à délais bornés (ou
partiellement synchrones, ou encore à horloges synchrones) et les réseaux totalement
synchrones.
5.2. Synchroniseurs
Les algorithmes asynchrones étant bien souvent moins performants que leurs
correspondants synchrones et leur analyse de complexité beaucoup plus complexe, il est
très utile de disposer d'une méthode générale simple et rapide de simulation des uns par les
autres.
Supposons donc un algorithme conçu pour un réseau donné, totalement synchrone.
Si l'on veut utiliser le mêmee synchrone sur le réseau asynchrone de S possédant
la même topologie, nous ne disposons plus d'aucun signal global de déclenchement et les
délais de transmission des messages y sont arbitraires (propriété (ii) du § 4) : il faut
surmonter ces difficultés pour s'assurer de la correction des algorithmes distribués, de
l'initialisation à la terminaison. Pour ce faire, un mécanisme logiciel tel que le
synchroniseur permet de concevoir simplement (de façon synchrone) n'importe quel
algorithme distribué synchrone dans n'importe quel réseau asynchrone en améliorant de
façon substantielle sa complexité (en temps et en messages) par rapport à l'algorithme
asynchrone correspondant. Fondamentalement, un synchroniseur est un protocole distribué
de synchronisation par communication qui simule les cycles d'horloge de façon que tout
message ne puisse être émis et reçu que durant un cycle. Autrement dit, le synchroniseur
agit sur une couche supérieure de logiciel en synchronisant l'émission et la réception d'un
message entre deux simulations de battements d'horloge. Systèmes distribués et algorithmes distribués 37
On peut ainsi s'assurer que le réseau asynchrone se comporte comme un réseau
synchrone du point de vue de l'exécution spécifique de l'algorithme synchrone particulier
considéré. Bien entendu, le synchroniseur lui-même introduit un certain surcoût en
complexité, en particulier en messages, mais sans commune mesure avec les gains réalisés.
6. Synchronisation logique
Considérons un système distribué asynchrone S, sans horloge ni « compteur de
temps » globaux et au sens de la propriété (ii) (§ 4) du système de communication. De
manière générale, on cherche à réaliser une synchronisation logique, ou virtuelle, du réseau
à partir des communications elles-mêmes.
Par exemple, la synchronisation par vague est une méthode très fructueuse
développée en particulier par Friedemann Mattem et généralisée par Gerard Tel [TEL-94].
Une approche très différente est celle de Gérard Florin et Ivan Lavallée [FLORIN,
LAVALLÉE-93] (cf. notes bibliographiques).
6.1 . Synchronisation virtuelle
La synchronisation virtuelle la plus couramment utilisée pour l'analyse des
algorithmes consiste, tout d'abord, à compenser l'absence de signal global par la création
d'un mécanisme virtuel local de déclenchement et de terminaison. Il s'agit d'une hypothèse
simple relative à la phase d'initialisation : tout processus est d'abord considéré dans un état
dit passif (S est alors dans un état stable dit quiescent), puis, à la suite d'une action
extérieure ou spontanément, un nombre a (1 < a < n) de processus initiateurs entrent
dans l'état actif et commencent à exécuter indépendamment (simultanément ou non)
l'algorithme (propriété (jciv) du § 4). Afin de comparer la complexité en messages de divers
algorithmes distribués, on formule souvent l'hypothèse que a = n, c'est-à-dire que tous
les processus sont indépendamment initiateurs simultanés de l'algorithme. Il se peut
cependant que pour certains algorithmes distribués, cette hypothèse diminue la généralité de
l'analyse ou que telle classe d'algorithmes suppose un initiateur unique, comme par
exemple la classe des algorithmes de diffusion (chapitre II, § 10) ou de parcours (chapitre
V § 4.1). À l'inverse, l'hypothèse d'un éveil collectif (a = n) peut aussi être inhérente à
l'algorithme lui-même, comme c'est le cas pour certains algorithmes distribués de
construction d'arbres de recouvrement minimum (chapitre V, § 3.3), ou pour les
algorithmes distribués sur les graphes du chapitre VII (voir également la note du § 7
concernant les systèmes dont l'état initial est supposé arbitraire et inconnu). 38 Concepts fondamentaux
Pour résumer, on peut donc supposer que le système S se comporte selon les règles
suivantes.
1 ° Un processus est toujours dans l'un des deux états fondamentaux, actif ou passif.
2° Seuls des processus actifs peuvent envoyer des messages d'activation.
3° Un processus peut passer de l'état actif h l'état passif h tout instant.
4° Un processus ne peut passer de l'état passif h l'état actif qu'à la réception d'un
message d'activation
5° Si tous les processus sont passifs et qu'aucun message d'activation n'est plus en
circulation, S atteint un état stable, dit quiescent.
Typiquement, cette propriété est atteinte par S lors de la terminaison des algorithmes
distribués ou, par exemple, lors d'un interblocage global des communications. Ainsi, dans
tout système distribué S (anonyme ou non) un algorithme distribué peut effectuer une
terminaiso n « pa r messages » ou «par processus ». Plus précisément, un algorithme
distribué est dit se terminer par processus lorsque, pour toute exécution, tous les processus
du système S atteignent un état stable quiescent ; ceci correspond à la terminaison au sens
habituel (avec détection de terminaison). En revanche, la terminaison par messages se
caractérise par le fait que l'information de fin d'exécution de l'algorithme peut ne pas
atteindre certains processus du réseau, l'algorithme distribué est alors dit sans détection de
terminaison au sens habituel du terme. Les algorithmes probabilistes d'élection dans des
réseaux anonymes, par exemple, se terminent par messages ou par processus selon le degré
d'information des entités sur l'ordre n du réseau (voir le chapitre IX, § 4.1 et le chapitre
XI, § 2).
6.2 . Algorithme distribué dirigé par réception de messages
Pour analyser la complexité d'un algorithme distribué dans S, il faut aussi surmonter
la contrainte due aux délais de transmissions arbitraires (propriété (H) du § 4). On fait alors
le plus souvent l'hypothèse que chaque processus est virtuellement synchronisé par
l'événement local suivant : la réception d'un message.
A part pour le(s) premier(s) message(s) d'initialisation — envoyé(s) par un sous-
ensemble quelconque, non vide, de l'ensemble X des processus de S —, un processus ne
peut se livrer à une quelconque activité (changement d'état, exécution d'une instruction, Systèmes distribués et algorithmes distribués 39
envoi d'un message, calcul local, etc.) qu'à la réception d'un message, et comme
conséquence de cette réception ; il devient ensuite inactif jusqu'à la réception d'un nouveau
message. Cette hypothèse se formule généralement de façon simple et imagée :
l'algorithme est dit « dirigé par réception de messages » ("Message Driven").
Pour un processus de S, défini comme une suite d'événements (§ 3), un algorithme
dirigé par messages n'est donc composé que d'un seul et unique type d'événement, la
réception d'un message : celle-ci déclenche une action atomique qui peut générer une mise
à jour de l'état local et l'envoi d'un nombre quelconque (fini) de messages à d'autres
processus. Il faut noter que, d'une part, cette activité peut être probabiliste et que, d'autre
part, il n'existe pas d'autres messages engendrés par le système — en particulier, aucun
message ne peut être engendré « spontanément » dans S.
Théorèm e 1. Soit un système distribué asynchrone S et deux algorithmes sur S, un
algorithme quelconque A et un algorithme A' dirigé par messages. Notons M(A,n) et
M(A',n ) le nombre de messages respectif échangés par A et par A'. On a
M(A,n) > M(A',n).
Démonstration. A étant un algorithme distribué asynchrone quelconque sur S, il est
toujours possible de construire un algorithme distribuée A ' dirigé par messages
comme suit. Après initialisation et réception d'un message quelconque, A ' envoi e une suite
de messages aussi longue que l'algorithme A peut le permettre, sans réception d'aucun
message et, ensuite seulement, A ' reçoit le message suivant. Par construction, A ' est alors
bien un algorithme dirigé par messages tel que M(A,n) > M(A\n) et toute exécution de A '
constitue une exécution possible de A — malgré des hypothèses (éventuellement) très
pessimistes de distribution des délais de transmission des messages. •
Le théorème 1 ci-dessus est utile, par exemple, pour le calcul de la bom e inférieure
du nombre de messages d'un algorithme distribué asynchrone quelconque : il suffit de
calculer cette borne pour uneée dirigé par messages
(cf. chapitre III, § 3).
Plus généralement, un algorithme distribué A peut être considéré, du point de vue de
l'analyse de la complexité, comme un algorithme asynchrone dirigé par réception de
messages, qui s'exécute dans un système distribué virtuellement synchrone S. Il est alors
naturel d'utiliser pour l'analyse le concept de phases virtuelles, puisque l'algorithme assure
lui-même sa propre synchronisation. Une phase est l'équivalent virtuel d'un cycle
d'horloge globale dans un système distribué totalement synchrone : à chaque phase ç>de
A, globalement, les processus peuvent recevoir des messages, les traiter et effectuer des 40 Concepts fondamentaux
calculs locaux éventuels, et envoyer des messages qui seront reçus et traités durant la phase
suivante cp + 1. On peut considérer ce type de synchronisation logique comme un cas
particulier de synchroniseur qui fonctionnerait de manière purement virtuelle. Un
algorithme synchrone dirigé par message est dirigé à la foi s par les messages et pa r le temps
( "Time and Message Driven ").
Remarqu e
Lorsqu'o n a affaire à un anneau dont les transmissions le long des liens de
communication sont fifo (hypothèse (iv) du § 4), le nombre de messages échangés ne
dépend plus des délais relatifs de transmission. On peut donc faire l'hypothèse que tous les
processus sont actifs simultanément au temps t = 1 et que les délais de transmission des
messages le long des lignes de l'anneau sont A'une unité de temps.
Le s hypothèses ci-dessus sont, en un sens, les plus faibles des contraintes
temporelles dans un réseau. Elles sont nécessaires pour l'analyse des algorithmes distribués
et, en fait, on peut les formuler en toute généralité si on s'en tient à ce seul point de vue.
Les analyses d'algorithmes d'élection sur les anneaux, par exemple, s'appuient sur ces
hypothèses (cf. chapitre III, § 2.1 et 2.2).
7. Discussion du modèle
Pour conclure ce chapitre d'introduction au modèle de système et d'algorithme
distribués, il faut souligner que, si la plupart des travaux dans ce domaine ont toujours été
généreusement larges dans leur définition des classes de défaillances à envisager, ils se
sont, à l'inverse, toujours montrés assez stricts quant aux hypothèses et aux modèles de
systèmes. Les algorithmes distribués sont souvent étudiés à l'aide d'un modèle de système
distribué synchrone, dans lequel tout processus possède une identité unique, souvent
connue de tous les autres processus — ou du moins de tous ses voisins (et vice versa) —,
et où l'initialisation est réalisée au temps zéro dans un état lui aussi bien déterminé et connu
du système.
Aucune de ces hypothèses n'est véritablement réaliste dans les réseaux actuels, et,
tenter de les vérifier, même sur une seule machine, devient de plus en plus difficile et
coûteux. Les grands systèmes ne fonctionnent pas avec une horloge globale et ne sont donc
pas synchrones. Octroyer une identité spécifique à chaque processus est également coûteux Systèmes distribués et algorithmes distribués 41
et difficile <*>, de plus, cela complique inutilement toute reconfiguration du système en cas de
défaillance. Enfin, restaurer simultanément toutes les unités et les lignes de communication
d'un grand réseau à un état initial est virtuellement irréalisable, et, quand bien même une
telle restauration serait possible, on ne l'effectuerait que très rarement du fait de ses effets
singulièrement destructeurs sur les activités en cours.
Bref, un modèle plus réaliste de système distribué S ' supposerait une définition
moins contraignante que celle du paragraphe 2 . Par exemple, S ' est une structure logicielle
et matérielle distribuée en un réseau asynchrone et anonyme de n processus séquentiels
communicants absolument indiscernables dont l'état initial est arbitraire et inconnu, les
autres hypothèses du système standard S restant grosso modo inchangées dans ce nouveau
modèle, à l'exception du système de communication. En effet, si on se place sur la couche
de logiciel la plus basse de S ', la communication est, en général, matérialisée par une
mémoire partagée : nous supposons donc que, dans S ', les processus communiquent
uniquement par l'intermédiaire d'un registre unique de taille finie (dont Y état initial est
arbitraire et inconnu). Tout accès à ce registre partagé ne peut s'effectuer que grâce à des
instructions atomiques de type "Test-and-Set" qui y lisent une valeur, puis en écrivent une
nouvelle — pouvant dépendre de la précédente —, et ce, en une unique étape indivisible.
Paradoxalement, ce système de communication est en fait très proche de celui du
paragraphe 2 (communication exclusive par messages), dans la mesure où le canal
physique reliant un processus à un autre peut être considérée comme un registre binaire
partagé, sur lequel uns peut écrire en envoyant un voltage approprié, et l'autre
peut lire, en l'enregistrant. En revanche, une conséquence très importante de cette définition
de 5' — où le réseau est supposé être dans un état initial arbitraire et inconnu — est que,
contrairement aux hypothèse formulées précédemment pour le modèle standard S, nous
pouvons supposer que le déclenchement d'un algorithme distribué est toujours réalisé
indépendamment (simultanément ou non) par un nombre quelconque a de processus
initiateurs (1 < a < n) parmi la collection des n processus du système. Nous avons déjà
vu que, dans le cadre du système standard S, on pouvait se limiter le plus souvent à un
déclenchement conjoint de l'exécution des n processus (§ 6 ) ; ce n'est plus le cas dans le
modèle S'. Le problème de l'éveil des processus ("The Wake-up Problem") dans un
système dynamique apparaît ainsi comme essentiel en informatique distribuée (cf.
[FISCHER , MORAN, RUDICH, TAUBENFELD-90] OU [ISRAELI, KRANAKIS, KRIZANC,
SANTORO-93]) .
(*) Utili ser le numéro de fabrication du processeur comme identité du processus est certes
une bonne idée... à condition de ne supposer qu'un processeur par processus, et vice versa ! 42 Concepts fondamentaux
Une première voie de recherche analogue et cohérente avec celle-ci est empruntée
dans [AFEK, LANDAU, SCHIEBER, YUNG-90], OÙ un modèle de réseau multimédia
associant un modèle standard de réseau point à point à un modèle standard de bus à
collisions est proposé.
Une seconde voie de recherche s'inscrit dans le droit fil de la définition du système
S'. Il s'agit de l'étude de 1'« auto-stabilisation » dans les systèmes distribué et des
systèmes et algorithmes distribués « auto-stabilisants » {"Self-Stabilizing Systems", "Self-
Stabilizing Algorithms"). Un systèmes distribué est dit auto-stabilisant si une exécution
quelconque peut y être déclenchée alors qu'il se trouve dans un état global possible
absolument quelconque. Une fois lancé, le système retrouve de lui-même sa cohérence
interne, sans intervention extérieure d'aucune sorte : il s'auto-stabilise. Cette propriété rend
le système tolérant à des défaillances d'un certain type, les pannes franches de processeurs
avec rétablissement spontanée dans un état quelconque. Le système se stabilise lorsque le
délai écoulé entre un rétablissement et l'occurrence d'une nouvelle panne franche est
suffisamment long — la durée d'une panne n'est pas prise en compte ici.
Deux catégories de critiques au modèl e à mémoire partagée S ' peuvent éventuellement
être avancées. La première est que , la plupart des ordinateurs n'implémentant en mémoire
que des instructions de type « lecture et écriture », il est inutile de considérer un modèle
plus puissant dans lequel les instructions seraient atomiques et de type "Test-and-Set".
Mais c'est oublier que les systèmes parallèles de grande taille n'accèdent à une mémoire
commune que pa r l'intermédiaire d'un réseau de communication, lequel peut posséder une
puissance indépendante de traitement suffisante pour lui permettre d'implémenter des
primitives plus élaborées que de simples lectures et écritures. On a déjà proposé de telles
machines MIMD (« Multi-instructions, multi-données »). De plus, tout ce qu'il est
impossible d'exécuter sur ce modèle constitue, a fortiori, une preuve d'impossibilité sur un
modèle lecture/écriture plus faible. La second e critique potentielle est que c e type de modèle
n'est pas réaliste pour les grands systèmes et que, dan s la réalité, les systèmes distribués
sont concrètement fondés sur le paradigme d'une communication par passage de messages
("Message Passing"). En fait, les système s conçus autour du passage de messages se
révèlent difficiles à implémenter et, par ailleurs, n'étant eux-mêmes qu'une abstraction, ils
peuvent fort bien ne refléter les réalités sous-jacentes du matériel que de manière très
imparfaite et imprécise.
Nous verrons d'ailleurs au chapitre II que les restrictions formulées ne concernent
pas seulement le modèle de système distribué, mais également les hypothèses et les
définitions des mesures de complexité, quoique sous un angle différent. Systèmes distribués et algorithmes distribués 43
Cependant, nous y avons déjà insisté, les hypothèse s usuelles et le modèle standard
de système distribué S du paragraphe 2 restent valides et acceptables dans la seule
perspective d'analyser des algorithmes distribués ; leur validité ne peut se concevoi r que si
l'on s'en tient à ce seul point de vue . L'essentiel est d e ne formuler que des hypothèses —
plus ou moins contraignantes — toujours justifiées, c'est-à-dire rigoureuses et simplifiant
l'analyse de la complexité des algorithmes , sans s'éloigner trop de la réalité. Comme
compromis, nous nous en tiendrons donc, dans la suite, au modèle S proposé en début de
chapitre, sous l'hypothèse d'identités distinctes des processus de S dans la deuxièm e partie
et sous celle de réseaux anonymes dans la troisième.
8. Notes bibliographiques
Grosso modo, c'est le modèle de système distribué défini au paragraphe 2 qui es t le
plus couramment utilisé dans la littérature. Rober Keller (dès 1968/1969 puis en 1976 dans
[KELLER-76]) formalisa le premier « un modèle conceptuel abstrait » pour les systèmes
parallèles centralisés comportant, entre autres, les notions d'« état », d'« occurrence
d'événements » et de « système de transitions » pour des « processus » communicants.
C'est Gérard Le Lann en 1977 [LE LANN -77 ] qui formalisa de son côt é le concept de
« système distribué ». Les notions de système parallèle, de processus séquentiel, de
communication, etc. sont bien entendu abondamment développées et utilisées dans
l'ouvrage classique de C . Anthony Richard Hoare [HOARE-87]. Les concept s de réseau,
d'action et transaction atomiques, d'événement, d'atomicité, etc. ainsi que la notion de
réseau point à point et les hypothèses sur les propriétés des lignes de communicatio n (§ 4)
d'un système distribué sont classiques. Pour plus de précision et d e développement , voir,
parmi beaucoup d'autres, [HOARE-87], [LAVALLÉE-90] et [RAYNAL-87,91].
Le modèle standard de système distribué du paragraphe 2 et la notion d'algorithme
distribué du paragraphe 3 sont majoritairement utilisés dans la littérature spécialisée, à
quelques variantes près, souvent conçues pour les besoin s des analyse s de complexité :
complexité en temp s dans un réseau asynchrone, complexité en moyenne , calculs de bornes
inférieures, etc. (cf. [LAVAULT-90], [BODLAENDER-91 ], etc.).
Le concept de processu s en tant que suite d'événements et la relatio n de causalité dans
l'ensemble des événement s (temps virtuel, etc.) sont bien détaillés dans les travaux de
Colin Fidge [FlDGE-91], Friedemann Mattern [MATTERN-89b] et Gerar d Tel [TEL-91-94].
Les problèmes de synchronicité et de synchronisation ne sont pas traité s per se au
paragraphe 5. Les travaux de Leslie Lamport font bien entendu autorité sur ce sujet ; voir 44 Concepts fondamentaux
entre autres [LAMPORT-78] et, avec Mani Chandy, [CHANDY, LAMPORT-85]. Pour une
approche plus synthétique, on pourra consulter, par exemple, (ANDRÉ, HERMAN,
VERJUS-83] , [LAMPORT, LYNCH-TO] et, surtout, Gerard Tel [TEL-91-94] ("Distributed
Infimum Approximation (DIA): Total Algorithms, DIA-algorithms", etc.). L'apport de
Friedemann Mattern sur ces problèmes est également très important : temps virtuel, états
globaux, horloges vectorielles [MATTERN-89b], terminaison et synchronisation par vague,
etc. Les récents travaux de Bernadette Charron-Bost, Friedemann Mattem et Gerard Tel
[CHARRON-BOST , MATTERN, TEL-91-93] et de Colin Fidge [FlDGE-91] sur la
caractérisation des communications synchrones et asynchrones et la notion de temps
logique représentent également une avancée importante dans ce domaine de recherche.
Les hypothèses de synchronisation virtuelle formulées pour les analyses complexité,
le calcul des bornes inférieures en particulier, sont développées dans [PACHL, KORACH,
ROTEM-84 ] OU [BODLAENDER-88].
Baruch Awerbuch [AWERBUCH-85] avait conçu dès 1985 la notion de synchroniseur
(§ 5) et proposé trois types différents de synchroniseurs, les synchroniseurs a, /3 et /,
chacun réalisant un compromis différent entre la complexité en temps et la complexité en
messages . Ainsi, la complexité en messages du synchroniseur a est en 0(m) et sa
complexité en temps en 0( 1 ), tandis que le synchroniseur /} a une complexité en messages
et en temps en 0(n). La complexité en messages et en temps du synchroniseur y est plus
délicate a exprimer, car fonction des arêtes et de la hauteur d'une partition en une forêt
couvrante du graphe G modélisant le réseau. Voir aussi [EVEN, RAJSBAUM-90 ] et
[MALKA, RAJSBAUM-91] pour la complexité d'une nouvelle notion de synchroniseur,
simple et performante, et [SHABTAY, SEGALL-91] pour des techniques améliorants les
synchroniseurs a, fi et y.
Le synchroniseur 8, fondé sur les propriétés d'un réseau r-couvrant a été conçu par
David Peleg et Jeffrey D. Ullman en 1987 pour l'hypercube, dans la mesure où les
synchroniseurs a, pe t yd'Awerbuch s'avéraient peu performants sur ce type de machine.
C e synchroniseur est donc une construction directement adaptée à l'hypercube et y est
optimal, avec une complexité en temps constante, en 0(1), et une complexité en messages
linéaire, en 0(n). L'originalité de leur travail tient en particulier au fait qu'ils démontrent la
complexité du synchroniseur 8 en utilisant les ensembles absorbants dans un graphe
construits grâce à une notion directement empruntée à la théorie du codage, celle de code et
de distance de Hamming.
Les synchroniseurs (SOS) et (SAD) ("Send on Start" et "Send after Delay") sont dûs
à Ching-Tsun Chou, Israel Cidon, Inder S. Gopal et Shmuel Zaks (1987). Grâce à des
hypothèses de synchronisme total des processus et des lignes de communication, leur

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.