Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 27.Esercitazione - Protocollo per il consenso Paxos


Sommario

  • Il problema del consenso
  • Paxos ed il Parlamento part-time
  • Presentazione del protocollo
  • Requisiti per la proposta e l’accettazione di un valore
  • Il protocollo
  • Progresso in Paxos
  • Esempi di utilizzo dell’algoritmo

Il problema del consenso

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.

Requisiti

I requisiti che devono essere soddisfatti da un algoritmo di consenso distribuito in ogni sua esecuzione sono:

  • Terminazione (termination): prima o poi ogni processo corretto prende una decisione
  • Accordo (agreement): due qualsiasi processi corretti non decidono diversamente
  • Integrità (integrity): se tutti i processi corretti propongono lo stesso valore, la decisione finale di ogni processo corretto corrisponde a quel valore

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.

Garanzia in sistemi asincroni (FLP)

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)

Sistemi asincroni

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.

Paxos island

“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.
[…]”

Parlamento part-time

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.

Parlamento part-time

Ciò poneva un problema:

  • se dei parlamentari decretavano che “37. è proibito dipingere sulle pareti del Tempio” per poi abbandonare il parlamento per un banchetto, un altro gruppo di legislatori appena entrato in parlamento, e ignari di quanto appena deciso, poteva far passare il decreto, in conflitto con il precedente “37. è garantita libertà d’espressione artistica”.

Ogni parlamentare annotava le leggi su di un proprio registro (con inchiostro indelebile).
I registri di due parlamentari non dovevano contenere informazioni contraddittorie.

Parlamento part-time

Per garantire progresso occorreva che almeno la metà dei legislatori fosse in Camera per un tempo sufficientemente lungo.
In tal caso:

  • ogni legge proposta da un parlamentare era prima o poi promulgata (ovvero ratificata da una maggioranza di parlamentari)
  • ogni legge ratificata appariva nel registro di ogni parlamentare

Parlamento part-time

Ogni parlamentare era fornito di:

  • un registro sul quale annotare le leggi promulgate
  • una penna ad inchiostro indelebile per scrivere sul suddetto registro
  • tutti i messaggeri di cui necessitava per comunicare con gli altri parlamentari
  • una clessidra
  • fogli di carta secondo necessità

La fine di Paxos

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.

Analogie con il problema del consenso


Liveness

Uno tra i valori proposti viene prima o poi scelto.
Se un valore viene scelto, ogni processo prima o poi saprà di tale scelta.

Safety

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.

Ruoli dei processi

Ogni processo può svolgere uno o più dei seguenti ruoli:

  • Proposer: svolge tale ruolo un processo che ha la facoltà di proporre un valore
  • Acceptor: svolge tale ruolo un processo che ha la facoltà di accettare un valore precedentemente proposto da un proposer
  • Learner: svolge tale ruolo un processo che ha la facoltà di apprendere la scelta di un valore effettuata da un acceptor

Processi e messaggi

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.

Scelta di un valore

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.

Scelta di un valore

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.

Scelta di un valore

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.

Scelta di un valore

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.

Soddisfare P2b

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.

Soddisfare P2b

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.

Esempio

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).


Esempio

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).


Generazione delle proposte

Affinché il requisito P2c sia soddisfatto, quando intende effettuare una proposta con numero n, un proposer deve conoscere:

  1. il valore della proposta con numero seriale più alto minore di n accettato da ogni acceptor in una maggioranza
  2. il valore della proposta con numero seriale più alto minore di n che sarà accettato da ogni acceptor in una maggioranza

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.

Generazione delle proposte

Prepare: il proposer sceglie un numero n ed invia una richiesta ad una maggioranza di acceptors richiedendo:

  • la promessa di non accettare mai una richiesta con numero seriale inferiore a n (promise), se possibile, e
  • il valore della proposta già accettata con il più grande numero seriale minore di n, se presente

Generazione delle proposte

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:

  • il valore della proposta con numero seriale più alto tra quelle riportate dagli acceptors
  • un qualsiasi valore, nel caso in cui le risposte non riportavano di una proposta precedente

Esempio


Esempio


Esempio


Esempio


Comportamento degli acceptor

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.

Comportamento degli acceptor

Un acceptor può ignorare una richiesta prepare per la quale non è in grado di effettuare una promessa.

  • Ovvero può non rispondere a richieste di tipo prepare(m) ove sia stato già inviato un messaggio promise(n) con n>m.

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):

  • la proposta di numero seriale più elevato accettata
  • il numero seriale delle richiesta prepare con numero maggiore a cui ha risposto con un messaggio promise

Algoritmo

  • Un Proposer seleziona un numero di proposta n ed invia una richiesta prepare(n) ad una maggioranza di acceptors.
  • Quando un acceptor riceve una prepare(n), se n è maggiore di ogni altra prepare a cui ha già riposto, risponde con una promise di non accettare più proposte con numero seriale minore di n e con il valore della proposta già accettata con numero più grande.

Algoritmo

  • Se il proposer riceve un messaggio promise(n,v) da una maggioranza degli acceptors, invia un messaggio accept(n,v) a tali acceptors, dove v è il valore della proposta con numero seriale più alto tra quelle riportate dagli acceptors, ovvero un qualsiasi valore, nel caso in cui le risposte non riportavano di una proposta precedente.
  • Se un acceptor riceve un messaggio accept(n,v), accetta la proposta a meno che non abbia già risposto ad una richiesta prepare avente numero seriale maggiore di n.

Osservazione

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]

Apprendimento

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.

Esempio

1. Ogni acceptor informa tutti i learner circa l’accettazione di un valore.

  • # msg = NA*NL.
  • Tollera il crash di NL-1 learner.

Esempio

2. Gli acceptor informano un solo learner distinto, che poi informa tutti gli altri learner.

  • # msg = NA+NL-1.
  • In caso di crash del learner distinto il valore scelto viene perso.

Esempio

3. Gli acceptor informano un sottoinsieme di learner che poi provvedono ad informare gli altri learner.

  • # msg = NA*N’L + N’L *(NL -N’L)
  • Tollera il crash di N’L-1 learner.

Progresso

Il progresso non è garantito.

  • Il proposer p completa la fase 1 per una proposta con numero n1
  • Un altro proposer q completa la fase 1 con una proposta con numero n2>n1
  • Durante la fase 2, le accept di p sono ignorate poiché gli acceptor hanno promesso di non accettare proposte con numero minore di n2
  • Quindi p ricomincia la fase 1 con una proposta con numero n3>n2
  • Le accept inviate da q con numero n2 saranno ignorate (gli acceptor nel frattempo hanno fatto promessa a p di non accettare proposte con numero minore di n3)
  • q fa una proposta con numero n4>n3

Progresso

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.

Implementazione

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).

Chubby

Servizio alla base dell’infrastruttura di Google che offre:

  • lock distribuiti per la sincronizzazione delle attività distribuite
  • file System per lo storage affidabile di piccoli file (complementare a GFS)
  • supporto all’elezione di primary replica in GFS
  • Name Service.

Chubby

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.

Chubby

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.

I materiali di supporto della lezione

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

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion