Chord

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Réseau Chord à 16 nœuds.

Chord est un réseau de recouvrement de type table de hachage distribuée pour les réseaux pair à pair (P2P). Chord est une des premières tables de hachage distribuées, parmi CAN, Tapestry, and Pastry. Chord a été présenté en 2001 par Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, et Hari Balakrishnan, et a été développé au MIT[1].

Il a pour particularité de disposer d'algorithmes d'une complexité d'au plus \mathcal{O}(\log N) requêtes pour trouver une information dans un anneau de N éléments.

Avantages[modifier | modifier le code]

  • Décentralisé
    Chord est complètement décentralisé, tous les nœuds sont au même niveau. Ce qui le rend robuste et adapté aux applications P2P peu organisées[1].
  • Passage à l'échelle
    Le coût d'une recherche est fonction du logarithme du nombre de nœuds[1].
  • Équilibrage de charge
    Équilibrage de charge naturel, hérité de la Fonction de hachage (SHA-1)[1].
  • Disponibilité
    On peut toujours trouver le nœud responsable d'une clef, même lorsque le système est instable[1].
  • Aucune contrainte sur le nom des clefs[1].

Inconvénients[modifier | modifier le code]

  • Sécurité
    Un ensemble de participants mal intentionnés ou buggés peut offrir une vue incorrecte de l'anneau[1].
  • Mal adapté au réseau sous-jacent
    2 pairs voisins sur l'anneau peuvent être de part et d'autre du globe. Les pairs voisins ont plus de messages à s'envoyer[2] que deux pairs quelconques.

Notes[modifier | modifier le code]

  1. a, b, c, d, e, f et g (en) I. Stoica, R. Morris, D. Karger, M. F. Kaashoek et H. Balakrishnan, « Chord: A scalable peer-to-peer lookup service for internet applications », ACM SIGCOMM Computer Communication Review, vol. 31, no 4,‎ , p. 149 (DOI 10.1145/964723.383071, lire en ligne)
  2. cf détails de l'algorithme, pas encore présent sur la version française de la page

Annexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]