N processi comunicanti tramite scambio messaggi.
Canali di comunicazione affidabili.
I processi sono soggetti a fallimenti di tipo crash oppure bizantini.
Il processo pi (i=1 .. N) possiede una propria variabile di decisione di, e propone un proprio valore vi appartenente a un insieme D.
Ciascun processo parte da uno stato di indecisione, e mira a raggiungere uno stato di decisione, in cui il valore di di è immutabile.
I requisiti che devono essere soddisfatti da un algoritmo di consenso distribuito in ogni sua esecuzione sono:
Si possono avere varianti al requisito di integrità: per es., un requisito di integrità più debole richiede che il valore di decisione sia proposto da qualche processo corretto, ma non necessariamente da tutti i processi corretti.
Non esiste alcun algoritmo deterministico in grado di garantire il raggiungimento del consenso in un sistema asincrono a scambio di messaggi anche nel caso di un unico fallimento per crash di un processo.
(Fischer, Lynch, Paterson)
Indebolire la condizione di Termination
Introducendo elementi di non determinismo oppure garantendo la termination esclusivamente durante periodi di sincronismo del sistema.
Indebolire la condizione di Agreement
Individuando un insieme finito per i possibili valori decisionali dei singoli processi.
Irrobustire il modello del sistema
Introducendo dei failure detectors per distinguere i processi lenti (ma corretti) da quelli effettivamente falliti.
“Recent archaeological discoveries on the island of Paxos reveal that the parliament functioned despite the peripatetic propensity of its part-time legislators.
[…]
Early in this millennium, the Aegean island of Paxos was a thriving mercantile center. Wealth led to political sophistication, and the Paxons replaced their ancient theocracy with a parliamentary form of government.
[…]”
Ciascun membro aveva un registro in cui annotare tutte i decreti approvati.
I decreti approvati erano numerati (in ordine crescente).
I parlamentari, così come i messaggeri, potevano entrare ed uscire dal parlamento a piacere.
I messaggeri potevano anche uscire prima di consegnare un messaggio affidatogli, “magari per un viaggio di sei mesi” o “andar via per sempre e il messaggio non veniva consegnato”.
Ma quando in Camera, parlamentari e messaggeri erano dediti al lavoro ed eseguivano prontamente i loro compiti.
C’era molto rispetto e fiducia tanto che si tendeva a far passare ogni decreto proposto.
Ciò poneva un problema:
Ogni parlamentare annotava le leggi su di un proprio registro (con inchiostro indelebile).
I registri di due parlamentari non dovevano contenere informazioni contraddittorie.
Per garantire progresso occorreva che almeno la metà dei legislatori fosse in Camera per un tempo sufficientemente lungo.
In tal caso:
Ogni parlamentare era fornito di:
I matematici dell’isola di Paxos elaborarono un complesso sistema per garantire consistenza e progresso al parlamento.
Tuttavia questo meccanismo aveva un punto di debolezza relativamente all’elezione dei nuovi membri del parlamento, che avveniva utilizzando le regolari procedure del parlamento.
Un giorno, a causa di un errore, fu passata una legge che asseriva che gli unici membri del parlamento erano dei marinai periti in un incidente navale.
Da quel momento il parlamento fu abbandonato e la civiltà di Paxos tramontò rapidamente, finchè un generale di nome Λαμπσων prese possesso dell’isola con un colpo di stato instaurando una dittatura militare che pose fine a secoli di progresso governativo.
Uno tra i valori proposti viene prima o poi scelto.
Se un valore viene scelto, ogni processo prima o poi saprà di tale scelta.
Può essere scelto un valore tra quelli proposti.
Il valore scelto deve essere unico.
Un processo non saprà mai che un valore è stato scelto a meno che esso non sia stato effettivamente scelto.
Ogni processo può svolgere uno o più dei seguenti ruoli:
I processi possono essere eseguiti a velocità arbitrarie (i.e. su macchine diverse), possono fallire e poi riprendere l’esecuzione.
Poiché possono fallire dopo che un valore è stato deciso e poi ripartire, è necessario che ricordino alcune informazioni anche dopo un recovery.
I messaggi non hanno limiti di dimensioni, possono essere duplicati o persi, ma non corrotti.
Il modo più semplice sarebbe quello di avere un solo acceptor.
Sarebbe un SPOF.
Quindi si considera un insieme di acceptor e un valore proposto è accettato se una maggioranza di essi lo accetta.
In assenza di fallimenti o perdite di messaggi, é desiderabile che un valore venga scelto anche se un solo valore viene proposto da un unico proposer.
E’ quindi auspicabile che il seguente requisito venga soddisfatto:
P1: Un acceptor deve accettare la prima proposta che riceve.
Tuttavia, se diversi proposer propongono valori diversi in tempi vicini, ogni acceptor potrebbe scegliere un valore diverso e nessuno sarebbe scelto da una maggioranza.
Viene associato un numero di serie distinto ad ogni proposta ed occorre garantire che:
P2: Se viene scelta una proposta con valore v e numero seriale n, allora ogni proposta scelta con numero seriale n’>n deve avere valore v.
Affinchè un valore sia scelto, deve essere accettato da almeno un acceptor.
Per soddisfare il requisito P2 occorre che:
P2a: Se viene scelta una proposta con valore v e numero seriale n, allora ogni proposta con numero seriale n’>n accettata da un qualsiasi acceptor deve avere valore v.
P1 continua a garantire che una proposta venga scelta.
La comunicazione asincrona può far si che una proposta venga scelta da un acceptor quando altri non hanno ricevuto alcuna proposta.
Un altro proposer potrebbe invece proporre un valore diverso con numero di serie maggiore.
P1 impone di accettare tale valore (che sarebbe il primo ricevuto) andando in contrasto con P2a. Quindi si considera il requisito più forte:
P2b: Se viene scelta una proposta con valore v e numero seriale n, allora ogni proposta con numero seriale n’>n effettuata da un qualsiasi proposer deve avere valore v.
Si supponga che la proposta (m,v) sia stata scelta.
Si vuole che ogni proposta con numero seriale n > m abbia valore v.
È possibile procedere per induzione su n, mostrando che la proposta con numero n ha valore v se ogni proposta con numero in [m;n-1] ha valore v.
Se (m,v) è stata scelta, esiste un insieme C di una maggioranza di acceptor che ha accettato (m,v).
Dunque:
ogni acceptor in C ha accettato una proposta il cui numero è compreso in [m;n-1] e ogni proposta accettata con numero in [m;n-1] ha valore v.
Poiché C costituisce una maggioranza degli acceptors, ogni insieme S costituente una maggioranza degli acceptors deve includere uno degli elementi di C.
Occorre garantire la seguente condizione invariante:
P2c: Per ogni v ed n, se viene effettuata la proposta (n,v), esiste un insieme S di una maggioranza di acceptors tale che
(a) nessun acceptor di S ha accettato una proposta con numero seriale minore di n (v può essere qualsiasi), oppure
(b) v è il valore associato alla proposta con numero seriale più alto tra le proposte con numero minore di n accettate dagli elementi di S.
In questo caso il proposer può proporre un qualsiasi valore perché nessun acceptor in S ha accettato alcuna proposta con numero seriale minore di 2 (il minimo tra i numeri seriale delle proposte accettate è maggiore di 2).
In questo caso il proposer deve proporre β, cioè il valore associato alla proposta con numero seriale più alto tra quelle accettate con numero minore di 27 (5 e 2).
Affinché il requisito P2c sia soddisfatto, quando intende effettuare una proposta con numero n, un proposer deve conoscere:
Mentre conoscere le proposte accettate è abbastanza semplice, prevedere le scelte future degli acceptor è piuttosto complicato…
La promessa degli acceptor di non accettare proposte con numero minore di n può essere sufficiente.
Prepare: il proposer sceglie un numero n ed invia una richiesta ad una maggioranza di acceptors richiedendo:
Accept: se il proposer riceve risposta alla richiesta di prepare da una maggioranza degli acceptors, invia ad essi una richiesta di accept per una proposta con numero n.
Il valore v associato alla proposta può essere:
Gli acceptor possono ricevere due tipi di messaggi: prepare e accept.
Un acceptor può sempre rispondere ad una richiesta di tipo prepare.
Un acceptor può rispondere ad una richiesta di tipo accept, accettando la proposta, solo se non ha promesso a qualche processo di non farlo.
Viene quindi formulato il seguente requisito:
P1a: Un acceptor può accettare una proposta con numero seriale n se e solo se non ha risposto ad una richiesta prepare il cui numero è maggiore di n.
Un acceptor può ignorare una richiesta prepare per la quale non è in grado di effettuare una promessa.
Un acceptor può ignorare richieste prepare relative a proposte già accettate (messaggi duplicati).
Ogni acceptor è quindi tenuto a mantenere in memoria stabile (così da soddisfare l’invariante P2c anche in seguito al riavvio dopo un fallimento):
Può essere dimostrato che la fase 2 dell’algoritmo ha il minor costo possibile per un algoritmo di consenso in presenza di fallimenti.
In altri termini, Paxos può essere considerato l’ottimo.
[Keidar, Rajsbaum – “On the cost of fault-tolerant consensus when there are no faults” – SIGACT News 32(2), 2001]
In questa fase entrano in gioco i processi learner.
Sono possibili diverse strategie:
1. Ogni acceptor informa tutti i learner circa l’accettazione di un valore.
2. Gli acceptor informano un solo learner distinto, che poi informa tutti gli altri learner.
3. Gli acceptor informano un sottoinsieme di learner che poi provvedono ad informare gli altri learner.
Il progresso non è garantito.
Per garantire la liveness si può eleggere un proposer distinto.
Esso deve essere l’unico processo autorizzato ad effettuare proposte (e quindi ad inviare i messaggi prepare).
Se non si verifica un numero eccessivo di guasti nelle restanti componenti del sistema (proposers, acceptors e rete di comunicazione), è possibile raggiungere il consenso con un singolo proposer.
Del resto sappiamo che
Non esiste alcun algoritmo deterministico in grado di garantire il raggiungimento del consenso in un sistema asincrono a scambio di messaggi anche nel caso di un unico fallimento per crash di un processo.
Per cui occorre un algoritmo per l’elezione del proposer distinto, il quale richiede l’introduzione di casualità o timeouts.
La Liveness è pertanto garantita esclusivamente durante i periodi di sincronia del sistema.
La Safety invece viene garantita a prescindere dalla sincronia.
Solitamente, ogni processo nel sistema svolge i tre ruoli.
Si considera un leader che funge da distinguished proposer.
Nel caso di proposer distinti, per garantire che non vengano effettuate proposte con lo stesso numero, essi scelgono i numeri da insiemi (ordinati) disgiunti.
Ciascun proposer deve memorizzare la proposta con numero seriale più alto (così da iniziare la fase 1 con un numero maggiore di ogni altro usato).
Servizio alla base dell’infrastruttura di Google che offre:
Si assume che i server replica operino a velocità differenti e possano fallire.
Ogni server replica ha accesso ad una memoria stabile.
I messaggi possono essere persi, riordinati, duplicati, richiedere un tempo indeterminato per la consegna ma non essere corrotti.
In Chubby l’agreement consiste nel far si che ciascuna replica abbia lo stesso valore (cioè la stessa operazione) in corrispondenza di una data entry nei file di log.
1. Caratterizzazione dei sistemi distribuiti
2. Modelli di sistemi distribuiti
3. Tempo e sincronizzazione nei Sistemi Distribuiti
4. Stato globale nei Sistemi Distribuiti
5. Problemi di consenso nei sistemi distribuiti
7. Algoritmi di mutua esclusione nei sistemi distribuiti
8. Algoritmi di elezione nei sistemi distribuiti
10. Il Network File System di SUN Microsystems
11. AFS (Andrew File System) e GFS (Google File System)
12. Transazioni e controllo di concorrenza
13. Transazioni
15. Affidabilità (dependability) dei sistemi software distribuiti
16. Affidabilità dei sistemi software distribuiti
17. Software Faults
18. Classificazione e analisi dei difetti software
L. Lamport, The Part Time Parliament – ACM Transactions on Computer Systems, Vol. 16 Issue 2, May 1998
L. Lamport, Paxos Made Simple – ACM SIGACT News (Distributed Computing Column) Vol. 32, Issue 4, December 2001