ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 30/7 - 2011  - pp.777-779
TITRE
ÉDITORIAL

RÉSUMÉ

« Un système distribué est un système où la défaillance d’une machine dont vous ignoriez l’existence peut rendre votre propre machine inutilisable ». Cette citation restée célèbre de Leslie Lamport rend parfaitement compte de l’évolution de l’algorithmique distribuée. Alors que la motivation initiale pour la distribution des calculs tenait principalement à l’amélioration des performances globales ou à la réduction des coûts, tous les travaux récents du domaine prennent en compte une notion plus ou moins élaborée d’adversaire.

L’algorithmique distribuée est l’algorithmique des réseaux et des systèmes distribués. Dans un algorithme distribué, les machines qui participent au calcul collaborent à une tâche commune malgré des informations qui ne peuvent s’échanger que localement, malgré des vitesses de calcul et de communication qui diffèrent parfois significativement, malgré des connaissances sur le système global qui ne sont que parcellaires, malgré des pannes de certaines de ces machines qui surviennent inopinément, malgré des attaques sur des machines critiques qui surviennent au pire moment, malgré des machines qui vont et qui viennent au gré de la volonté de leurs utilisateurs. En somme, il s’agit pour ces machines de collaborer malgré l’adversité.

Les chercheurs qui étudient les algorithmes séquentiels classiques différencient les problèmes suivant qu’il existe ou non un algorithme pour trouver une solution à ce problème, et proposent une hiérarchie de classes de complexité pour séparer ce qui est « théoriquement » calculable de ce qui est « pratiquement » calculable. Les chercheurs qui étudient les algorithmes distribués ne considèrent que des problèmes qui admettent une solution séquentielle (souvent pratiquement calculable voire trivialement calculable), et différencient les problèmes suivant les adversaires qui permettent de les résoudre d’une part (c’est-à-dire que ces adversaires sont suffisamment faibles pour qu’un algorithme distribué résolvant le problème puisse exister) des adversaires qui rendent toute tentative de résolution algorithmique du problème impossible d’autre part. L’efficacité d’une solution s’évalue alors suivant deux critères orthogonaux : l’adversaire toléré et les ressources utilisées pour tolérer cet adversaire. Un algorithme sera plus flexible qu’un autre s’il est capable de tolérer un adversaire plus général (i.e. plus puissant), et donc susceptible de résoudre un problème donné dans un plus grand nombre de contextes. Pour un adversaire donné, un algorithme sera plus performant qu’un autre s’il utilise moins de ressources (mémoire, temps de calcul, quantité d’information échangée, etc.) dans le même contexte.



AUTEUR(S)
Sébastien TIXEUIL

LANGUE DE L'ARTICLE
Français

 PRIX
GRATUIT
   
ACCÉDER A L'ARTICLE COMPLET  (101 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier