{"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\/hr\/blog\/administrirovanie\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","title":{"rendered":"Ma\u010dka Schr\u00f6dinger bez kutije: problem konsenzusa u distribuiranim sustavima","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Zamislite sljede\u0107e. U prostoriji su zaklju\u010dana 5 ma\u010daka, i kako bi oti\u0161le probuditi vlasnika, moraju se zajedno dogovoriti o tome, jer mogu otvoriti vrata samo zajedno, nasloniv\u0161i se na njih. Ako je jedna od ma\u010daka ma\u010dka Schr\u00f6dinger, a ostale ma\u010dke ne znaju za njezinu odluku, postavlja se pitanje: \"Kako to mogu u\u010diniti?\" <\/p>\n

U ovom \u010dlanku \u0107u vam jednostavnim jezikom objasniti teoretske osnove svijeta distribuiranih sustava i principe njihovog rada. Tako\u0111er, povr\u0161no \u0107u razmotriti glavnu ideju koja le\u017ei u osnovi Paxosa. <\/p>\n

\"Ma\u010dka
\n<\/a><\/noindex>
\nKada programeri koriste obla\u010dne infrastrukture, razli\u010dite baze podataka i rade u klasterima s velikim brojem \u010dvorova, uvjereni su da \u0107e podaci biti cjeloviti, o\u010duvani i uvijek dostupni. No, odakle dolaze jamstva?<\/p>\n

U su\u0161tini, jamstva koja imamo su jamstva davatelja usluga. Oni su opisana u dokumentaciji otprilike ovako: \u201eOva usluga je dovoljno pouzdana, ima zadani SLA, ne brinite, sve \u0107e raditi distribuirano, kao \u0161to o\u010dekujete.\u201c <\/p>\n

Skloni smo vjerovati u najbolje, jer nas pametni mu\u0161ki iz velikih kompanija uvjeravaju da \u0107e sve biti u redu. Ne postavljamo si pitanje: za\u0161to bi ovo uop\u0107e moglo raditi? Ima li nekog formalnog opravdanja ispravnosti rada takvih sustava?<\/p>\n

Nedavno sam i\u0161ao na \u0161kolu o distribuiranim ra\u010dunalnim sustavima<\/a><\/noindex> i bio sam jako inspiriran ovom temom. Predavanja u \u0161koli vi\u0161e su podsje\u0107ala na satove iz matemati\u010dke analize nego na ne\u0161to vezano uz ra\u010dunalne sustave. No, upravo su tako u svoje vrijeme dokazivani najva\u017eniji algoritmi koje svakodnevno koristimo, a da toga nismo ni svjesni. <\/p>\n

U ve\u0107ini modernih distribuiranih sustava koristi se algoritam konsenzusa Paxos i njegove razne modifikacije. Najbolje je \u0161to se opravdanost i, u principu, sama mogu\u0107nost postojanja ovog algoritma mo\u017ee dokazati jednostavno uz pomo\u0107 olovke i papira. Pri tom se algoritam prakti\u010dno primjenjuje u velikim sustavima koji rade na ogromnom broju \u010dvorova u oblacima. <\/p>\n

Lagana ilustracija o \u010demu \u0107e se dalje raditi: zadatak dvaju generala<\/b>Hajde da se malo razgibamo analizom zadatka dvaju generala<\/a><\/noindex>. <\/p>\n

Imamo dvije vojske \u2013 crvenu i bijelu. Bijele trupe su smje\u0161tene u opsjednutom gradu. Crvene trupe pod vodstvom generala A1 i A2 nalaze se s obje strane grada. Zadatak crvenih je napasti bijeli grad i pobijediti. Me\u0111utim, vojska svakog crvenog generala pojedina\u010dno je manja od vojske bijelih.<\/p>\n

\"Ma\u010dka
\n
\nUvjeti pobjede za crvene: obojica generala moraju napasti istovremeno kako bi imali broj\u010danu prednost nad bijelima. Za to se generali A1 i A2 trebaju dogovoriti me\u0111usobno. Ako svaki napadne pojedina\u010dno, crveni \u0107e izgubiti. <\/p>\n

Da bi se dogovorili, generali A1 i A2 mogu slati glasnike jedni drugima kroz teritorij bijelog grada. Glasnik mo\u017ee uspje\u0161no do\u0107i do saveznika ili ga mo\u017ee uhvatiti protivnik. Pitanje je: postoji li takva sekvenca komunikacija izme\u0111u crvenih generala (sekvenca slanja glasnika od A1 do A2 i obrnuto od A2 do A1), u kojoj \u0107e se oni jam\u010divo dogovoriti o napadu u \u010das X. Ovdje, pod jamstvima podrazumijevamo da \u0107e obojica generala imati jednozna\u010dnu potvrdu da saveznik (drugi general) sigurno napada u dogovoreno vrijeme X.<\/p>\n

Pretpostavimo da A1 \u0161alje glasnika A2 s porukom: \u201eNapadnimo danas u pono\u0107!\u201c. General A1 ne mo\u017ee napasti bez potvrde od generala A2. Ako je glasnik od A1 stigao, tada general A2 \u0161alje potvrdu s porukom: \u201eDa, napadnimo danas bijele\u201c. No sada general A2 ne zna je li njegov glasnik stigao ili ne, nema jamstava da \u0107e napad biti simultan. Sada generalu A2 opet treba potvrda.<\/p>\n

Ako se nastavi s njihovom komunikacijom, otkriva se sljede\u0107e: koliko god ciklusa razmjene poruka bilo, ne postoji na\u010din da se jam\u010dito obavijeste obojica generala o tome da su njihove poruke primljene (pod uvjetom da bilo koji glasnik mo\u017ee biti uhva\u0107en).<\/p>\n

Zadatak dva generala odli\u010dna je ilustracija vrlo jednostavnog distribuiranog sustava, gdje postoje dva \u010dvora s nepouzdanom komunikacijom. To zna\u010di da nemamo 100% jamstvo da \u0107e se sinkronizirati. O sli\u010dnim problemima, ali na ve\u0107em razmjeru, bit \u0107e rije\u010di dalje u \u010dlanku.<\/p>\n

Uvodimo pojam distribuiranih sustava.<\/h2>\n

\nDistribuirani sustav je skup ra\u010dunala (dalje \u0107emo ih zvati \u010dvorovima) koji mogu razmjenjivati poruke. Svaki pojedini \u010dvor je autonomna entitet. \u010cvor mo\u017ee samostalno obra\u0111ivati zadatke, ali da bi komunicirao s drugim \u010dvorovima, mora slati i primati poruke. <\/p>\n

Kako su poruke konkretno implementirane, koje se protokoli koriste \u2013 to nas ne zanima u ovom kontekstu. Va\u017eno je da \u010dvorovi distribuiranog sustava mogu razmjenjivati podatke me\u0111usobno slanjem poruka.<\/p>\n

Samo definicija izgleda prili\u010dno jednostavno, ali treba uzeti u obzir da distribuirani sustav ima brojne atribute koji \u0107e nam biti va\u017eni.<\/p>\n

Atributi distribuiranih sustava<\/h4>\n

<\/p>\n

    \n
  1. Konkurentnost<\/b> je mogu\u0107nost nastanka istovremenih ili konkurentnih doga\u0111aja u sustavu. \u0160tovi\u0161e, smatrat \u0107emo da su doga\u0111aji koji su se dogodili na dva razli\u010dita \u010dvora potencijalno konkurentni sve dok nemamo jasan redoslijed nastanka tih doga\u0111aja. A, obi\u010dno, nemamo.<\/li>\n
  2. Nedostatak globalnog vremena<\/b>. Nemamo jasan redoslijed doga\u0111aja zbog nedostatka globalnog vremena. U obi\u010dnom ljudskom svijetu navikli smo da imamo satove i apsolutno vrijeme. Sve se mijenja kada se radi o distribuiranim sustavima. \u010cak i najto\u010dniji atomski satovi imaju pomake, a mogu\u0107a su i stanja kada ne mo\u017eemo re\u0107i koji od dva doga\u0111aja se dogodio ranije. Stoga se ne mo\u017eemo oslanjati na vrijeme.<\/li>\n
  3. Neovisno otkazivanje \u010dvorova sustava<\/b>. Postoji jo\u0161 jedan problem: ne\u0161to mo\u017ee po\u0107i po zlu jednostavno zato \u0161to na\u0161i \u010dvorovi nisu vje\u010dni. Mo\u017ee otkazati tvrdi disk, virtualka u oblaku se mo\u017ee ponovno pokrenuti, mre\u017ea mo\u017ee zatreptati i poruke se mogu izgubiti. \u0160tovi\u0161e, mogu\u0107a su i stanja kada \u010dvorovi rade, ali istovremeno djeluju protiv sustava. Posljednja klasa problema \u010dak je dobila posebno ime: problem bizantskih generala<\/a><\/noindex>. Najpopularniji primjer distribuiranog sustava s ovakvim problemom je Blockchain. No, danas ne\u0107emo razmatrati ovu posebnu klasu problema. Zanimat \u0107e nas situacije u kojima jednostavno jedan ili vi\u0161e \u010dvorova mogu otkazati.<\/li>\n
  4. Modeli komunikacije (modeli razmjene poruka) izme\u0111u \u010dvorova<\/b>. Utvrdili smo da \u010dvorovi komuniciraju putem razmjene poruka. Postoje dva poznata modela razmjene poruka: sinkroni i asinkroni.<\/li>\n<\/ol>\n

    <\/p>\n

    Modeli komunikacije izme\u0111u \u010dvorova u distribuiranim sustavima<\/h4>\n

    \nSinkroni model<\/b> \u2013 znamo to\u010dno da postoji kona\u010dna poznata delta vremena u kojoj poruka garancirano dolazi s jednog \u010dvora na drugi. Ako to vrijeme istekne, a poruka nije stigla, mo\u017eemo sigurno re\u0107i da je \u010dvor otkazao. U takvom modelu imamo predvidivo vrijeme \u010dekanja. <\/p>\n

    Asinkroni model<\/b> \u2013 u asinkronim modelima smatramo da je vrijeme \u010dekanja kona\u010dno, ali ne postoji takva delta vremena nakon koje mo\u017eemo jam\u010diti da je \u010dvor otkazao. Tj. vrijeme \u010dekanja poruke od \u010dvora mo\u017ee biti proizvoljno dugo. Ovo je va\u017eno definiranje, i o tome \u0107emo dalje razgovarati. <\/p>\n

    Pojam konzensa u distribuiranim sustavima<\/h2>\n

    \nPrije formalne definicije pojma konzensa, razmotrimo primjer situacije u kojoj nam je potreban, a to je \u2013 Replikacija strojne dr\u017eave<\/b>. <\/p>\n

    Imamo neki distribuirani zapis. \u017deljeli bismo da bude dosljedan i da sadr\u017ei identi\u010dne podatke na svim \u010dvorovima distribuiranog sustava. Kada neki od \u010dvorova sazna novu vrijednost koju \u017eeli zabilje\u017eiti u zapis, njegov zadatak postaje predlo\u017eiti tu vrijednost svim ostalim \u010dvorovima kako bi se zapis a\u017eurirao na svim \u010dvorovima i sustav pre\u0161ao u novo dosljedno stanje. Pritom je va\u017eno da se \u010dvorovi dogovore: svi \u010dvorovi su se slo\u017eili da je predlo\u017eena nova vrijednost ispravna, svi \u010dvorovi su prihvatili tu vrijednost, i samo u tom slu\u010daju svi mogu zabilje\u017eiti novu vrijednost u zapis. <\/p>\n

    Drugim rije\u010dima: nitko od \u010dvorova nije prigovorio da ima a\u017eurirane informacije, a predlo\u017eena vrijednost je neto\u010dna. Dogovor izme\u0111u \u010dvorova i suglasnost o jedinstvenoj ispravnoj prihva\u0107enoj vrijednosti jest konsenzus u distribuiranom sustavu. Dalje \u0107emo govoriti o algoritmima koji omogu\u0107uju da distribuirani sustav garantirano postigne konsenzus.
    \n\"Ma\u010dka
    \nMo\u017eemo formalno definirati algoritam postizanja konsenzusa (ili jednostavno algoritam konsenzusa) kao funkciju koja prenosi distribuirani sustav iz stanja A u stanje B. Ovo stanje trebaju prihvatiti svi \u010dvorovi, a svi \u010dvorovi ga moraju potvrditi. Kako pokazuje iskustvo, ovaj zadatak nije nimalo trivijalan kao \u0161to se na prvi pogled \u010dini.<\/p>\n

    Svojstva algoritma konsenzusa<\/h4>\n

    \nAlgoritam konsenzusa mora imati tri svojstva kako bi sustav mogao postojati i napredovati u prijelazu iz jednog stanja u drugo:<\/p>\n

      \n
    1. Sporazum <\/b> \u2013 svi ispravno funkcioniraju\u0107i \u010dvorovi moraju prihvatiti istu vrijednost (u literaturi, ovo svojstvo se tako\u0111er naziva svojstvo sigurnosti). Svi \u010dvorovi koji trenutno rade (nisu u kvaru i nisu izgubili vezu s ostalima) trebaju posti\u0107i sporazum i prihvatiti neku kona\u010dnu zajedni\u010dku vrijednost.\n

      Ovdje je va\u017eno razumjeti da \u010dvorovi u ovom distribuiranom sustavu \u017eele posti\u0107i dogovor. Drugim rije\u010dima, govorimo o sustavima u kojima mo\u017ee do\u0107i do kvara (na primjer, neki \u010dvor mo\u017ee otkazati), ali u ovom sustavu nema \u010dvorova koji namjerno djeluju protiv drugih (zadatak bizantijskih generala). Zbog ovog svojstva sustav ostaje konzistentan.<\/li>\n

    2. Integritet <\/b> \u2013 ako svi ispravno funkcioniraju\u0107i \u010dvorovi nude istu vrijednost v<\/b>, svaki ispravno funkcioniraju\u0107i \u010dvor mora prihvatiti tu vrijednost v<\/b>. <\/li>\n
    3. Zavr\u0161etak <\/b>\u2013 svi ispravno funkcioniraju\u0107i \u010dvorovi na kraju \u0107e prihvatiti neku vrijednost (svojstvo aktivnosti), \u0161to omogu\u0107uje algoritmu napredovanje u sustavu. Svaki pojedina\u010dni ispravno funkcioniraju\u0107i \u010dvor mora prije ili kasnije prihvatiti kona\u010dnu vrijednost i potvrditi to: \u201eZa mene, ova vrijednost je istinita, sla\u017eem se s cijelim sustavom.\u201c<\/li>\n<\/ol>\n

      <\/p>\n

      Primjer rada algoritma konsenzusa<\/h4>\n

      \nDok svojstva algoritma mo\u017eda nisu potpuno jasna, ilustrirajmo na primjeru koje faze prolazi najjednostavniji algoritam konsenzusa u sustavu s sinkronim modelom razmjene poruka, gdje svi \u010dvorovi rade ispravno, poruke se ne gube i ni\u0161ta se ne kvari (stvarno li se to doga\u0111a?).<\/p>\n

        \n
      1. Sve po\u010dinje s prijedlogom ruke i srca (Propose). Pretpostavimo da se klijent povezao na \u010dvor nazvan \"\u010cvor 1\" i zapo\u010deo transakciju, \u0161aljuci \u010dvoru novu vrijednost \u2013 O. Od ovog trenutka \"\u010cvor 1\" nazivamo proposer<\/b>. Kao proposer, \"\u010cvor 1\" sada mora obavijestiti cijeli sustav da ima nove podatke i \u0161alje poruke svim ostalim \u010dvorovima: \"Gledajte! Primio sam vrijednost 'O', i \u017eelim je zapisati! Molim vas, potvrdite da \u0107ete i vi zapisati 'O' u svoj log.\"\n

        \"Ma\u010dka<\/li>\n

      2. Sljede\u0107a faza je glasovanje za predlo\u017eenu vrijednost (Voting). Za\u0161to je to potrebno? Mo\u017ee se dogoditi da su drugim \u010dvorovima do\u0161le novije informacije i da imaju podatke o istoj transakciji.\n

        \"Ma\u010dka
        \n
        \nKada \u010dvor \"\u010cvor 1\" po\u0161alje svoj prijedlog, ostali \u010dvorovi provjeravaju u svojim logovima podatke o ovom doga\u0111aju. Ako nema proturje\u010dnosti, \u010dvorovi objavljuju: \"Da, nemam drugih podataka o ovom doga\u0111aju. Vrijednost 'O' je najnovija informacija koju smo dobili.\" <\/p>\n

        U svakom drugom slu\u010daju, \u010dvorovi mogu odgovoriti \"\u010cvoru 1\": \"Slu\u0161aj! Imam novije podatke o ovoj transakciji. Ne 'O', nego ne\u0161to bolje.\"<\/p>\n

        U fazi glasovanja \u010dvorovi donose odluku: ili svi prihva\u0107aju jednu vrijednost, ili netko od njih glasa protiv, ozna\u010davaju\u0107i da ima novije podatke. <\/li>\n

      3. Ako je krug glasovanja pro\u0161ao uspje\u0161no, i svi su bili 'za', sustav prelazi u novu fazu - prihva\u0107anje vrijednosti (Accept). \"\u010cvor 1\" prikuplja sve odgovore drugih \u010dvorova i javlja: \"Svi su se slo\u017eili s vrijedno\u0161\u0107u 'O'! Sada slu\u017ebeno izjavljujem da je 'O' na\u0161a nova vrijednost, jedinstvena za sve! Zapisujte u svoju knji\u017eicu, ne zaboravite. Zapisujte u svoj log!\"\n

        \"Ma\u010dka<\/li>\n

      4. Ostali \u010dvorovi \u0161alju potvrdu (Accepted) da su zapisali vrijednost 'O', ni\u0161ta novo tijekom tog vremena nije pristiglo (svojstveni dvofazni commit). Nakon ovog zna\u010dajnog doga\u0111aja, smatramo da je distribuirana transakcija izvr\u0161ena.
        \n \"Ma\u010dka <\/li>\n<\/ol>\n

        \nTako algoritam konsenzusa u jednostavnom slu\u010daju sastoji se od \u010detiri koraka: propose, glasovanje (voting), prihva\u0107anje (accept), potvrda prihva\u0107anja (accepted).<\/p>\n

        Ako na nekom koraku nismo uspjeli posti\u0107i saglasnost, algoritam se pokre\u0107e ispo\u010detka, uzimaju\u0107i u obzir informacije koje \u0107e pru\u017eiti \u010dvorovi koji su odbili potvrditi predlo\u017eenu vrijednost.<\/p>\n

        Konsenzus algoritam u asinkronom sustavu<\/h2>\n

        \nDo sada je sve bilo jednostavno, jer se radilo o sinkronom modelu razmjene poruka. No, mi znamo da smo u modernom svijetu navikli raditi asinkrono. Kako onda sli\u010dan algoritam funkcionira u sustavu s asinkronim modelom razmjene poruka, gdje smatramo da vrijeme \u010dekanja na odgovor od \u010dvora mo\u017ee biti proizvoljno dugo (usput, kvar \u010dvora tako\u0111er mo\u017eemo smatrati primjerom kada \u010dvor mo\u017ee odgovarati koliko god dugo \u017eeli). <\/p>\n

        Sada kada znamo kako algoritam konsenzusa u osnovi funkcionira, pitanje za znati\u017eeljne \u010ditatelje koji su stigli do ovog mjesta: koliko \u010dvorova u sustavu od N \u010dvorova s asinkronim modelom poruka mo\u017ee otkazati da bi sustav i dalje mogao posti\u0107i konsenzus?<\/p><\/blockquote>\n

        \nTo\u010dan odgovor i obja\u0161njenje su ispod.<\/b>To\u010dan odgovor: 0<\/b>. Ako barem jedan \u010dvor u asinkronom sustavu otka\u017ee, sustav ne mo\u017ee posti\u0107i konsenzus. Ova tvrdnja je dokazana u poznatoj teoremi FLP (1985, Fischer, Lynch, Paterson, izvor u zavr\u0161nom dijelu \u010dlanka): \u201eNemogu\u0107nost postizanja distribuiranog konsenzusa pri otkazu barem jednog \u010dvora\u201c.
        \n\"Ma\u010dka
        \nDakle, imamo problem, navikli smo da je sve asinkrono. A sada ovo. Kako dalje \u017eivjeti? <\/p>\n

        Sada smo govorili o teoriji, o matematici. \u0160to zna\u010di \u201ekonsenzus se ne mo\u017ee posti\u0107i\u201c, prevo\u0111enjem s matemati\u010dkog jezika na na\u0161 \u2013 in\u017eenjerski? To zna\u010di da \u201ene mo\u017ee uvijek biti postignut\u201c, tj. postoji slu\u010daj u kojem konsenzus nije mogu\u0107e posti\u0107i. A koji je to slu\u010daj? <\/p>\n

        To je zapravo kr\u0161enje svojstva \u017eivosti, opisano iznad. Nemamo zajedni\u010dki dogovor, i sustav ne mo\u017ee napredovati (ne mo\u017ee zavr\u0161iti u kona\u010dnom vremenu) u slu\u010daju kada nemamo odgovor od svih \u010dvorova. Jer u asinkronom sustavu nemamo predvidivo vrijeme odgovora, i ne mo\u017eemo znati je li \u010dvor otkazao ili samo dugo odgovara.<\/p>\n

        No, u praksi mo\u017eemo prona\u0107i re\u0161enje. Neka na\u0161 algoritam mo\u017ee raditi dugo u slu\u010daju otkaza (potencijalno mo\u017ee raditi beskona\u010dno). No, u ve\u0107ini situacija, kada ve\u0107ina \u010dvorova ispravno funkcionira, imat \u0107emo napredak u sustavu. <\/p>\n

        U praksi se susre\u0107emo s djelomi\u010dno sinkronim komunikacijskim modelima. Djelomi\u010dna sinkronost se shva\u0107a ovako: op\u0107enito imamo asinkroni model, ali se formalno uvodi koncept \u201eglobal stabilization time\u201c nekog vremenskog trenutka. <\/p>\n

        Ovaj vremenski trenutak mo\u017ee se ne ostvarivati beskrajno dugo, ali jednom mora do\u0107i. Aktivirat \u0107e se virtualni alarm, i od tog trenutka mo\u017eemo predvidjeti delta vremena potrebno da poruke stignu. Od tog trenutka sustav se iz asinkronog pretvara u sinkroni. U praksi se radi upravo o takvim sustavima. <\/p>\n

        Paxos algoritam rje\u0161ava probleme konsenzusa<\/h2>\n

        \nPaxos <\/a><\/noindex> \u2013 to je porodica algoritama koji rje\u0161avaju problem konsenzusa za djelomi\u010dno sinkrone sustave, pod uvjetom da neki \u010dvorovi mogu otkazati. Autor Paxosa je Leslie Lamport<\/a><\/noindex>. On je 1989. godine predlo\u017eio formalni dokaz o postojanju i to\u010dnosti algoritma. <\/p>\n

        No, dokaz se pokazao daleko od trivijalnog. Prva publikacija objavljena je tek 1998. godine (33 stranice) s opisom algoritma. Kako se ispostavilo, bila je izuzetno te\u0161ka za razumijevanje, a 2001. godine objavljeno je obja\u0161njenje \u010dlanka koje je zauzelo 14 stranica. Obujam publikacija naveden je kako bi se pokazalo da je problem konsenzusa zapravo vrlo slo\u017een i da iza takvih algoritama stoji ogroman trud najpametnijih ljudi.<\/p>\n

        Zanimljivo je da je sam Leslie Lamport u svom predavanju primijetio da u drugom \u010dlanku-obja\u0161njenju postoji jedno tvrdnja, jedna re\u010denica (nije precizirao koja), koja se mo\u017ee razli\u010dito tuma\u010diti. Zbog toga veliki broj modernih implementacija Paxosa ne radi potpuno ispravno. <\/p><\/blockquote>\n

        \nDetaljna analiza rada Paxosa zahtijevat \u0107e vi\u0161e od jednog \u010dlanka, stoga \u0107u poku\u0161ati vrlo sa\u017eeto prenijeti glavnu ideju algoritma. U linkovima na kraju mog \u010dlanka prona\u0107i \u0107ete materijale za daljnje istra\u017eivanje ove teme.<\/p>\n

        Uloge u Paxosu<\/h4>\n

        \nU algoritmu Paxos postoji pojam uloga. Razmotrit \u0107emo tri osnovne (postoje modifikacije s dodatnim ulogama):<\/p>\n

          \n
        1. Proposers (tako\u0111er se mogu susresti termini: vo\u0111e ili koordinatori)<\/b>. To su momci koji saznaju o nekom novom predlogu od korisnika i preuzimaju ulogu lidera. Njihov zadatak je da pokrenu krug predlaganja novog vrednovanja i koordiniraju daljnje akcije \u010dvorova. Osim toga, Paxos dopu\u0161ta postojanje vi\u0161e lidera u odre\u0111enim situacijama.<\/li>\n
        2. Priznavaoci (Glasa\u010di)<\/b>. To su \u010dvorovi koji glasaju za usvajanje ili odbijanje odre\u0111enog vrednovanja. Njihova uloga je veoma va\u017ena, jer upravo od njih zavisi odluka: u koje stanje \u0107e pre\u0107i (ili ne\u0107e pre\u0107i) sistem nakon slede\u0107e faze algoritma konsenzusa.<\/li>\n
        3. U\u010ditelji<\/b>. \u010cvorovi koji jednostavno prihvataju i bele\u017ee novo usvojeno vrednovanje kada se stanje sistema promeni. Oni ne donose odluke, samo primaju podatke i mogu ih predati krajnjem korisniku. <\/li>\n<\/ol>\n

          \nJedan \u010dvor mo\u017ee obavljati vi\u0161e uloga u razli\u010ditim situacijama. <\/p>\n

          Pojam kvoruma<\/h4>\n

          \nPretpostavljamo da imamo sistem od N<\/b> \u010dvorova. I od njih najvi\u0161e F<\/b> \u010dvorova mo\u017ee otkazati rad. Ako F \u010dvorova otka\u017ee rad, to zna\u010di da u klasteru mora biti najmanje 2F + 1<\/b> \u010dvorova acceptora. <\/p>\n

          To je neophodno za to da uvek, \u010dak i u najgorem scenariju, imamo ve\u0107inu \u201edobrih\u201c, ispravno funkcioni\u0161u\u0107ih \u010dvorova. To jest, F + 1<\/b> \u201edobrih\u201c \u010dvorova koji su se slo\u017eili, i kona\u010dna vrednost \u0107e biti prihva\u0107ena. U suprotnom, mo\u017ee do\u0107i do situacije u kojoj razli\u010dite lokalne grupe prihvate razli\u010dite vrednosti i ne mogu se dogovoriti. Stoga nam je potrebno apsolutna ve\u0107ina da pobedimo u glasovanju.<\/p>\n

          Op\u0161ta ideja rada algoritma konsenzusa Paxos<\/h4>\n

          \nAlgoritam Paxos podrazumeva dve velike faze, koje se dalje dele na dva koraka svaka:<\/p>\n

            \n
          1. Faza 1a: Priprema<\/b>. U fazi pripreme vo\u0111a (proposer) obavje\u0161tava sve \u010dvorove: \u00abZapo\u010dinjemo novu fazu glasovanja. Imamo novi krug. Broj ovog kruga \u2013 n. Sada \u0107emo po\u010deti glasovati\u00bb. Dok samo obavje\u0161tava o po\u010detku novog ciklusa, ne objavljuje novu vrijednost. Zadatak ove faze je pokrenuti novi krug i obavijestiti sve o njegovom jedinstvenom broju. Broj kruga je va\u017ean, to mora biti vrijednost ve\u0107a od svih prethodnih brojeva glasovanja od svih prethodnih lidera. Zato \u0161to upravo zahvaljuju\u0107i broju kruga drugi \u010dvorovi u sustavu \u0107e shvatiti koliko su svje\u017ei podaci kod vo\u0111e. Vjerojatno ve\u0107 drugi \u010dvorovi imaju rezultate glasovanja iz mnogo kasnijih krugova i samo \u0107e obavijestiti vo\u0111u da je zapeo.<\/li>\n
          2. Faza 1b: Obe\u0107anje<\/b>. Kada su \u010dvorovi-acceptori primili broj nove faze glasovanja, mogu\u0107a su dva ishoda: \n