{"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\/da\/blog\/administrirovanie\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","title":{"rendered":"Schr\u00f6dingers kat uden kasse: Konsensusproblemet i distribuerede systemer","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Lad os forestille os. I et rum er 5 katte l\u00e5st inde, og for at v\u00e6kke ejeren skal de blive enige om det, for d\u00f8ren kan kun \u00e5bnes, hvis de alle fem skubber imod den. Hvis en af kattene er Schr\u00f6dingers kat, og de andre katte ikke ved, hvad han har besluttet, opst\u00e5r sp\u00f8rgsm\u00e5let: \"Hvordan kan de g\u00f8re det?\" <\/p>\n

I denne artikel vil jeg med enkle ord fort\u00e6lle dig om de teoretiske aspekter af verdenen af distribuerede systemer og principperne bag deres arbejde. Jeg vil ogs\u00e5 kort gennemg\u00e5 den vigtigste id\u00e9, der ligger til grund for Paxos. <\/p>\n

\"Schr\u00f6dingers
\n<\/a><\/noindex>
\nN\u00e5r udviklere bruger cloud-infrastrukturer, forskellige databaser, og arbejder i klynger med mange noder, er de sikre p\u00e5, at dataene vil v\u00e6re intakte, sikre og altid tilg\u00e6ngelige. Men hvor kommer garantierne fra?<\/p>\n

I bund og grund er de garantier, vi har, garantier fra leverand\u00f8ren. De beskrives i dokumentationen omtrent s\u00e5ledes: \"Denne tjeneste er ret p\u00e5lidelig, den har en fastsat SLA, bekymre dig ikke, alt vil fungere distribueret, som du forventer.\" <\/p>\n

Vi har en tendens til at tro p\u00e5 det bedste, for kloge fyre fra store virksomheder har forsikret os om, at alt vil v\u00e6re i orden. Vi stiller ikke sp\u00f8rgsm\u00e5let: hvorfor, hvorfor overhovedet, kan dette fungere? Er der nogen formel begrundelse for korrektheden af disse systemers funktion?<\/p>\n

For nylig var jeg til en skole i distribuerede beregninger<\/a><\/noindex> og jeg blev meget inspireret af emnet. Forel\u00e6sningerne i skolen mindede mere om timer i matematisk analyse end noget, der var relateret til computersystemer. Men det var netop s\u00e5dan, vigtige algoritmer, som vi bruger hver dag, blev bevist, uden at vi selv er klar over det. <\/p>\n

I de fleste moderne distribuerede systemer anvendes konsensusalgoritmen Paxos og dens forskellige modifikationer. Det mest fantastiske er, at holdbarheden og muligheden for, at denne algoritme eksisterer, kan bevises med blot en pen og papir. Samtidig anvendes algoritmen i praksis i store systemer, der k\u00f8rer p\u00e5 et stort antal noder i skyen. <\/p>\n

En let illustration af, hvad der vil blive diskuteret n\u00e6ste gang: to generalers problem<\/b>Lad os for sjov tage fat p\u00e5 to generalers problem<\/a><\/noindex>. <\/p>\n

Vi har to h\u00e6re - den r\u00f8de og den hvide. De hvide styrker er baseret i den belejrede by. De r\u00f8de styrker under ledelse af generalerne A1 og A2 er placeret p\u00e5 to sider af byen. Opgaven for de r\u00f8de er at angribe den hvide by og vinde. Men styrken af hver r\u00f8d general er mindre end styrken af de hvide.<\/p>\n

\"Schr\u00f6dingers
\n
\nVilk\u00e5rene for sejr for de r\u00f8de: begge generaler skal angribe samtidig for at have et numerisk overtag over de hvide. For dette skal generalerne A1 og A2 blive enige med hinanden. Hvis hver af dem angriber enkeltvis, vil de r\u00f8de tabe. <\/p>\n

For at blive enige kan generalerne A1 og A2 sende budbringere til hinanden over det hvide byomr\u00e5de. Budbringeren kan n\u00e5 frem til den allierede general eller kan blive opfanget af fjenden. Sp\u00f8rgsm\u00e5let er: findes der en sekvens af kommunikation mellem de r\u00f8de generaler (sekvensen af budbringere fra A1 til A2 og omvendt fra A2 til A1), hvor de garanteret kan blive enige om angrebet p\u00e5 tidspunktet X. Her forst\u00e5s garantien som, at begge generaler vil have entydig bekr\u00e6ftelse p\u00e5, at deres allierede (den anden general) helt sikkert vil angribe p\u00e5 det angivne tidspunkt X.<\/p>\n

Antag, at A1 sender en budbringer til A2 med beskeden: 'Lad os angribe i aften ved midnat!'. General A1 kan ikke angribe uden bekr\u00e6ftelse fra general A2. Hvis budbringeren fra A1 er n\u00e5et frem, s\u00e5 sender general A2 en bekr\u00e6ftelse med beskeden: 'Ja, lad os g\u00e5 efter de hvide i aften'. Men nu ved general A2 ikke, om hans budbringer er n\u00e5et frem eller ej; han har ingen garantier for, at angrebet bliver simultant. Nu skal general A2 igen have bekr\u00e6ftelse.<\/p>\n

Hvis vi forts\u00e6tter deres kommunikation, vil det blive klart, at uanset hvor mange cykler af meddelelser der udveksles, er der ingen m\u00e5de at garantere, at begge generaler bliver underrettet om, at deres meddelelser er modtaget (givet at enhver budbringer kan blive opfanget).<\/p>\n

Opgaven med de to generaler er en glimrende illustration af et meget simpelt distribueret system, hvor der er to noder med usikker kommunikation. Det betyder, at vi ikke har 100 % garanti for, at de synkroniseres. Jeg vil senere i artiklen tale om s\u00e5danne problemer, men i en st\u00f8rre skala.<\/p>\n

Vi indf\u00f8rer begrebet distribuerede systemer.<\/h2>\n

\nEt distribueret system er en gruppe af computere (her kaldet noder), der kan udveksle beskeder. Hver enkelt node er en selvst\u00e6ndig enhed. En node kan selvst\u00e6ndigt behandle opgaver, men for at interagere med andre noder skal den sende og modtage beskeder. <\/p>\n

Hvordan beskederne konkret er implementeret, hvilke protokoller der anvendes, er ikke vores fokus i denne sammenh\u00e6ng. Det vigtige er, at noderne i det distribuerede system kan udveksle data med hinanden ved at sende beskeder.<\/p>\n

Selve definitionen virker ikke s\u00e6rlig kompleks, men det er vigtigt at tage h\u00f8jde for, at et distribueret system har en r\u00e6kke attributter, som vil v\u00e6re vigtige for os.<\/p>\n

Attributter for distribuerede systemer<\/h4>\n

<\/p>\n

    \n
  1. Samtidighed<\/b> \u2013 muligheden for, at der opst\u00e5r samtidige eller konkurrerende h\u00e6ndelser i systemet. Desuden vil vi betragte h\u00e6ndelser, der finder sted p\u00e5 to forskellige noder, som potentielt konkurrencepr\u00e6gede, indtil vi har en klar r\u00e6kkef\u00f8lge af disse h\u00e6ndelser. Og normalt har vi ikke den r\u00e6kkef\u00f8lge.<\/li>\n
  2. Manglen p\u00e5 globale ur<\/b>. Vi har ikke en klar r\u00e6kkef\u00f8lge af h\u00e6ndelser p\u00e5 grund af frav\u00e6ret af et globalt ur. I den normale verden er vi vant til, at vi har ure og tid er absolut. Alt \u00e6ndrer sig, n\u00e5r det kommer til distribuerede systemer. Selv de mest pr\u00e6cise atomur har drift, og der kan opst\u00e5 situationer, hvor vi ikke kan sige, hvilken af de to h\u00e6ndelser der skete f\u00f8rst. Derfor kan vi heller ikke stole p\u00e5 tiden.<\/li>\n
  3. Uafh\u00e6ngig fejl i noderne i systemet<\/b>. Der er et andet problem: noget kan g\u00e5 galt ganske enkelt fordi vores noder ikke er evige. En harddisk kan svigte, en virtuel maskine i skyen kan genstarte, netv\u00e6rket kan blinke, og meddelelser kan g\u00e5 tabt. Desuden er der situationer, hvor noderne fungerer, men samtidig arbejder imod systemet. Den sidste klasse af problemer har endda f\u00e5et et s\u00e6rligt navn: problemet med de byzantinske generaler<\/a><\/noindex>. Det mest popul\u00e6re eksempel p\u00e5 et distribueret system med et s\u00e5dant problem er Blockchain. Men i dag vil vi ikke se p\u00e5 denne s\u00e6rlige klasse af problemer. Vi vil v\u00e6re interesserede i situationer, hvor blot en eller flere noder kan fejle.<\/li>\n
  4. Kommunikationsmodeller (beskedsystemer) mellem noderne<\/b>. Vi har allerede fundet ud af, at noder kommunikerer ved at udveksle beskeder. Der er to kendte modeller for beskedudveksling: synkron og asynkron.<\/li>\n<\/ol>\n

    <\/p>\n

    Kommunikationsmodeller mellem noder i distribuerede systemer<\/h4>\n

    \nSynkron model<\/b> \u2013 vi ved pr\u00e6cist, at der er en kendt tidsforsinkelse, hvor en besked garanteret n\u00e5r fra \u00e9n node til en anden. Hvis denne tid er udl\u00f8bet, og beskeden ikke er ankommet, kan vi med sikkerhed sige, at noden er nede. I en s\u00e5dan model har vi en forudsigelig ventetid. <\/p>\n

    Asynkron model<\/b> \u2013 i asynkrone modeller antager vi, at ventetiden er endelig, men der findes ikke en tidsforsinkelse, efter hvilken vi kan garantere, at noden er nede. Dvs. ventetiden for en besked fra noden kan v\u00e6re ubegribelig lang. Dette er en vigtig definition, og vi vil tale mere om det senere. <\/p>\n

    Begrebet konsensus i distribuerede systemer<\/h2>\n

    \nF\u00f8r vi formelt definerer begrebet konsensus, lad os overveje et eksempel p\u00e5 en situation, hvor det er n\u00f8dvendigt, nemlig \u2013 State Machine Replication<\/b>. <\/p>\n

    Vi har en vis distribueret log. Vi \u00f8nsker, at den skal v\u00e6re konsistent og indeholde identiske data p\u00e5 alle noder i det distribuerede system. N\u00e5r en af noderne f\u00e5r kendskab til en ny v\u00e6rdi, som den vil skrive til loggen, bliver dens opgave at foresl\u00e5 denne v\u00e6rdi til alle andre noder, s\u00e5 loggen opdateres p\u00e5 alle noder, og systemet kommer ind i en ny konsistent tilstand. Det er vigtigt, at noderne bliver enige: alle noder er enige om, at den foresl\u00e5ede nye v\u00e6rdi er korrekt, alle noder har accepteret denne v\u00e6rdi, og kun i s\u00e5 fald kan alle skrive den nye v\u00e6rdi til loggen. <\/p>\n

    Med andre ord: ingen af noderne har indsigelser mod, at de har mere aktuel information, og at den foresl\u00e5ede v\u00e6rdi er forkert. Enigheden mellem noderne og enigheden om den samme korrekte accepterede v\u00e6rdi er konsensus i et distribueret system. Senere vil vi tale om algoritmer, der tillader det distribuerede system at opn\u00e5 konsensus med garanti.
    \n\"Schr\u00f6dingers
    \nMere formelt kan vi definere en konsensusalgoritme (eller blot konsensusalgoritmen) som en funktion, der f\u00f8rer et distribueret system fra tilstand A til tilstand B. Dette tilstand skal v\u00e6re accepteret af alle noder, og alle noder skal kunne bekr\u00e6fte det. Det viser sig, at denne opgave slet ikke er s\u00e5 triviel, som det ser ud ved f\u00f8rste \u00f8jekast.<\/p>\n

    Egenskaber ved konsensusalgoritmen<\/h4>\n

    \nKonsensusalgoritmen skal have tre egenskaber for at systemet kan forts\u00e6tte med at eksistere og have fremdrift i overgangen fra tilstand til tilstand:<\/p>\n

      \n
    1. Enighed <\/b> \u2013 alle korrekt fungerende noder skal acceptere den samme v\u00e6rdi (i artiklerne kaldes denne egenskab ogs\u00e5 sikkerhedsegenskab). Alle noder, der i \u00f8jeblikket fungerer (ikke er brudt ned og ikke har mistet forbindelsen til de andre), skal n\u00e5 til enighed og acceptere en f\u00e6lles endelig v\u00e6rdi.\n

      Her er det vigtigt at forst\u00e5, at noderne i det distribuerede system, vi taler om, \u00f8nsker at blive enige. Det vil sige, at vi nu taler om systemer, hvor noget m\u00e5ske kan g\u00e5 galt (f.eks. kan en node fejle), men i dette system er der bestemt ikke noder, der arbejder imod de andre (problemet med de byzantinske generaler). P\u00e5 grund af denne egenskab forbliver systemet konsistent.<\/li>\n

    2. Integritet <\/b> \u2013 hvis alle korrekt fungerende noder tilbyder den samme v\u00e6rdi v<\/b>, skal hver korrekt fungerende node acceptere denne v\u00e6rdi v<\/b>. <\/li>\n
    3. Afslutning <\/b>\u2013 alle korrekt fungerende noder vil til sidst acceptere en v\u00e6rdi (levende egenskab), hvilket giver algoritmen mulighed for at have fremdrift i systemet. Hver enkelt korrekt fungerende node skal en dag have accepteret den endelige v\u00e6rdi og bekr\u00e6ftet det: \"For mig er denne v\u00e6rdi sand, jeg er enig med hele systemet\".<\/li>\n<\/ol>\n

      <\/p>\n

      Eksempel p\u00e5 konsensusalgoritmens funktion<\/h4>\n

      \nSelv om egenskaberne ved algoritmen m\u00e5ske ikke er helt klare, vil vi derfor illustrere, hvilke faser den enkleste konsensusalgoritme gennemg\u00e5r i et system med en synkron kommunikationsmodel, hvor alle noder fungerer som de skal, beskeder ikke g\u00e5r tabt, og intet g\u00e5r i stykker (kan det virkelig ske?).<\/p>\n

        \n
      1. Det hele begynder med et forslag om h\u00e5nden og hjertet (Propose). Lad os antage, at en klient har tilsluttet sig noden kaldet \"Nod 1\" og p\u00e5begyndt en transaktion ved at overf\u00f8re en ny v\u00e6rdi \u2013 O. Fra dette \u00f8jeblik vil vi kalde \"Nod 1\" proposer<\/b>. Som proposer skal \"Nod 1\" nu underrette hele systemet om, at den har friske data. Den sender beskeder til alle de andre noder: \"Se! Jeg har modtaget v\u00e6rdien 'O', og jeg \u00f8nsker at gemme den! Bekr\u00e6ft venligst, at I ogs\u00e5 vil gemme 'O' i jeres log.\"\n

        \"Schr\u00f6dingers<\/li>\n

      2. N\u00e6ste fase er afstemning for den foresl\u00e5ede v\u00e6rdi (Voting). Hvad er form\u00e5let med den? Det kan ske, at andre noder har modtaget mere friske oplysninger, og at de har data vedr\u00f8rende den samme transaktion.\n

        \"Schr\u00f6dingers
        \n
        \nN\u00e5r noden \"Nod 1\" sender sit proposal, kontrollerer de andre noder deres logfiler for data relateret til denne h\u00e6ndelse. Hvis der ikke er nogen uoverensstemmelser, erkl\u00e6rer noderne: \"Ja, jeg har ingen andre data vedr\u00f8rende denne h\u00e6ndelse. V\u00e6rdien 'O' er de nyeste oplysninger, vi har f\u00e5et.\" <\/p>\n

        I alle andre tilf\u00e6lde kan noderne svare til \"Nod 1\": \"H\u00f8r her! Jeg har mere friske data om denne transaktion. Ikke 'O', men noget bedre.\"<\/p>\n

        I afstemningsfasen tr\u00e6ffer noderne en beslutning: enten accepterer alle samme v\u00e6rdi, eller en af dem stemmer imod, hvilket angiver, at den har mere friske data. <\/li>\n

      3. Hvis afstemningsrunden er vellykket, og alle stemmer 'ja', g\u00e5r systemet videre til en ny fase \u2013 accept af v\u00e6rdien (Accept). \"Nod 1\" indsamler alle svar fra de andre noder og meddeler: \"Alle er enige om v\u00e6rdien 'O'! Jeg erkl\u00e6rer nu officielt, at 'O' er vores nye v\u00e6rdi, f\u00e6lles for alle! Skriv det ned i jeres b\u00f8ger, glem det ikke. Skriv det i jeres log!\"\n

        \"Schr\u00f6dingers<\/li>\n

      4. De andre noder sender bekr\u00e6ftelse (Accepted) om, at de har gemt v\u00e6rdien 'O', og der er ikke kommet noget nyt i mellemtiden (en slags to-faset commit). Efter denne betydningsfulde begivenhed betragter vi, at den distribuerede transaktion er gennemf\u00f8rt.
        \n \"Schr\u00f6dingers <\/li>\n<\/ol>\n

        \nP\u00e5 den m\u00e5de best\u00e5r konsensusalgoritmen i den enkle situation af fire trin: propose, afstemning (voting), accept (accept), bekr\u00e6ftelse af accept (accepted).<\/p>\n

        Hvis vi ikke kan opn\u00e5 enighed p\u00e5 et hvilket som helst trin, starter algoritmen forfra med in mente den information, de noder, der n\u00e6gtede at bekr\u00e6fte den foresl\u00e5ede v\u00e6rdi, vil give.<\/p>\n

        Konsensusalgoritme i et asynkront system<\/h2>\n

        \nIndtil nu har alt v\u00e6ret glat, for vi har talt om en synkron model for meddelelsesudveksling. Men vi ved, at vi i den moderne verden er vant til at g\u00f8re alt asynkront. Hvordan fungerer den tilsvarende algoritme i et system med en asynkron meddelelsesmodel, hvor vi antager, at ventetiden p\u00e5 et svar fra en node kan v\u00e6re ubegribelig lang (forresten kan en nodes nedbrud ogs\u00e5 betragtes som et eksempel, hvor noden kan svare uendeligt langsomt). <\/p>\n

        Nu, n\u00e5r vi ved, hvordan konsensusalgoritmen grundl\u00e6ggende fungerer, stilles der et sp\u00f8rgsm\u00e5l til de nysgerrige l\u00e6sere, som er n\u00e5et hertil: Hvor mange noder i et system med N noder med asynkron meddelelsesmodel kan g\u00e5 ned, s\u00e5 systemet stadig kan opn\u00e5 konsensus?<\/p><\/blockquote>\n

        \nDet rigtige svar og begrundelse er bag spoileren.<\/b>Det rigtige svar: 0<\/b>. Hvis blot \u00e9n node i et asynkront system g\u00e5r ned, kan systemet ikke opn\u00e5 konsensus. Denne p\u00e5stand er bevist i den kendte teorem FLP (1985, Fischer, Lynch, Paterson, henvisning til det originale i slutningen af artiklen): \"Det er umuligt at opn\u00e5 distribueret konsensus, n\u00e5r mindst \u00e9n node g\u00e5r ud af drift.\"
        \n\"Schr\u00f6dingers
        \nDrenge, s\u00e5 har vi et problem, vi er vant til, at alt er asynkront. Og s\u00e5 er der dette. Hvordan skal vi s\u00e5 leve videre? <\/p>\n

        Vi har lige talt om teorien, om matematikken. Hvad betyder \"konsensus ikke kan opn\u00e5s\" n\u00e5r vi overs\u00e6tter fra matematiksprog til vores - ingeni\u00f8rm\u00e6ssige? Det betyder, at \"det ikke altid kan opn\u00e5s\", dvs. der findes et tilf\u00e6lde, hvor konsensus ikke er muligt. Hvad er dette tilf\u00e6lde? <\/p>\n

        Dette er netop en overtr\u00e6delse af liveness property, som beskrevet ovenfor. Vi har ikke enighed, og systemet kan ikke have fremskridt (kan ikke afsluttes inden for en endelig tid), n\u00e5r vi ikke har svar fra alle noder. Fordi i et asynkront system har vi ikke forudsigelig svartid, og vi kan ikke vide, om en node er g\u00e5et ned eller blot svarer langsomt.<\/p>\n

        Men i praksis kan vi finde en l\u00f8sning. Lad vores algoritme kunne fungere l\u00e6nge ved fejl (kan potentielt fungere uendeligt). Men i de fleste situationer, n\u00e5r de fleste noder fungerer korrekt, vil vi have fremskridt i systemet. <\/p>\n

        I praksis arbejder vi med delvist synkrone kommunikationsmodeller. Delvis synkronisering forst\u00e5s s\u00e5ledes: I almindelighed har vi en asynkron model, men der indf\u00f8res formelt et begreb kaldet 'global stabiliseringstid' for et bestemt tidspunkt. <\/p>\n

        Dette tidspunkt kan muligvis ikke opst\u00e5 i lang tid, men en dag skal det komme. En virtuel alarm vil ringe, og fra dette \u00f8jeblik kan vi forudsige tidsdeltaget, som det vil tage for beskederne at n\u00e5 frem. Fra dette \u00f8jeblik omdannes systemet fra asynkront til synkront. I praksis arbejder vi netop med s\u00e5danne systemer. <\/p>\n

        Paxos-algoritmen l\u00f8ser konsensusproblemer<\/h2>\n

        \nPaxos <\/a><\/noindex> - er en familie af algoritmer, som l\u00f8ser konsensusproblemet for delvist synkrone systemer, forudsat at nogle noder kan fejle. Forfatteren af Paxos er Leslie Lamport<\/a><\/noindex>. Han pr\u00e6senterede et formelt bevis p\u00e5 eksistensen og korrektheden af algoritmen i 1989. <\/p>\n

        Men beviset viste sig at v\u00e6re alt andet end trivielt. Den f\u00f8rste publikation blev udgivet f\u00f8rst i 1998 (33 sider) med en beskrivelse af algoritmen. Det viste sig, at den var ekstremt sv\u00e6r at forst\u00e5, og i 2001 blev der offentliggjort en forklaring p\u00e5 artiklen, som fyldte 14 sider. Omfanget af publikationerne er angivet for at vise, at konsensusproblemet faktisk ikke er simpelt, og at der ligger enorme anstrengelser fra kloge mennesker bag s\u00e5danne algoritmer.<\/p>\n

        Interessant nok bem\u00e6rkede Leslie Lamport selv i sin forel\u00e6sning, at der i den anden forklarende artikel er en s\u00e6tning, en linje (han specificerede ikke hvilken), som kan tolkes p\u00e5 forskellige m\u00e5der. Og p\u00e5 grund af dette fungerer mange moderne implementeringer af Paxos ikke helt korrekt. <\/p><\/blockquote>\n

        \nEn detaljeret gennemgang af Paxos' funktionalitet vil kr\u00e6ve mere end \u00e9n artikel, s\u00e5 jeg vil fors\u00f8ge kort at formidle den grundl\u00e6ggende id\u00e9 bag algoritmen. I linksene i slutningen af min artikel kan du finde materialer til videre fordybelse i emnet.<\/p>\n

        Roller i Paxos<\/h4>\n

        \nI Paxos-algoritmen findes der et begreb om roller. Lad os se p\u00e5 tre grundl\u00e6ggende (der er modificationer med ekstra roller):<\/p>\n

          \n
        1. Proposers (der kan ogs\u00e5 findes termer som: ledere eller koordinatorer)<\/b>. Dette er fyre, der l\u00e6rer om en ny betydning fra brugeren og tager rollen som leder. Deres opgave er at starte en runde med at foresl\u00e5 en ny betydning og koordinere de efterf\u00f8lgende handlinger fra noderne. Paxos tillader desuden, at der i bestemte situationer kan v\u00e6re flere ledere.<\/li>\n
        2. Acceptorer (V\u00e6lgere)<\/b>. Dette er noder, der stemmer for eller imod accepten af en eller anden v\u00e6rdi. Deres rolle er meget vigtig, fordi det afh\u00e6nger af dem, hvilken tilstand systemet vil overg\u00e5 til (eller ikke overg\u00e5 til) efter n\u00e6ste fase af konsensusalgoritmen.<\/li>\n
        3. L\u00e6rere<\/b>. Noder, der blot modtager og registrerer den nyeste accepterede v\u00e6rdi, n\u00e5r systemets tilstand \u00e6ndres. De tr\u00e6ffer ikke beslutninger, men modtager data og kan videregive dem til slutbrugeren. <\/li>\n<\/ol>\n

          \nEn enkelt node kan kombinere flere roller i forskellige situationer. <\/p>\n

          Begrebet quorum<\/h4>\n

          \nVi antager, at vi har et system med N<\/b> noder. Og maksimalt F<\/b> noder kan svigte. Hvis F noder svigter, betyder det, at vi i klyngen skal have mindst 2F + 1<\/b> acceptor-noder. <\/p>\n

          Dette er n\u00f8dvendigt, s\u00e5 vi altid, selv i den v\u00e6rste situation, har et flertal af \"gode\", korrekt fungerende noder. Det vil sige, at vi har F + 1<\/b> \"gode\" noder, som har accepteret, og den endelige v\u00e6rdi vil blive vedtaget. Ellers kan der opst\u00e5 situationer, hvor forskellige lokale grupper vil acceptere forskellige v\u00e6rdier og ikke kan blive enige. Derfor har vi brug for et absolut flertal for at vinde afstemningen.<\/p>\n

          Den overordnede id\u00e9 bag Paxos konsensusalgoritmen<\/h4>\n

          \nPaxos-algoritmen har to store faser, som hver i sig selv opdeles i to skridt:<\/p>\n

            \n
          1. Fase 1a: Forbered<\/b>. I forberedelsesfasen informerer lederen (proposer) alle noder: \u201eVi starter en ny afstemningsfase. Vi har en ny runde. Nummeret p\u00e5 denne runde er n. Nu begynder vi at afgive stemmer\u201c. Indtil nu fort\u00e6ller han blot om starten p\u00e5 en ny cyklus, men han angiver ikke en ny v\u00e6rdi. Form\u00e5let med denne fase er at igangs\u00e6tte en ny runde og informere alle om dens unikke nummer. Runde nummeret er vigtigt, det skal v\u00e6re et tal, der er st\u00f8rre end alle tidligere afstemningsnumre fra alle tidligere ledere. Netop fordi rundenummeret g\u00f8r, at andre noder i systemet forst\u00e5r, hvor friske dataene er hos lederen. Det er sandsynligt, at andre noder allerede har afstemningsresultater fra meget senere runder, og de vil blot fort\u00e6lle lederen, at han er bagud.<\/li>\n
          2. Fase 1b: L\u00f8fte<\/b>. N\u00e5r acceptor-noderne modtager nummeret p\u00e5 den nye afstemningsrunde, er der to mulige udfald: \n