- 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
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « CAP theorem » (voir la liste des auteurs)
- (en) [PDF] Lynch, Nancy, et Seth Gilbert : « Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. » in ACM SIGACT News, v. 33 N°2, 2002, p. 51-59.
- (en) julianbrowne.com : Brewer's CAP Theorem. Consulté le 2 mars 2010.
- (en) royans.net : Brewers CAP theorem on distributed systems.
- (en) Brewer, Eric : Towards Robust Distributed Systems.
Lien externe
- (en) Problems with CAP, and Yahoo's little known NoSQL system par Daniel Abadi.
Catégories :- Calcul distribué
- Théorème d'informatique
- Disponibilité (informatique)
Wikimedia Foundation. 2010.