{"id":37335,"date":"2019-10-31T22:17:01","date_gmt":"2019-10-31T19:17:01","guid":{"rendered":"https:\/\/prohoster.info\/blog\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah\/"},"modified":"2019-10-31T22:17:01","modified_gmt":"2019-10-31T19:17:01","slug":"kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","status":"publish","type":"post","link":"https:\/\/prohoster.info\/it\/blog\/administrirovanie\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","title":{"rendered":"Il gatto di Schr\u00f6dinger senza scatola: il problema del consenso nei sistemi distribuiti","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Immagina. In una stanza ci sono 5 gatti rinchiusi, e per andare a svegliare il padrone devono prima accordarsi tutti insieme, poich\u00e9 possono aprire la porta solo in cinque spingendosi contro di essa. Se uno dei gatti \u00e8 il gatto di Schr\u00f6dinger e gli altri non sono a conoscenza della sua decisione, sorge la domanda: \"Come possono farlo?\" <\/p>\n

In questo articolo spiegher\u00f2 in termini semplici la componente teorica del mondo dei sistemi distribuiti e i principi su cui si basano. Inoltre, esaminer\u00f2 brevemente l'idea principale alla base di Paxos. <\/p>\n

\"Il
\n<\/a><\/noindex>
\nQuando gli sviluppatori utilizzano infrastrutture cloud, diverse basi di dati e lavorano in cluster di numerosi nodi, sono certi che i dati saranno interi, sicuri e sempre accessibili. Ma da dove provengono le garanzie?<\/p>\n

Di fatto, le garanzie che abbiamo sono quelle fornite dal fornitore. Vengono descritte nella documentazione all'incirca in questo modo: \"Questo servizio \u00e8 sufficientemente affidabile, ha un SLA definito, non preoccuparti, tutto funzioner\u00e0 distribuito come ti aspetti\". <\/p>\n

Tendiamo a credere nel meglio, poich\u00e9 i grandi esperti delle grandi aziende ci hanno assicurato che tutto andr\u00e0 per il verso giusto. Non ci poniamo la domanda: perch\u00e9, per l'appunto, questo dovrebbe funzionare? C'\u00e8 una qualche giustificazione formale per la correttezza del funzionamento di tali sistemi?<\/p>\n

Recentemente sono stato a una scuola di calcolo distribuito<\/a><\/noindex> e sono stato molto ispirato da questo argomento. Le lezioni nella scuola assomigliavano pi\u00f9 a corsi di analisi matematica piuttosto che a qualcosa legato a sistemi computerizzati. Ma \u00e8 esattamente cos\u00ec che un tempo venivano dimostrati i pi\u00f9 importanti algoritmi che utilizziamo ogni giorno, senza neanche rendercene conto. <\/p>\n

Nella maggior parte dei moderni sistemi distribuiti viene utilizzato l'algoritmo di consenso Paxos e le sue varie modifiche. La cosa pi\u00f9 interessante \u00e8 che la validit\u00e0 e, in linea di principio, la possibilit\u00e0 stessa di esistenza di questo algoritmo possono essere dimostrate semplicemente con una penna e della carta. Nel pratico, per\u00f2, l'algoritmo \u00e8 applicato in grandi sistemi che operano su un numero elevato di nodi nelle nuvole. <\/p>\n

Un'illustrazione leggera di ci\u00f2 di cui si parler\u00e0 in seguito: il problema dei due generali<\/b>Per riscaldarci, analizziamo il problema dei due generali<\/a><\/noindex>. <\/p>\n

Ci sono due eserciti: uno rosso e uno bianco. Le forze bianche sono basate nella citt\u00e0 assediata. Le forze rosse, comandate dai generali A1 e A2, si trovano ai due lati della citt\u00e0. L'obiettivo dei rossi \u00e8 attaccare la citt\u00e0 bianca e vincere. Tuttavia, l'esercito di ciascun generale rosso \u00e8 pi\u00f9 piccolo rispetto a quello dei bianchi.<\/p>\n

\"Il
\n
\nLe condizioni per la vittoria dei rossi: entrambi i generali devono attaccare simultaneamente per avere un vantaggio numerico sui bianchi. Per questo, i generali A1 e A2 devono mettersi d'accordo tra di loro. Se ciascuno attacca separatamente, i rossi perderanno. <\/p>\n

Per mettersi d'accordo, i generali A1 e A2 possono inviare messaggeri l'uno all'altro attraverso il territorio della citt\u00e0 bianca. Un messaggero pu\u00f2 arrivare con successo al generale alleato o pu\u00f2 essere intercettato dal nemico. La domanda \u00e8: esiste una sequenza di comunicazioni tra i generali rossi (sequenza di invio dei messaggeri da A1 a A2 e viceversa da A2 a A1), in cui possano garantire di concordare l'attacco all'ora X. Qui, per garanzie si intende che entrambi i generali abbiano una conferma inequivocabile che l'alleato (l'altro generale) attaccher\u00e0 sicuramente all'ora X.<\/p>\n

Supponiamo che A1 invii un messaggero a A2 con il seguente messaggio: \u00abAttacchiamo oggi a mezzanotte!\u00bb. Il generale A1 non pu\u00f2 attaccare senza la conferma del generale A2. Se il messaggero di A1 \u00e8 arrivato, il generale A2 invia una conferma con il messaggio: \u00abS\u00ec, attacchiamo oggi, abbattiamo i bianchi\u00bb. Ma ora il generale A2 non sa se il suo messaggero sia arrivato o meno, non ha garanzie che l'attacco avverr\u00e0 simultaneamente. Ora il generale A2 ha bisogno nuovamente di una conferma.<\/p>\n

Se approfondiamo ulteriormente la loro comunicazione, scopriremo che, per quanti cicli di scambio messaggi ci siano, non c'\u00e8 modo di garantire che entrambi i generali siano stati informati della ricezione dei loro messaggi (a condizione che uno qualsiasi dei messaggeri possa essere intercettato).<\/p>\n

Il problema dei due generali \u00e8 un'ottima illustrazione di un sistema distribuito molto semplice, dove ci sono due nodi con comunicazione inaffidabile. Quindi non abbiamo la garanzia del 100% che essi si sincronizzino. Si parler\u00e0 di problemi simili su una scala molto pi\u00f9 ampia pi\u00f9 avanti nell'articolo.<\/p>\n

Introduciamo il concetto di sistemi distribuiti<\/h2>\n

\nUn sistema distribuito \u00e8 un insieme di computer (da ora in poi chiamati nodi) che possono scambiarsi messaggi. Ogni nodo \u00e8 un'entit\u00e0 autonoma. Un nodo pu\u00f2 elaborare compiti in modo indipendente, ma per interagire con altri nodi deve inviare e ricevere messaggi. <\/p>\n

Come vengono implementati i messaggi e quali protocolli vengono utilizzati non ci interessa in questo contesto. \u00c8 importante che i nodi di un sistema distribuito possano scambiarsi dati inviando messaggi.<\/p>\n

La definizione stessa non sembra molto complessa, ma bisogna considerare che un sistema distribuito ha una serie di attributi che saranno importanti per noi.<\/p>\n

Attributi dei sistemi distribuiti<\/h4>\n

<\/p>\n

    \n
  1. Concorrenza<\/b> \u2013 la possibilit\u00e0 che si verifichino eventi simultanei o concorrenti nel sistema. Inoltre, considereremo che gli eventi che si verificano su due nodi diversi sono potenzialmente concorrenti fino a quando non abbiamo un ordine definitivo di insorgenza di questi eventi. E, come regola, di solito non abbiamo tale ordine.<\/li>\n
  2. Assenza di orologi globali<\/b>. Non abbiamo un ordine preciso degli eventi a causa dell'assenza di orologi globali. Nel mondo normale degli esseri umani, siamo abituati a avere orologi e tempo definito. Tutto cambia quando si parla di sistemi distribuiti. Anche gli orologi atomici pi\u00f9 precisi presentano un drift, e ci possono essere situazioni in cui non possiamo dire quale dei due eventi sia avvenuto per primo. Pertanto, non possiamo nemmeno fare affidamento sul tempo.<\/li>\n
  3. Guasto indipendente dei nodi del sistema<\/b>. C'\u00e8 un altro problema: qualcosa pu\u00f2 andare storto semplicemente perch\u00e9 i nostri nodi non sono eterni. Un disco rigido pu\u00f2 guastarsi, una macchina virtuale nel cloud pu\u00f2 riavviarsi, la rete pu\u00f2 lampeggiare e i messaggi possono andare persi. Inoltre, possono verificarsi situazioni in cui i nodi funzionano, ma lavorano contro il sistema. L'ultimo classe di problemi ha persino ricevuto un nome specifico: problema dei generali bizantini<\/a><\/noindex>. Il pi\u00f9 popolare esempio di un sistema distribuito con tale problema \u00e8 il Blockchain. Ma oggi non esamineremo questa particolare classe di problemi. Ci interesseranno situazioni in cui uno o pi\u00f9 nodi possono semplicemente guastarsi.<\/li>\n
  4. Modelli di comunicazione (modelli di scambio di messaggi) tra nodi<\/b>. Abbiamo gi\u00e0 stabilito che i nodi comunicano tramite scambi di messaggi. Ci sono due modelli di scambio di messaggi ben noti: sincrono e asincrono.<\/li>\n<\/ol>\n

    <\/p>\n

    Modelli di comunicazione tra nodi in sistemi distribuiti<\/h4>\n

    \nModello sincrono<\/b> \u2013 sappiamo con certezza che esiste una delta di tempo finita, entro la quale il messaggio arriva garantito da un nodo all'altro. Se questo tempo scade e il messaggio non \u00e8 arrivato, possiamo affermare con certezza che il nodo \u00e8 fuori uso. In questo modello abbiamo un tempo di attesa prevedibile. <\/p>\n

    Modello asincrono<\/b> \u2013 nei modelli asincroni consideriamo che il tempo di attesa sia finito, ma non esiste una delta di tempo dopo la quale possiamo garantire che il nodo sia fuori uso. Cio\u00e8, il tempo di attesa per un messaggio da un nodo pu\u00f2 essere arbitrariamente lungo. Questa \u00e8 una definizione importante, e ne parleremo in seguito. <\/p>\n

    Il concetto di consenso nei sistemi distribuiti<\/h2>\n

    \nPrima di definire formalmente il concetto di consenso, consideriamo un esempio di situazione in cui \u00e8 necessario, ovvero \u2013 Replica di macchine di stato<\/b>. <\/p>\n

    Abbiamo un certo registro distribuito. Vorremmo che fosse coerente e contenesse dati identici su tutti i nodi del sistema distribuito. Quando uno dei nodi apprende un nuovo valore che intende registrare nel registro, il suo compito \u00e8 proporre questo valore a tutti gli altri nodi, affinch\u00e9 il registro venga aggiornato su tutti i nodi e il sistema passi a un nuovo stato coerente. \u00c8 importante che i nodi raggiungano un accordo tra loro: tutti i nodi devono concordare che il nuovo valore proposto sia corretto, tutti i nodi devono accettare tale valore, e solo allora tutti possono registrare il nuovo valore nel registro. <\/p>\n

    In altre parole: nessuno dei nodi ha obiettato di avere informazioni pi\u00f9 aggiornate e che il valore proposto fosse errato. L'accordo tra i nodi e il consenso su un unico valore corretto accettato \u00e8 ci\u00f2 che costituisce il consenso in un sistema distribuito. Successivamente parleremo degli algoritmi che consentono a un sistema distribuito di raggiungere il consenso in modo garantito.
    \n\"Il
    \nIn modo pi\u00f9 formale, possiamo definire un algoritmo di consenso (o semplicemente algoritmo di consenso) come una funzione che trasforma un sistema distribuito da uno stato A a uno stato B. Questo stato deve essere accettato da tutti i nodi, e tutti i nodi devono poterlo convalidare. A quanto pare, questo compito non \u00e8 affatto triviale come potrebbe sembrare a prima vista.<\/p>\n

    Propriet\u00e0 dell'algoritmo di consenso<\/h4>\n

    \nL'algoritmo di consenso deve possedere tre propriet\u00e0 affinch\u00e9 il sistema continui a esistere e faccia progressi nel passaggio da uno stato a un altro:<\/p>\n

      \n
    1. Accordo <\/b> \u2013 tutti i nodi funzionanti correttamente devono accettare lo stesso valore (in letteratura, questa propriet\u00e0 \u00e8 anche nota come safety property). Tutti i nodi attualmente operativi (che non sono guasti e non hanno perso la connessione con gli altri) devono raggiungere un accordo e accettare un valore comune finale.\n

      \u00c8 importante comprendere che i nodi nel sistema distribuito che stiamo considerando desiderano accordarsi. Stiamo parlando di sistemi in cui qualcosa pu\u00f2 semplicemente fallire (ad esempio, un nodo pu\u00f2 smettere di funzionare), ma in questo sistema non ci sono nodi che lavorano intenzionalmente contro gli altri (il problema dei generali bizantini). Grazie a questa propriet\u00e0, il sistema rimane consistente.<\/li>\n

    2. Integrit\u00e0 <\/b> \u2014 se tutti i nodi funzionanti correttamente offrono lo stesso valore v<\/b>, significa che ogni nodo funzionante correttamente deve accettare questo valore v<\/b>. <\/li>\n
    3. Terminazione <\/b>\u2013 tutti i nodi funzionanti correttamente alla fine accetteranno un certo valore (propriet\u00e0 di vitalit\u00e0), permettendo all'algoritmo di fare progressi nel sistema. Ogni singolo nodo funzionante correttamente deve, prima o poi, accettare il valore finale e confermarlo: \"Per me, questo valore \u00e8 vero, sono d'accordo con l'intero sistema\".<\/li>\n<\/ol>\n

      <\/p>\n

      Esempio di funzionamento dell'algoritmo di consenso<\/h4>\n

      \nAl momento le propriet\u00e0 dell'algoritmo potrebbero non essere del tutto chiare. Pertanto, illustriamo con un esempio quali fasi attraversa il pi\u00f9 semplice algoritmo di consenso in un sistema con un modello di scambio messaggi sincrono, dove tutti i nodi funzionano correttamente, i messaggi non vanno persi e non ci sono guasti (pu\u00f2 davvero succedere?).<\/p>\n

        \n
      1. Tutto inizia con una proposta (Propose). Supponiamo che un cliente si sia connesso al nodo chiamato \"Nodo 1\" e abbia avviato una transazione, inviando al nodo un nuovo valore \u2013 0. Da questo momento in poi, il \"Nodo 1\" sar\u00e0 chiamato proposer<\/b>. Come proposer, il \"Nodo 1\" deve ora informare l'intero sistema che ha nuovi dati, e invia a tutti gli altri nodi un messaggio: \"Guardate! Ho ricevuto il valore '0' e voglio memorizzarlo! Vi prego di confermare che anche voi memorizzerete '0' nel vostro registro.\"\n

        \"Il<\/li>\n

      2. La fase successiva \u00e8 il voto sul valore proposto (Voting). A cosa serve? Pu\u00f2 accadere che ad altri nodi sia arrivata un'informazione pi\u00f9 recente e che abbiano dati su questa stessa transazione.\n

        \"Il
        \n
        \nQuando il nodo \"Nodo 1\" invia la sua proposta, gli altri nodi controllano nei loro registri i dati relativi a questo evento. Se non ci sono contraddizioni, i nodi dichiarano: \"S\u00ec, non ho altri dati su questo evento. Il valore 'O' \u00e8 l'informazione pi\u00f9 recente che abbiamo ottenuto.\" <\/p>\n

        In qualsiasi altro caso, i nodi possono rispondere a \"Nodo 1\": \"Ascolta! Ho dati pi\u00f9 aggiornati su questa transazione. Non 'O', ma qualcosa di meglio.\"<\/p>\n

        Nella fase di voto, i nodi arrivano a una decisione: o tutti accettano un valore unico, oppure qualcuno di loro vota contro, indicando di avere dati pi\u00f9 aggiornati. <\/li>\n

      3. Se il turno di voto ha avuto successo e tutti hanno votato 's\u00ec', il sistema passa a una nuova fase: l'accettazione del valore (Accept). \"Nodo 1\" raccoglie tutte le risposte degli altri nodi e annuncia: \"Tutti hanno concordato sul valore 'O'! Ora dichiaro ufficialmente che 'O' \u00e8 il nostro nuovo valore, unico per tutti! Annotatelo, non dimenticatelo. Scrivetelo nel vostro registro!\"\n

        \"Il<\/li>\n

      4. Gli altri nodi inviano una conferma (Accepted) che hanno registrato il valore \"O\"; nel frattempo non sono arrivate nuove informazioni (una sorta di commit a due fasi). Dopo questo significativo evento, consideriamo che la transazione distribuita sia stata completata.
        \n \"Il <\/li>\n<\/ol>\n

        \nPertanto, l'algoritmo di consenso, in un caso semplice, consiste in quattro passaggi: propose, voting, accept, accepted.<\/p>\n

        Se in qualche fase non siamo riusciti a raggiungere un consenso, l'algoritmo riparte da capo, tenendo conto delle informazioni fornite dai nodi che si sono rifiutati di confermare il valore proposto.<\/p>\n

        L'algoritmo di consenso in un sistema asincrono<\/h2>\n

        \nFino a questo punto, tutto \u00e8 andato liscio, poich\u00e9 si trattava di un modello di scambio messaggi sincrono. Ma sappiamo che nel mondo moderno siamo abituati a fare tutto in modo asincrono. Come funziona quindi un algoritmo simile in un sistema con un modello di scambio messaggi asincrono, dove riteniamo che il tempo di attesa per una risposta da un nodo possa essere indefinito (tra l'altro, il guasto di un nodo pu\u00f2 essere vista anche come un esempio, in cui un nodo pu\u00f2 rispondere dopo un tempo indefinito). <\/p>\n

        Ora che sappiamo come funziona, in linea di principio, l'algoritmo di consenso, la domanda per quei lettori curiosi che sono arrivati fino a questo punto \u00e8: quanti nodi in un sistema di N nodi con un modello di messaggistica asincrona possono guastarsi affinch\u00e9 il sistema possa comunque raggiungere il consenso?<\/p><\/blockquote>\n

        \nLa risposta corretta e la motivazione sono nel seguito.<\/b>La risposta corretta: 0<\/b>. Se almeno un nodo in un sistema asincrono si guasta, il sistema non sar\u00e0 in grado di raggiungere il consenso. Questa affermazione \u00e8 dimostrata nel noto teorema FLP (1985, Fischer, Lynch, Paterson, riferimento originale alla fine dell'articolo): \u00abL'impossibilit\u00e0 di raggiungere un consenso distribuito in caso di guasto di almeno un nodo\u00bb.
        \n\"Il
        \nRagazzi, allora abbiamo un problema, siamo abituati a pensare che tutto sia asincrono. E ora ci troviamo in questa situazione. Come possiamo procedere? <\/p>\n

        Abbiamo appena parlato di teoria, di matematica. Cosa significa \u00abil consenso non pu\u00f2 essere raggiunto\u00bb traducendo dal linguaggio matematico al nostro - ingegneristico? Significa che \u00abnon sempre pu\u00f2 essere raggiunto\u00bb, ossia esiste un caso in cui il consenso non \u00e8 raggiungibile. Ma qual \u00e8 questo caso? <\/p>\n

        Questo rappresenta proprio una violazione della propriet\u00e0 di liveness descritta sopra. Non abbiamo un consenso comune e il sistema non pu\u00f2 fare progressi (non pu\u00f2 terminare in un tempo finito) quando non riceviamo risposta da tutti i nodi. Poich\u00e9 in un sistema asincrono non abbiamo un tempo di risposta prevedibile, non possiamo sapere se un nodo \u00e8 guasto o sta semplicemente rispondendo lentamente.<\/p>\n

        Ma nella pratica possiamo trovare una soluzione. Diciamo che il nostro algoritmo pu\u00f2 funzionare a lungo in caso di guasti (potenzialmente pu\u00f2 operare all'infinito). Tuttavia, nella maggior parte delle situazioni, quando la maggior parte dei nodi funziona correttamente, avremo dei progressi nel sistema. <\/p>\n

        Nella pratica, affrontiamo modelli di comunicazione parzialmente sincroni. La parziale sincronia si intende nel senso che, in generale, abbiamo un modello asincrono, ma viene formalmente introdotto un concetto di \"tempo di stabilizzazione globale\" in un certo momento. <\/p>\n

        Questo momento potrebbe non arrivare per lungo tempo, ma un giorno dovr\u00e0 arrivare. Suoner\u00e0 la sveglia virtuale, e da quel momento saremo in grado di prevedere la delta di tempo che intercorre affinch\u00e9 i messaggi arrivino. Da quel momento il sistema passa da asincrono a sincrono. Nella pratica, ci confrontiamo proprio con questi sistemi. <\/p>\n

        L'algoritmo Paxos risolve problemi di consenso<\/h2>\n

        \nPaxos <\/a><\/noindex> \u00e8 una famiglia di algoritmi che risolvono il problema del consenso per sistemi parzialmente sincroni, a patto che alcuni nodi possano andare offline. L'autore di Paxos \u00e8 Leslie Lamport<\/a><\/noindex>. Ha proposto una dimostrazione formale dell'esistenza e correttezza dell'algoritmo nel 1989. <\/p>\n

        Ma la dimostrazione si rivel\u00f2 tutt\u2019altro che banale. La prima pubblicazione \u00e8 stata rilasciata solo nel 1998 (33 pagine) con la descrizione dell'algoritmo. Si \u00e8 rivelata estremamente complessa da comprendere, e nel 2001 \u00e8 stata pubblicata una spiegazione dell'articolo che ha occupato 14 pagine. I volumi delle pubblicazioni sono forniti per dimostrare che in realt\u00e0 il problema del consenso \u00e8 tutt'altro che semplice, e dietro a questi algoritmi ci sono enormi fatiche delle menti pi\u00f9 brillanti.<\/p>\n

        \u00c8 interessante notare che lo stesso Leslie Lamport nella sua lezione ha osservato che nel secondo articolo esplicativo c'\u00e8 un'affermazione, una riga (non specificata quale), che pu\u00f2 essere interpretata in vari modi. A causa di ci\u00f2, un gran numero di implementazioni moderne di Paxos non funzionano in modo del tutto corretto. <\/p><\/blockquote>\n

        \nUn'analisi approfondita del funzionamento di Paxos richiederebbe pi\u00f9 di un articolo, quindi cercher\u00f2 di trasmettere brevemente l'idea principale dell'algoritmo. Nei link alla fine del mio articolo troverete materiali per un ulteriore approfondimento su questo argomento.<\/p>\n

        Ruoli in Paxos<\/h4>\n

        \nNell'algoritmo Paxos esiste il concetto di ruoli. Consideriamo i tre principali (esistono modifiche con ruoli aggiuntivi):<\/p>\n

          \n
        1. Proposers (possono essere utilizzati anche i termini: leader o coordinatori)<\/b>. Sono i ragazzi che apprendono un nuovo valore dall'utente e assumono il ruolo di leader. Il loro compito \u00e8 avviare un round di proposta di un nuovo valore e coordinare le ulteriori azioni dei nodi. Paxos consente la presenza di pi\u00f9 leader in alcune situazioni.<\/li>\n
        2. Acceptors (Voters)<\/b>. Sono nodi che votano per l'accettazione o il rifiuto di un determinato valore. Il loro ruolo \u00e8 molto importante, poich\u00e9 da loro dipende la decisione: in quale stato passer\u00e0 (o non passer\u00e0) il sistema dopo ogni fase dell'algoritmo di consenso.<\/li>\n
        3. Apprendenti<\/b>. Nodi che semplicemente accettano e registrano il nuovo valore accettato quando lo stato del sistema cambia. Non prendono decisioni, ricevono solo dati e possono restituirli all'utente finale. <\/li>\n<\/ol>\n

          \nUn nodo pu\u00f2 assumere pi\u00f9 ruoli in diverse situazioni. <\/p>\n

          Il concetto di quoro<\/h4>\n

          \nSupponiamo di avere un sistema di N<\/b> nodi. E di questi un massimo di F<\/b> nodi pu\u00f2 guastarsi. Se F nodi si guastano, significa che nel cluster devono esserci almeno 2F + 1<\/b> nodi accettatori. <\/p>\n

          Questo \u00e8 necessario affinch\u00e9 anche nella peggiore situazione i nodi \"buoni\", che funzionano correttamente, abbiano la maggioranza. Cio\u00e8, F + 1<\/b> \u201cbuoni\u201d nodi che hanno acconsentito, e il valore finale sar\u00e0 accettato. Altrimenti, potrebbe verificarsi una situazione in cui i nostri diversi gruppi locali accettano valori diversi e non riescono a mettersi d'accordo. Pertanto, abbiamo bisogno di una maggioranza assoluta per vincere la votazione.<\/p>\n

          L'idea generale del funzionamento dell'algoritmo di consenso Paxos<\/h4>\n

          \nL'algoritmo Paxos prevede due fasi principali, che a loro volta sono suddivise in due passaggi ciascuna:<\/p>\n

            \n
          1. Fase 1a: Prepare<\/b>. Durante la fase di preparazione, il leader (proposer) comunica a tutti i nodi: \u00abIniziamo una nuova fase di votazione. Abbiamo un nuovo turno. Il numero di questo turno \u00e8 n. Ora iniziamo a votare\u00bb. In questo momento, sta solo annunciando l'inizio di un nuovo ciclo, ma non sta rivelando un nuovo valore. L'obiettivo di questa fase \u00e8 avviare un nuovo turno e comunicare a tutti il suo numero unico. Il numero del turno \u00e8 importante, deve essere un valore superiore a tutti i numeri di votazione precedenti provenienti da tutti i leader passati. Infatti, grazie al numero del turno, gli altri nodi nel sistema capiranno quanto siano recenti i dati del leader. Probabilmente, gli altri nodi hanno gi\u00e0 risultati di votazione di turni molto pi\u00f9 recenti e informeranno semplicemente il leader che \u00e8 rimasto indietro.<\/li>\n
          2. Fase 1b: Promessa<\/b>. Quando i nodi-acceptor hanno ricevuto il numero della nuova fase di votazione, possono verificarsi due esiti: \n