Il teorema CAP, è uno dei teoremi fondamentali dei sistemi distribuiti. Iniziato come una congettura fatta dal computer scientist Brewer (e per questo conosciuto anche come Brewer’s theorem), è diventato un teorema grazie a Seth Gilbert e Nancy Lynch del MIT i quali hanno dimostrato formalmente la congettura.
Sostanzialmente dice che un sistema distribuito può avere al massimo due di queste tre proprietà:

  • Consistenza (Consistency): Ogni richiesta di lettura effettuata da qualunque nodo per lo stesso dato, porta allo stesso valore (o uno più aggiornato).
  • Disponibilità (Availability): Ad ogni richiesta corrisponde una risposta. Ma senza la garanzia di ricevere risposte corrette (ovvero che le nostre letture siano coerenti).
  • Tolleranza di partizione (Partition Tolerance): Il sistema continua ad operare nonostante arbitrarie perdite di messaggi fra i nodi.

Il teorema CAP afferma che un sistema distribuito non può essere contemporaneamente consistente, disponibile e tollrante al partizionamento. Vediamo prima quindi nel dettaglio in cosa consistono queste proprietà.

Un semplice sistema distribuito

Consideriamo quindi un semplice sistema distribuito. Il nostro sistema di esempio, è composto da due sever G_1 e G_2. Entrambi i server sono incaricati di tenere traccia di una unica variabile v, il cui valore iniziale è v_0. G_1 e G_2 possono comunicare tra di loro o con un client esterno.

Possiamo quindi visualizzare il nostro sistema così:

Un client può richiedere di scrivere (write) o leggere (read) la variabile v ad entrambi i server. Quando un server riceve una richiesta, esegue la computazione necessaria e genera una risposta al client.

Ecco quindi un esempio di scrittura (write):

Ed un esempio di lettura (read):

Stabilite le caratteristiche del nostro sistema, passiamo a vedere nel dettaglio le proprietà di consistenza, disponibilità e tolleranza al partizionamento.

Consistenza

Vediamo come Gilber e Lynch definiscono nel loro paper la consistenza:

Qualunque operazione di lettura che inizia dopo una operazione di scrittura completata, deve ritornare quel valore o il risultato della successiva scrittura.

In un sistema consistente quando un client scrive un valore in un qualunque server e riceve una risposta di conferma, si aspetta che le successive richieste di lettura risultino nel valore da lui scritto o un valore aggiornato (ad esempio da un altro client) indipendentemente dal server interrogato.
Vediamo un esempio di sistema inconsistente:

Il client scrive v_1 su G_1 che risponde con un ack (done). Quando però il client invia una richiesta di lettura a v_2, riceve dei dati non aggiornati: ovvero v_0.

Vediamo quindi un esempio di sistema consistente:

In questo sistema, G_1 replica il valore ricevuto su G_2 prima di rispondere con un ack al client. In questo modo, quando il client invia una lettura verso G_2, riceve il valore più aggiornato: ovvero v_1.

Disponibilità

Vediamo come Gilbert e Lynch descrivono la disponibilità di un sistema:

Ogni richiesta ricevuta da un nodo non fallito nel sistema, deve ricevere una risposta.

In un sistema ad alta disponibilità, se il client invia una richiesta ed il server non è crashato, allora deve ricevere una risposta. Il server non può ignorare le richieste del client.

Tolleranza al partizionamento

Gilbert e Lynch descrivono la proprietà di partition tolerance come:

Alla rete è permesso perdere un numero arbitrario di messaggi inviati da un nodo all’altro.

Questo significa che uno o più messaggi scambiati fra G_1 e G_2 potrebbe andare persi. Ammesso che tutti i messaggi vengano scartati, il sistema assomiglierebbe a questo:

Se possiede la proprietà di partition tolerance, il nostro sistema deve riuscire a funzionare correttamente nonostante partizioni del network arbitrarie.

Dimostrazione del teorema

Dopo aver visto brevemente le proprietà di consistenza, disponibilità e tolleranza al partizionamento possiamo finalmente provare che un sistema distribuito non può possederle contemporaneamente tutte e tre.
La dimostrazione procede per assurdo: assumiamo che esista un sistema che possieda tutte e tre le proprietà.

Iniziamo creando una partizione del sistema:

Un cliente invia a G_1 un comando di write per il valore v_1. Visto che il nostro sistema è disponibile, G_1 è obbligato a risponderci. Visto che la rete è partizionata però, G_1 non può replicare il valore appena scritto su G_2. Gilbert e Lnch chiamano questa fase di esecuzione con \alpha_1.

In seguito, il nostro client invia una richiesta di lettura verso G_2. Visto che il sistema è dispoibile, G_2 è costretto a rispondere. Visto che la rete è partizionata però, G_2 on ha potuto aggiornare il suo valore da G_1. Per questo motivo, ritornerà il valore v_0.
Gilbert e Lynch chiamano questa fase di esecuzione \alpha_2.

Ritornando il valore v_0 nonostante il client abbia inviato una write con un valore più aggiornato, G_2 rompe la proprietà di consistenza.

Visto che abbiamo assunto consistenza, disponibilità e tolleranza al partizionamento possano esistere contemporaneamente in un sistema, mostrando un esempio di esecuzione che rompe la proprietà di consistenza abbiamo dimostrato che non è possibile possederle tutte e tre insieme.

Per approfondire

Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services
Le immagini sono prese da: https://mwhittaker.github.io/blog/an_illustrated_proof_of_the_cap_theorem/