Tag Archives: sistemi distribuiti

Il problema del consenso distribuito: l’algoritmo Paxos, step-by-step

Nei sistemi distribuiti, una serie di macchine sono in grado di raggiungere un consenso su una decisione che è estremamente importante. I sistemi di database, ad esempio, devono assicurare che tutte le macchine siano d’accorso se effettuare un commit o il rollback di una transazione, in modo che ogni macchina abbia una visione coerente dei dati (si immagini ad esempio il problema sul proprio conto bancario. Una macchina pensa che tu abbia 1000 euro sul tuo conto, ma un’altra macchina crede che tu abbia il conto vuoto).

Il consenso è difficile da raggiungere, perché i messaggi tra le macchine possono essere persi o ritardati in modo indefinito, oppure le macchine stesse possono fallire – come fa una macchina a sapere se un’altra macchina ha elaborato un messaggio?

Solitamente si utilizza il Commit a due fasi (Two-phase commit), ma ha un problema – se il nodo coordinatore di una transazione fallisce, il sistema rimane bloccato fino a quando questo nodo non si riavvia. Il commit a tre fasi risolve questo problema del blocco, ma fa sempre affidamento su un unico coordinatore.

In questo articolo, si discute Paxos, un protocollo distribuito alternativo al commit a due fasi e a quello a tre fasi. Paxos garantisce che i nodi sceglieranno sempre e solo un singolo valore (quindi garantisce la safety), ma non garantisce che un valore verrà scelto se la maggioranza dei nodi non sono disponibili (progress). Gli algoritmi di consenso hanno come obiettivo la safety, perché non importa se si faccia un commit o un rollback – ma è di fondamentale importanza che una sola risposta sia scelta.

Continue reading Il problema del consenso distribuito: l’algoritmo Paxos, step-by-step