Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Théorème CAP
Résumé
thumb|Représentation des contraintes du 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 (c'est-à-dire de manière synchrone) les trois contraintes suivantes :
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 (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).
Attention : 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.
D'après ce théorème, un système de calcul/stockage distribué ne peut garantir à un instant t que deux de ces contraintes mais pas les trois.
Le théorème part d'une conjecture énoncée par le chercheur en informatique Eric Brewer de l'université de Californie à Berkeley lors du Symposium on Principles of Distributed Computing (PODC, « Symposium sur les principes d'informatique distribuée »). 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.
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 voit 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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.