Théorème CAP

Théorème CAP

Le théorème CAP ou CDP, aussi connu sous le nom de théorème de Brewer dit qu'il est impossible sur un système informatique de calcul distribué de garantir en même temps les trois contraintes suivantes[1],[2] :

  • Cohérence : tous les nœuds du système voient exactement les mêmes données au même moment ;
  • Disponibilité (Availability en anglais) : la perte de nœuds n'empêche pas les survivants de continuer à fonctionner correctement ;
  • Résistance au morcellement (Partition Tolerance en anglais) : aucune panne moins importante qu'une coupure totale du réseau ne doit empêcher le système de répondre correctement (ou encore : en cas de morcellement en sous-réseaux, chacun doit pouvoir fonctionner de manière autonome).

D'après ce théorème, un système de calcul distribué ne peut garantir à un instant T que deux de ces contraintes mais pas les trois[3].

Sommaire

Historique

Le théorème part d'une conjecture énoncée à l'Université de Berkeley, en Californie, par le chercheur en informatique Eric Brewer lors du Symposium on Principles of Distributed Computing (PODC, « Symposium sur les principes d'informatique distribuée »)[4]. En 2002, Seth Gilbert et Nancy Lynch du MIT publient une preuve formelle de la vérifiabilité de la conjecture de Brewer, et en font un théorème établi[1].

Illustration

Soit A et B 2 utilisateurs du système, soit N1 et N2 2 nœuds du système. Si A modifie une valeur sur N1, alors pour que B voit cette valeur sur N2 il faut attendre que N1 et N2 soit synchronisés.

Si N1 et N2 doivent toujours servir des valeurs cohérentes, alors il y a un temps incompressible entre le début de l'écriture, la synchro et la lecture suivante. Sur un système très chargé et très gros, ce temps incompressible va considérablement influencer la disponibilité et la résistance au morcellement. Il existe bien évidemment des techniques pour optimiser ce temps mais plus le système est gros, plus il est difficile à réduire.

Références

Lien externe


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorème CAP de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Cap — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Cap », sur le Wiktionnaire (dictionnaire universel) Cap ou CAP peut désigner : Sommaire …   Wikipédia en Français

  • Théorème de baire — Le théorème de Baire, dit aussi lemme de Baire, est un théorème de topologie dû au mathématicien René Baire. Un espace topologique est dit de Baire si toute intersection dénombrable d ouverts denses est dense. De façon équivalente, un espace… …   Wikipédia en Français

  • Theoreme de Banach-Schauder — Théorème de Banach Schauder En analyse fonctionnelle, le théorème de Banach Schauder, également appelé théorème de l application ouverte est un résultat fondamental qui affirme qu une application linéaire continue surjective entre deux espaces… …   Wikipédia en Français

  • Théorème de banach-schauder — En analyse fonctionnelle, le théorème de Banach Schauder, également appelé théorème de l application ouverte est un résultat fondamental qui affirme qu une application linéaire continue surjective entre deux espaces vectoriels normés complets est …   Wikipédia en Français

  • Théorème de l'application ouverte — Théorème de Banach Schauder En analyse fonctionnelle, le théorème de Banach Schauder, également appelé théorème de l application ouverte est un résultat fondamental qui affirme qu une application linéaire continue surjective entre deux espaces… …   Wikipédia en Français

  • Théorème de bayes — Le théorème de Bayes est un résultat de base en théorie des probabilités, issu des travaux du révérend Thomas Bayes et retrouvé ensuite indépendamment par Laplace. Dans son unique article, Bayes cherchait à déterminer ce que l’on appellerait… …   Wikipédia en Français

  • Theoreme de Pascal — Théorème de Pascal Il existe plusieurs théorèmes appelés théorème de Pascal. Sommaire 1 Géométrie 1.1 Théorème de Pascal (direct et réciproque) 1.1.1 Théorème de Pappus Pascal …   Wikipédia en Français

  • Theoreme de van Kampen — Théorème de van Kampen En topologie algébrique, le théorème de van Kampen, également appelé théorème de Seifert Van Kampen, est un résultat permettant de calculer le groupe fondamental d un espace topologique qui se décompose en des espaces plus… …   Wikipédia en Français

  • Théorème de Helly — dans le plan : si trois quelconques des convexes de la famille se rencontrent alors l intersection de tous ces convexes est non vide. Le théorème de Helly est un résultat combinatoire sur les convexes. Ce résultat a été prouvé en 1913 par… …   Wikipédia en Français

  • Théorème de Van Kampen — En topologie algébrique, le théorème de van Kampen, également appelé théorème de Seifert Van Kampen, est un résultat permettant de calculer le groupe fondamental d un espace topologique qui se décompose en des espaces plus simples dont les… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”