{"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":"

Immaginiamo. In una stanza ci sono 5 gatti, e per andare a svegliare il padrone devono accordarsi tutti insieme, dato che possono aprire la porta solo tutti insieme. Se uno dei gatti \u00e8 il gatto di Schr\u00f6dinger, mentre gli altri gatti non conoscono la sua decisione, sorge la domanda: \u00abCome possono farlo?\u00bb <\/p>\n

In questo articolo vi spiegher\u00f2 in modo semplice la teoria dietro il mondo dei sistemi distribuiti e i principi del loro funzionamento. Inoltre, esaminer\u00f2 brevemente l'idea principale alla base di Paxos. <\/p>\n

\"Il
\n<\/a><\/noindex>
\nQuando gli sviluppatori utilizzano infrastrutture cloud, diversi database e lavorano in cluster di nodi, sono certi che i dati saranno integri, sicuri e sempre accessibili. Ma da dove vengono queste garanzie?<\/p>\n

Fondamentalmente, le garanzie che abbiamo sono quelle del fornitore. Sono descritte nella documentazione pi\u00f9 o meno in questo modo: \u00abQuesto servizio \u00e8 abbastanza affidabile, ha un SLA definito, non preoccuparti, tutto funzioner\u00e0 in distribuzione come ti aspetti\u00bb. <\/p>\n

Tendiamo a credere nel meglio, poich\u00e9 signori intelligenti di grandi aziende ci hanno assicurato che andr\u00e0 tutto bene. Non ci poniamo la domanda: perch\u00e9, in realt\u00e0, tutto ci\u00f2 potrebbe funzionare? Esiste una qualche giustificazione formale per la correttezza di tali sistemi?<\/p>\n

Recentemente sono andato a una scuola di calcolo distribuito<\/a><\/noindex> e sono rimasto molto ispirato da questo tema. Le lezioni della scuola somigliavano pi\u00f9 a corsi di analisi matematica che a qualcosa legato ai sistemi informatici. Ma \u00e8 proprio cos\u00ec che un tempo venivano dimostrati gli algoritmi pi\u00f9 importanti che utilizziamo ogni giorno senza neanche accorgercene. <\/p>\n

Nella maggior parte dei moderni sistemi distribuiti si utilizza l'algoritmo di consenso Paxos e le sue varie modifiche. La cosa pi\u00f9 interessante \u00e8 che la validit\u00e0 e, in generale, la stessa possibile esistenza di questo algoritmo possono essere dimostrate semplicemente con carta e penna. Nel frattempo, nella pratica, l'algoritmo viene applicato in grandi sistemi operanti su un numero enorme di nodi nelle nuvole. <\/p>\n

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

Abbiamo due eserciti: uno rosso e uno bianco. Le forze bianche si trovano nella citt\u00e0 assediata. Le forze rosse, guidate dai generali A1 e A2, si sono dislocate ai due lati della citt\u00e0. Il compito dei rossi \u00e8 attaccare la citt\u00e0 bianca e vincere. Tuttavia, l'esercito di ciascun generale rosso \u00e8 pi\u00f9 piccolo di 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 farlo, i generali A1 e A2 devono accordarsi tra loro. Se ciascuno attacca separatamente, i rossi perderanno. <\/p>\n

Per accordarsi, i generali A1 e A2 possono inviare messaggeri l'uno all'altro attraverso il territorio della citt\u00e0 bianca. Un messaggero pu\u00f2 raggiungere con successo il generale alleato o pu\u00f2 essere intercettato dal nemico. Il problema \u00e8: esiste una sequenza di comunicazioni tra i generali rossi (sequenza di invio di messaggeri da A1 a A2 e viceversa da A2 a A1) che garantisca che si accordino per attaccare all'ora X? Qui, per garanzie, si intende che entrambi i generali riceveranno una conferma inequivocabile che l'alleato (l'altro generale) attaccher\u00e0 esattamente all'orario stabilito 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 a fracassare i bianchi\u00bb. Ma ora il generale A2 non sa se il suo messaggero \u00e8 arrivato o no, non ha garanzie che l'attacco sar\u00e0 simultaneo. Ora, il generale A2 ha di nuovo bisogno di una conferma.<\/p>\n

Se si approfondisce ulteriormente la loro comunicazione, si scoprir\u00e0 quanto segue: non importa quante volte si scambino messaggi, non esiste un modo per garantire che entrambi i generali siano informati che i loro messaggi sono stati ricevuti (dato che qualunque messaggero pu\u00f2 essere intercettato).<\/p>\n

Il problema dei due generali \u00e8 un'eccellente illustrazione di un sistema distribuito molto semplice, dove ci sono due nodi con una comunicazione inaffidabile. Questo significa che non abbiamo la garanzia al 100% che si sincronizzeranno. Di problemi simili, ma su una scala pi\u00f9 ampia, si parler\u00e0 pi\u00f9 avanti nell'articolo.<\/p>\n

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

\nUn sistema distribuito \u00e8 un gruppo di computer (che chiameremo nodi) in grado di scambiarsi messaggi. Ogni singolo 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, quali protocolli vengono utilizzati, non ci interessa in questo contesto. \u00c8 importante che i nodi del sistema distribuito possano scambiarsi dati inviando messaggi tra loro.<\/p>\n

La definizione stessa non \u00e8 molto complessa, ma \u00e8 necessario 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 \u00e8 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 finch\u00e9 non abbiamo un ordine chiaro nella loro apparizione. E, di solito, non lo abbiamo.<\/li>\n
  2. Assenza di orologi globali<\/b>. Non abbiamo un ordine chiaro degli eventi a causa dell'assenza di orologi globali. Nel mondo degli esseri umani siamo abituati ad avere orologi e tempo assoluto. Tutto cambia quando si parla di sistemi distribuiti. Anche gli orologi atomici super precisi hanno un drift, e ci possono essere situazioni in cui non possiamo dire quale dei due eventi si sia verificato per primo. Pertanto, non possiamo nemmeno fare affidamento sul tempo.<\/li>\n
  3. Guasto indipendente dei nodi del sistema<\/b>. C'\u00e8 un'altra problematica: 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 avere dei problemi e i messaggi possono andare persi. Inoltre, ci possono essere situazioni in cui i nodi funzionano, ma agiscono contro il sistema. Quest'ultima classe di problemi ha persino ricevuto un nome specifico: il problema dei generali bizantini<\/a><\/noindex>. L'esempio pi\u00f9 popolare di sistema distribuito con questo problema \u00e8 il Blockchain. Ma oggi non parleremo di questa specifica classe di problemi. Ci interesseremo a situazioni in cui uno o pi\u00f9 nodi possono andarsene in tilt.<\/li>\n
  4. Modelli di comunicazione (modelli di scambio di messaggi) tra nodi<\/b>Abbiamo gi\u00e0 stabilito che i nodi comunicano attraverso lo scambio di messaggi. Ci sono due modelli di scambio di messaggi noti: sincrono e asincrono.<\/li>\n<\/ol>\n

    <\/p>\n

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

    \nModello sincrono<\/b> \u2013 sappiamo esattamente che c'\u00e8 una delta di tempo finita nota, entro la quale il messaggio arriva garantito da un nodo all'altro. Se questo tempo scade e il messaggio non \u00e8 arrivato, possiamo dire con certezza che il nodo \u00e8 guasto. 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 \u00e8 guasto. 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 ulteriormente. <\/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 ci serve, ovvero \u2013 Replica della macchina di stato<\/b>. <\/p>\n

    Abbiamo un certo log 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 log, il suo compito \u00e8 proporre questo valore a tutti gli altri nodi, affinch\u00e9 il log si aggiorni su tutti i nodi e il sistema passi a un nuovo stato coerente. \u00c8 importante che i nodi si mettano d'accordo tra di loro: tutti i nodi concordano che il nuovo valore proposto sia corretto, tutti i nodi accettano questo valore, e solo in questo caso possono tutti registrare il nuovo valore nel log. <\/p>\n

    In altre parole: nessuno dei nodi ha obiettato di avere informazioni pi\u00f9 aggiornate, e che il valore proposto \u00e8 errato. L'accordo tra i nodi e il consenso su un unico valore accettato corretto \u00e8 il consenso in un sistema distribuito. Successivamente parleremo degli algoritmi che permettono a un sistema distribuito di raggiungere garantito il consenso.
    \n\"Il
    \nIn modo pi\u00f9 formale, possiamo definire l'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 \u00e8 accettato da tutti i nodi, e tutti i nodi possono confermarlo. Si scopre che questa operazione non \u00e8 cos\u00ec banale come sembra a prima vista.<\/p>\n

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

    \nL'algoritmo di consenso deve avere tre propriet\u00e0 affinch\u00e9 il sistema possa continuare ad esistere e avere qualche progresso nel passaggio da uno stato all'altro:<\/p>\n

      \n
    1. Accordo <\/b> \u2013 tutti i nodi funzionanti devono accettare lo stesso valore (in articoli questa propriet\u00e0 \u00e8 talvolta indicata come propriet\u00e0 di sicurezza). Tutti i nodi attualmente operativi (che non sono offline e non hanno perso il contatto con gli altri) devono arrivare a un accordo e accettare un certo valore finale comune.\n

      \u00c8 importante capire che i nodi nel sistema distribuito che stiamo considerando vogliono mettersi d'accordo. Vale a dire, stiamo parlando di sistemi in cui qualcosa potrebbe semplicemente guastarsi (ad esempio, un nodo potrebbe guastarsi), 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> \u2013 se tutti i nodi funzionanti offrono lo stesso valore v<\/b>, allora ogni nodo funzionante deve accettare questo valore v<\/b>. <\/li>\n
    3. Terminazione <\/b>\u2013 tutti i nodi funzionanti alla fine accetteranno un certo valore (propriet\u00e0 di vivacit\u00e0), il che consente all'algoritmo di progredire nel sistema. Ogni singolo nodo funzionante deve, prima o poi, accettare un 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

      \nFinch\u00e9 le propriet\u00e0 dell'algoritmo potrebbero non essere del tutto chiare. Illustriamo quindi, con un esempio, quali fasi attraversa il pi\u00f9 semplice algoritmo di consenso in un sistema con un modello di scambio messaggi sincrono, in cui tutti i nodi funzionano come previsto, i messaggi non vengono persi e niente si rompe (\u00e8 davvero possibile che accada?).<\/p>\n

        \n
      1. Tutto inizia con la proposta di matrimonio (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 O. Da questo momento in poi, chiameremo \"Nodo 1\" proposer<\/b>. Come proposer, \"Nodo 1\" deve ora notificare l'intero sistema che ha nuovi dati e invia a tutti gli altri nodi messaggi: \"Guardate! Ho ricevuto il valore 'O' e voglio scriverlo! Vi chiedo di confermare che lo scriverete anch'esso 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 siano arrivati dati pi\u00f9 aggiornati, e che abbiano informazioni relative alla 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 relativi a questo evento. Il valore 'O' \u00e8 l'informazione pi\u00f9 recente che abbiamo ricevuto.\" <\/p>\n

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

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

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

        \"Il<\/li>\n

      4. Gli altri nodi inviano conferma (Accepted) che hanno annotato il valore 'O', che nel frattempo non \u00e8 arrivato nulla di nuovo (una sorta di commit in due fasi). Dopo questo evento significativo, 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, voto (voting), accettazione (accept), conferma dell'accettazione (accepted).<\/p>\n

        Se in qualche fase non riusciamo a raggiungere un consenso, l'algoritmo viene riavviato, tenendo conto delle informazioni fornite dai nodi che hanno rifiutato di confermare il valore proposto.<\/p>\n

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

        \nFino a questo momento tutto andava bene, poich\u00e9 stavamo trattando un modello di scambio di 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 di messaggi asincrono, dove consideriamo che il tempo di attesa per una risposta da un nodo possa essere arbitrariamente lungo (per inciso, l'uscita di un nodo fuori gioco pu\u00f2 anche essere vista come un esempio in cui un nodo potrebbe rispondere con arbitraria lentezza). <\/p>\n

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

        \nLa risposta corretta e la motivazione sono nel spoiler.<\/b>Risposta corretta: 0<\/b>. Se almeno un nodo in un sistema asincrono esce fuori gioco, il sistema non potr\u00e0 raggiungere il consenso. Questa affermazione \u00e8 dimostrata nel noto teorema FLP (1985, Fischer, Lynch, Paterson, link all'originale alla fine dell'articolo): \"L'impossibilit\u00e0 di raggiungere un consenso distribuito in caso di guasto di almeno un nodo\".
        \n\"Il
        \nRagazzi, allora abbiamo un problema, siamo abituati a fare tutto in modo asincrono. E ora ci troviamo in questa situazione. Come andiamo avanti? <\/p>\n

        Abbiamo parlato della teoria, della matematica. Cosa significa \"il consenso non pu\u00f2 essere raggiunto\", traducendo dal linguaggio matematico al nostro \u2013 ingegneristico? Significa che \"non sempre pu\u00f2 essere raggiunto\", cio\u00e8 esiste un caso in cui il consenso non \u00e8 raggiungibile. Ma quale \u00e8 questo caso? <\/p>\n

        \u00c8 proprio la violazione della propriet\u00e0 di vivacit\u00e0, descritta sopra. Non abbiamo consenso comune e il sistema non pu\u00f2 avere progresso (non pu\u00f2 completarsi in un tempo finito) nel caso in cui non riceviamo risposta da tutti i nodi. Perch\u00e9 in un sistema asincrono non abbiamo un tempo di risposta prevedibile e non possiamo sapere se un nodo \u00e8 fuori gioco o semplicemente sta rispondendo lentamente.<\/p>\n

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

        Nella pratica, abbiamo a che fare con modelli di comunicazione parzialmente sincroni. La parziale sincronicit\u00e0 \u00e8 intesa come segue: generalmente abbiamo un modello asincrono, ma si introduce formalmente il concetto di \"tempo di stabilizzazione globale\" in un certo momento. <\/p>\n

        Questo momento potrebbe non verificarsi per un tempo indefinito, ma un giorno deve arrivare. Suoner\u00e0 la sveglia virtuale e da quel momento possiamo prevedere la delta temporale per cui i messaggi arriveranno. Da quel momento, il sistema passa da asincrono a sincrono. Nella pratica, trattiamo proprio con sistemi di questo tipo. <\/p>\n

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

        \nPaxos <\/a><\/noindex> \u00e8 una famiglia di algoritmi che risolve il problema del consenso per sistemi parzialmente sincroni, a condizione che alcuni nodi possano guastarsi. 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 \u00e8 rivelata tutt'altro che banale. La prima pubblicazione \u00e8 stata rilasciata solo nel 1998 (33 pagine) con la descrizione dell'algoritmo. Si \u00e8 rivelata estremamente difficile da comprendere, e nel 2001 \u00e8 stata pubblicata una spiegazione dell'articolo che ha occupato 14 pagine. Le dimensioni delle pubblicazioni sono indicate per dimostrare che in realt\u00e0 il problema del consenso \u00e8 piuttosto complesso e dietro a tali algoritmi c'\u00e8 un enorme lavoro delle menti pi\u00f9 brillanti.<\/p>\n

        \u00c8 interessante notare che lo stesso Leslie Lamport nella sua lezione ha osservato che nella seconda articolo di spiegazione c'\u00e8 un'affermazione, una riga (non ha specificato quale), che pu\u00f2 essere interpretata in modi diversi. E per questo motivo, un gran numero di implementazioni moderne di Paxos non funzionano del tutto correttamente. <\/p><\/blockquote>\n

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

        Ruoli in Paxos<\/h4>\n

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

          \n
        1. Proposers (possono anche essere utilizzati i termini: leader o coordinatori)<\/b>Questi sono i ragazzi che apprendono un nuovo valore dall'utente e svolgono il ruolo di leader. Il loro compito \u00e8 avviare un round per proporre un nuovo valore e coordinare le ulteriori azioni dei nodi. Inoltre, Paxos consente la presenza di pi\u00f9 leader in determinate situazioni.<\/li>\n
        2. Accettatori (Votanti)<\/b>Questi sono i nodi che votano per l'accettazione o il rifiuto di un certo valore. Il loro ruolo \u00e8 molto importante, poich\u00e9 dipende da loro la decisione su quale stato passer\u00e0 (o non passer\u00e0) il sistema dopo la fase successiva dell'algoritmo di consenso.<\/li>\n
        3. Apprendisti<\/b>I nodi che semplicemente accettano e registrano il nuovo valore accettato quando lo stato del sistema \u00e8 cambiato. Non prendono decisioni, ma ricevono dati e possono fornirli all'utente finale. <\/li>\n<\/ol>\n

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

          Il concetto di quorum<\/h4>\n

          \nPresupponiamo di avere un sistema costituito da N<\/b> nodi. E di questi, al massimo F<\/b> nodi possono guastarsi. Se F nodi si guastano, allora nel nostro cluster devono esserci almeno 2F + 1<\/b> nodi acceptor. <\/p>\n

          Questo \u00e8 necessario affinch\u00e9 abbiamo sempre, anche nella situazione peggiore, un numero maggiore di nodi \"buoni\", funzionanti correttamente. Cio\u00e8, abbiamo bisogno di F + 1<\/b> nodi \"buoni\" che abbiano concordato, e il valore finale sar\u00e0 accettato. Altrimenti, potrebbe verificarsi una situazione in cui diversi gruppi locali accettano valori diversi e non possono accordarsi tra loro. Pertanto, abbiamo bisogno di una maggioranza assoluta per vincere nella votazione.<\/p>\n

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

          \nL'algoritmo Paxos prevede due grandi fasi, ciascuna delle quali \u00e8 suddivisa in due passaggi:<\/p>\n

            \n
          1. Fase 1a: Preparare<\/b>. Durante la fase di preparazione, il leader (proposer) informa tutti i nodi: \u00abIniziamo una nuova fase di voto. Abbiamo un nuovo turno. Il numero di questo turno \u00e8 n. Adesso iniziamo a votare\u00bb. Finora ha solo comunicato l'inizio di un nuovo ciclo, senza fornire 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 maggiore rispetto a tutti i numeri di voto precedenti da tutti i leader precedenti. Infatti, \u00e8 grazie al numero del turno che gli altri nodi nel sistema capiranno quanto siano aggiornati i dati del leader. Probabilmente, altri nodi hanno gi\u00e0 risultati di voti provenienti da turni molto pi\u00f9 recenti e semplicemente informeranno il leader che \u00e8 rimasto indietro.<\/li>\n
          2. Fase 1b: Promessa<\/b>. Quando i nodi acceptor ricevono il numero di una nuova fase di voto, ci sono due possibili esiti: \n