Lethéorème CAP ou CDP, aussi connu sous le nom dethéorème de Brewer, dit qu'il est impossible sur un systèmeinformatique decalcul distribué de garantir en même temps (c'est-à-dire de manièresynchrone) les trois contraintes suivantes[1],[2] :
Cohérence (Consistency en anglais) : tous les nœuds du système voient exactement les mêmes données au même moment ;
Disponibilité (Availability en anglais) : garantie que toutes les requêtes reçoivent une réponse ;
Tolérance au partitionnement[Note 1] (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/stockage distribué ne peut garantir à un instantt que deux de ces contraintes mais pas les trois[3].
La meilleure solution connue pour l'arbitrage AP (disponibilité et partitionnement) est d'utiliser un modèle de cohérence relaxé tel quecohérence éventuelle forte (Strong Eventual Consistency, SEC), dont lestypes de données répliqués sans conflit sont une implémentation.
Le théorème part d'uneconjecture énoncée par le chercheur en informatiqueEric Brewer de l'université de Californie à Berkeley lors duSymposium on Principles of Distributed Computing (PODC, « Symposium sur les principes d'informatique distribuée »)[4],[1]. En 2002, Seth Gilbert etNancy Lynch duMIT publient une preuve formelle de la vérifiabilité de la conjecture de Brewer, et en font un théorème établi[1].
Soit A et B deux utilisateurs du système, soit N1 et N2 deux nœuds du système. Si A modifie une valeur sur N1, alors pour que B voie cette valeur sur N2, il faut attendre que N1 et N2 soient 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 synchronisation et la lecture suivante. Sur un système très chargé et très vaste, 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 vaste, plus il est difficile à réduire.
Exemple d'arbitrage qu'implique le théorème CAP : deux utilisateurs qui font une même recherche sur un même moteur de recherche peuvent obtenir des résultats différents, mais on peut considérer que cet inconvénient est moins grave que de ne pas avoir de résultats du tout[5].
↑Dans cette définition, le terme « partitionnement » ne doit pas être compris au sens que, dans une base, un objet peut être scindé en plusieurs destinations de stockage, mais comme des machines distinctes (appelées généralement nœuds) possédant chacune une partie des données tel que, seul, l’ensemble des nœuds permet de reconstituer l’intégralité des données de la base.
