{"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\/sq\/blog\/administrirovanie\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","title":{"rendered":"Miu i Schr\u00f6dingerit pa kuti: problemi i konsensit n\u00eb sistemet e shp\u00ebrndara","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Le t\u00eb imagjinojm\u00eb. N\u00eb nj\u00eb dhom\u00eb jan\u00eb kat\u00ebr mace t\u00eb mbyllura, dhe p\u00ebr t\u00eb zgjuar zotin e tyre, ato duhet t\u00eb bien dakord me nj\u00ebra-tjetr\u00ebn, sepse dera mund t\u00eb hapet vet\u00ebm n\u00ebse t\u00eb pes\u00eb mb\u00ebshteten mbi t\u00eb. N\u00ebse nj\u00ebra prej maceve \u00ebsht\u00eb macja e Schr\u00f6dinger-it, dhe macet e tjera nuk din\u00eb p\u00ebr vendimin e tij, lind pyetja: \"Si mund ta b\u00ebjn\u00eb k\u00ebt\u00eb?\" <\/p>\n

N\u00eb k\u00ebt\u00eb artikull do t'ju shpjegoj n\u00eb m\u00ebnyr\u00eb t\u00eb thjesht\u00eb p\u00ebr p\u00ebrb\u00ebr\u00ebsin te\u043e\u0440\u0435\u0442ik t\u00eb bot\u00ebs s\u00eb sistemeve t\u00eb shp\u00ebrndara dhe parimet e funksionimit t\u00eb tyre. Gjithashtu, do t\u00eb shqyrtoj n\u00eb m\u00ebnyr\u00eb t\u00eb sip\u00ebrfaqshme iden\u00eb kryesore q\u00eb q\u00ebndron pas Paxos. <\/p>\n

\"Miu
\n<\/a><\/noindex>
\nKur zhvilluesit p\u00ebrdorin infrastrukturen cloud, bazat e t\u00eb dh\u00ebnave t\u00eb ndryshme, dhe punojn\u00eb n\u00eb klastere me nj\u00eb num\u00ebr t\u00eb madh nodash, ata jan\u00eb t\u00eb sigurt se t\u00eb dh\u00ebnat do t\u00eb jen\u00eb t\u00eb plota, t\u00eb ruajtura dhe gjithmon\u00eb t\u00eb aksesueshme. Por nga vijn\u00eb garancit\u00eb?<\/p>\n

N\u00eb thelb, garancit\u00eb q\u00eb kemi jan\u00eb garancit\u00eb e ofruesit. Ato p\u00ebrshkruhen n\u00eb dokumentacion n\u00eb k\u00ebt\u00eb m\u00ebnyr\u00eb: \"Ky sh\u00ebrbim \u00ebsht\u00eb mjaft i besuesh\u00ebm, ka nj\u00eb SLA t\u00eb caktuar, mos u shqet\u00ebsoni, gjith\u00e7ka do t\u00eb funksionoj\u00eb si\u00e7 e prisni.\" <\/p>\n

Ne kemi tendenc\u00ebn t\u00eb besojm\u00eb n\u00eb m\u00eb t\u00eb mir\u00ebn, sepse djemt\u00eb e men\u00e7ur nga kompanit\u00eb e m\u00ebdha na kan\u00eb siguruar se gjith\u00e7ka do t\u00eb shkoj\u00eb mir\u00eb. Ne nuk e shqyrtojm\u00eb pyetjen: pse, n\u00eb fakt, kjo mund t\u00eb funksionoj\u00eb? A ka ndonj\u00eb arsyetim formal p\u00ebr drejt\u00ebsin\u00eb e funksionimit t\u00eb till\u00eb t\u00eb sistemeve?<\/p>\n

S\u00eb fundmi, kam shkuar n\u00eb shkoll\u00ebn p\u00ebr llogaritjet e shp\u00ebrndara<\/a><\/noindex> dhe u frym\u00ebzova shum\u00eb nga kjo tem\u00eb. Ligj\u00ebratat n\u00eb shkoll\u00eb m\u00eb shum\u00eb i ngjanin seancave t\u00eb analiz\u00ebs matematikore, sesa di\u00e7kaje q\u00eb lidhet me sistemet kompjuterike. Por pik\u00ebrisht k\u00ebshtu jan\u00eb provuar algoritmet m\u00eb t\u00eb r\u00ebnd\u00ebsishme q\u00eb p\u00ebrdorim \u00e7do dit\u00eb, pa e kuptuar vet\u00eb. <\/p>\n

N\u00eb shumic\u00ebn e sistemeve moderne t\u00eb shp\u00ebrndara p\u00ebrdoret algoritmi i konsensusit Paxos dhe modifikimet e tij t\u00eb ndryshme. Gj\u00ebja m\u00eb e shk\u00eblqyer \u00ebsht\u00eb se arsyetueshm\u00ebria dhe, n\u00eb parim, mund\u00ebsia e ekzistenc\u00ebs s\u00eb k\u00ebtij algoritmi mund t\u00eb provohet thjesht me nj\u00eb stilolaps dhe let\u00ebr. Nd\u00ebrkoh\u00eb, n\u00eb praktik\u00eb, algoritmi aplikohet n\u00eb sisteme t\u00eb m\u00ebdha q\u00eb punojn\u00eb n\u00eb nj\u00eb num\u00ebr t\u00eb madh nodash n\u00eb cloud. <\/p>\n

Nj\u00eb ilustrim i leht\u00eb p\u00ebr at\u00eb q\u00eb do t\u00eb diskutohet m\u00eb von\u00eb: problemi i dy gjeneral\u00ebve<\/b>Le t\u00eb analizojm\u00eb p\u00ebr ngrohje problemin e dy gjeneral\u00ebve<\/a><\/noindex>. <\/p>\n

Ne kemi dy ushtri \u2013 at\u00eb kuqe dhe at\u00eb t\u00eb bardh\u00eb. Ushtria e bardh\u00eb \u00ebsht\u00eb e vendosur n\u00eb qytetin e rrethuar. Ushtria e kuqe, e udh\u00ebhequr nga gjeneral\u00ebt A1 dhe A2, pozicionohet n\u00eb dy an\u00ebt e qytetit. Detyra e kuqve \u00ebsht\u00eb t\u00eb sulmojn\u00eb qytetin e bardh\u00eb dhe t\u00eb fitojn\u00eb. Megjithat\u00eb, ushtria e \u00e7do gjenerali t\u00eb kuq ve\u00e7mas \u00ebsht\u00eb m\u00eb e vog\u00ebl se ushtria e bardh\u00eb.<\/p>\n

\"Miu
\n
\nKushtet p\u00ebr fitoren e kuqve: t\u00eb dy gjeneral\u00ebt duhet t\u00eb sulmojn\u00eb nj\u00ebkoh\u00ebsisht p\u00ebr t\u00eb pasur nj\u00eb avantazh numerik ndaj t\u00eb bardh\u00ebve. P\u00ebr k\u00ebt\u00eb, gjeneral\u00ebt A1 dhe A2 duhet t\u00eb bien n\u00eb marr\u00ebveshje me nj\u00ebri-tjetrin. N\u00ebse secili sulmon ve\u00e7mas, kuqt\u00eb do t\u00eb humbin. <\/p>\n

P\u00ebr t\u00eb r\u00ebn\u00eb dakord, gjeneral\u00ebt A1 dhe A2 mund t\u00eb d\u00ebrgojn\u00eb lajm\u00ebtar\u00eb nj\u00ebri-tjetrit p\u00ebrmes territorit t\u00eb qytetit t\u00eb bardh\u00eb. Lajm\u00ebtarit mund t'i arrij\u00eb me sukses gjenerali aleat ose mund t\u00eb kapet nga armiku. Pyetja \u00ebsht\u00eb: a ka nj\u00eb sekuenc\u00eb komunikimesh midis gjeneral\u00ebve t\u00eb kuq (sekuenca e d\u00ebrgimit t\u00eb lajm\u00ebtar\u00ebve nga A1 te A2 dhe anasjelltas nga A2 te A1), me t\u00eb cil\u00ebn ata do t\u00eb garantojn\u00eb se do t\u00eb bien dakord p\u00ebr sulmin n\u00eb or\u00ebn X. K\u00ebtu, n\u00ebn garancit\u00eb kuptohet se t\u00eb dy gjeneral\u00ebt do t\u00eb ken\u00eb nj\u00eb konfirmim t\u00eb qart\u00eb se aleati (gjenerali tjet\u00ebr) do t\u00eb sulmoj\u00eb n\u00eb or\u00ebn e caktuar X.<\/p>\n

T\u00eb supozojm\u00eb se A1 d\u00ebrgon nj\u00eb lajm\u00ebtar te A2 me nj\u00eb mesazh: \"Le t\u00eb sulmojm\u00eb sot n\u00eb mesnat\u00eb!\". Gjenerali A1 nuk mund t\u00eb sulmoj\u00eb pa nj\u00eb konfirmim nga gjenerali A2. N\u00ebse lajm\u00ebtarit nga A1 iu arrit, at\u00ebher\u00eb gjenerali A2 d\u00ebrgon nj\u00eb konfirmim me mesazhin: \"Po, le t\u00eb shkat\u00ebrrojm\u00eb t\u00eb bardh\u00ebt sot\". Por tani gjenerali A2 nuk e di n\u00ebse lajm\u00ebtarit i ka arritur ose jo, nuk ka garanci se sulmi do t\u00eb jet\u00eb nj\u00ebkoh\u00ebsisht. Tani gjeneralit A2 i nevojitet p\u00ebrs\u00ebri nj\u00eb konfirmim.<\/p>\n

N\u00ebse e p\u00ebrshkruajm\u00eb m\u00eb tej komunikimin e tyre, do t\u00eb dal\u00eb n\u00eb pah se sa her\u00eb q\u00eb t\u00eb ket\u00eb cikle t\u00eb shk\u00ebmbimeve t\u00eb mesazheve, nuk ka m\u00ebnyr\u00eb p\u00ebr t\u00eb njoftuar garantuar t\u00eb dy gjeneral\u00ebt se mesazhet e tyre jan\u00eb pranuar (n\u00ebn kushtin q\u00eb ndonj\u00ebra prej lajm\u00ebtar\u00ebve mund t\u00eb kapet).<\/p>\n

Detyra e dy gjeneral\u00ebve \u00ebsht\u00eb nj\u00eb ilustrazion i shk\u00eblqyer i nj\u00eb sistemi t\u00eb thjesht\u00eb t\u00eb shp\u00ebrndar\u00eb, ku ka dy nyje me komunikim t\u00eb pasigurt. Kjo do t\u00eb thot\u00eb se nuk kemi nj\u00eb garanci 100% q\u00eb ata do t\u00eb sinkronizohen. P\u00ebr probleme t\u00eb ngjashme n\u00eb nj\u00eb shkall\u00eb m\u00eb t\u00eb madhe p\u00ebr m\u00eb shum\u00eb n\u00eb artikull.<\/p>\n

Po prezantojm\u00eb konceptin e sistemeve t\u00eb shp\u00ebrndara<\/h2>\n

\nNj\u00eb sistem i shp\u00ebrndar\u00eb \u00ebsht\u00eb nj\u00eb grup kompjuterash (q\u00eb do t'i quajm\u00eb nyje), t\u00eb cilat mund t\u00eb shk\u00ebmbejn\u00eb mesazhe. \u00c7do nyj\u00eb e ve\u00e7ant\u00eb \u00ebsht\u00eb nj\u00eb entitet autonom. Nj\u00eb nyj\u00eb mund t\u00eb p\u00ebrpunoj\u00eb detyra n\u00eb m\u00ebnyr\u00eb t\u00eb pavarur, por p\u00ebr t'u nd\u00ebrvepruar me nyje t\u00eb tjera, ajo duhet t\u00eb d\u00ebrgoj\u00eb dhe pranoj\u00eb mesazhe. <\/p>\n

Si konkretisht jan\u00eb realizuar mesazhet, cilat protokolle p\u00ebrdoren \u2013 kjo nuk na intereson n\u00eb k\u00ebt\u00eb kontekst. E r\u00ebnd\u00ebsishme \u00ebsht\u00eb q\u00eb nyjet e sistemit t\u00eb shp\u00ebrndar\u00eb mund t\u00eb shk\u00ebmbejn\u00eb t\u00eb dh\u00ebna me nj\u00ebra-tjetr\u00ebn p\u00ebrmes d\u00ebrgimit t\u00eb mesazheve.<\/p>\n

P\u00ebrkufizimi vet\u00eb duket se nuk \u00ebsht\u00eb shum\u00eb i komplikuar, por duhet t\u00eb merret parasysh se sistemi i shp\u00ebrndar\u00eb ka nj\u00eb s\u00ebr\u00eb atributesh, t\u00eb cilat do t\u00eb jen\u00eb t\u00eb r\u00ebnd\u00ebsishme p\u00ebr ne.<\/p>\n

Atributet e sistemeve t\u00eb shp\u00ebrndara<\/h4>\n

<\/p>\n

    \n
  1. Paralelizmi<\/b> \u2013 mund\u00ebsia e ndodhis\u00eb s\u00eb ngjarjeve t\u00eb nj\u00ebkohshme ose konkurruese n\u00eb sistem. P\u00ebr m\u00eb tep\u00ebr, do t\u00eb marrim n\u00eb konsiderat\u00eb se ngjarjet q\u00eb ndodhin n\u00eb dy nyje t\u00eb ndryshme jan\u00eb potencialisht konkurruese deri sa nuk kemi nj\u00eb rend t\u00eb qart\u00eb t\u00eb ndodhjeve t\u00eb k\u00ebtyre ngjarjeve. Dhe, zakonisht, ne nuk e kemi at\u00eb.<\/li>\n
  2. Mungesa e or\u00ebve globale<\/b>. Ne nuk kemi nj\u00eb rend t\u00eb qart\u00eb t\u00eb ngjarjeve p\u00ebr shkak t\u00eb munges\u00ebs s\u00eb or\u00ebve globale. N\u00eb bot\u00ebn e zakonshme t\u00eb njer\u00ebzve, ne jemi m\u00ebsuar q\u00eb t\u00eb kemi or\u00eb dhe koh\u00eb absolute. Gj\u00ebrat ndryshojn\u00eb kur flasim p\u00ebr sistemet e shp\u00ebrndara. Edhe or\u00ebt atomike m\u00eb t\u00eb sakta kan\u00eb dridhje, dhe jan\u00eb situata kur ne nuk mund t\u00eb themi se cila nga dy ngjarjet ka ndodhur e para. P\u00ebr m\u00eb tep\u00ebr, ne nuk mund t\u00eb mb\u00ebshtetemi n\u00eb koh\u00eb.<\/li>\n
  3. D\u00ebshtimi i pavarur i nyjeve t\u00eb sistemit<\/b>. Ka edhe nj\u00eb problem tjet\u00ebr: di\u00e7ka mund t\u00eb shkoj\u00eb keq thjesht sepse nyjet tona nuk jan\u00eb t\u00eb p\u00ebrjetshme. Nj\u00eb hard disk mund t\u00eb d\u00ebshtoj\u00eb, nj\u00eb makin\u00eb virtuale n\u00eb re mund t\u00eb ri\u00e7aktivizohet, mund t\u00eb ket\u00eb nj\u00eb ndales\u00eb n\u00eb rrjet dhe mesazhet humbasin. P\u00ebr m\u00eb tep\u00ebr, jan\u00eb situata kur nyjet funksionojn\u00eb, por n\u00eb t\u00eb nj\u00ebjt\u00ebn koh\u00eb funksionojn\u00eb kund\u00ebr sistemit. Klasi i fundit i problemeve mori nj\u00eb em\u00ebr t\u00eb ve\u00e7ant\u00eb: problemi i gjeneral\u00ebve bizantin\u00eb<\/a><\/noindex>. Shembulli m\u00eb i njohur i nj\u00eb sistemi t\u00eb shp\u00ebrndar\u00eb me nj\u00eb problem t\u00eb till\u00eb \u00ebsht\u00eb Blockchain. Por sot ne nuk do t\u00eb shqyrtojm\u00eb k\u00ebt\u00eb klas\u00eb t\u00eb ve\u00e7ant\u00eb problemeve. Ne do t\u00eb interesoheshim p\u00ebr situatat ku thjesht nj\u00eb ose disa nyje mund t\u00eb d\u00ebshtojn\u00eb.<\/li>\n
  4. Modelet e komunikimit (modelet e shk\u00ebmbimit t\u00eb mesazheve) midis nyjeve<\/b>. Ne kemi zbuluar tashm\u00eb se nyjet komunikojn\u00eb p\u00ebrmes shk\u00ebmbimit t\u00eb mesazheve. Ka dy modele t\u00eb njohura t\u00eb shk\u00ebmbimit t\u00eb mesazheve: t\u00eb sinkronizuara dhe asinkronizuara.<\/li>\n<\/ol>\n

    <\/p>\n

    Modelet e komunikimit mes nyjeve n\u00eb sistemet e shp\u00ebrndara<\/h4>\n

    \nModeli i sinkronizuar<\/b> \u2013 ne dim\u00eb sakt\u00ebsisht se ekziston nj\u00eb diferenc\u00eb e njohur kohore p\u00ebr t\u00eb cil\u00ebn mesazhi garanton q\u00eb arrin nga nj\u00eb nyje n\u00eb tjetr\u00ebn. N\u00ebse kjo koh\u00eb kalon dhe mesazhi nuk ka arritur, mund t\u00eb themi me siguri se nyja \u00ebsht\u00eb e prishur. N\u00eb k\u00ebt\u00eb model kemi nj\u00eb koh\u00eb pritur t\u00eb parashikueshme. <\/p>\n

    Modeli asinkron<\/b> \u2013 n\u00eb modelet asinkron ne e konsiderojm\u00eb se koha e pritjes \u00ebsht\u00eb e fundme, por nuk ekziston ndonj\u00eb diferenc\u00eb kohore pas s\u00eb cil\u00ebs mund t\u00eb garantojm\u00eb se nyja \u00ebsht\u00eb e prishur. Kjo do t\u00eb thot\u00eb se koha e pritjes p\u00ebr nj\u00eb mesazh nga nyja mund t\u00eb jet\u00eb \u00e7far\u00ebdo, pa kufizim. Kjo \u00ebsht\u00eb nj\u00eb p\u00ebrkufizim i r\u00ebnd\u00ebsish\u00ebm dhe do t\u00eb flasim mbi t\u00eb m\u00eb von\u00eb. <\/p>\n

    Koncepti i konsensusit n\u00eb sistemet e shp\u00ebrndara<\/h2>\n

    \nPara se t\u00eb p\u00ebrcaktojm\u00eb formalisht konceptin e konsensusit, le t\u00eb shqyrtojm\u00eb nj\u00eb shembull situate kur na nevojitet ai, dmth \u2013 Replikimi i Makinerive Shtet\u00ebrore<\/b>. <\/p>\n

    Ne kemi nj\u00eb disa regjistrime t\u00eb shp\u00ebrndara. Do t\u00eb donim q\u00eb ato t\u00eb ishin konsistente dhe t\u00eb p\u00ebrmbanin t\u00eb dh\u00ebna identike n\u00eb t\u00eb gjitha nyjet e sistemit t\u00eb shp\u00ebrndar\u00eb. Kur ndonj\u00eb nga nyjet merr nj\u00eb vler\u00eb t\u00eb re, e cila do t\u00eb regjistrohet n\u00eb regjistrim, detyra e tij b\u00ebhet t\u00eb propozoj\u00eb k\u00ebt\u00eb vler\u00eb p\u00ebr t\u00eb gjitha nyjet e tjera, n\u00eb m\u00ebnyr\u00eb q\u00eb regjistrimi t\u00eb p\u00ebrmir\u00ebsohet n\u00eb t\u00eb gjitha nyjet, dhe sistemi t\u00eb kaloj\u00eb n\u00eb nj\u00eb gjendje t\u00eb re konsistente. N\u00eb k\u00ebt\u00eb rast, \u00ebsht\u00eb e r\u00ebnd\u00ebsishme q\u00eb nyjet t\u00eb bien dakord me nj\u00ebri-tjetrin: t\u00eb gjitha nyjet t\u00eb bien dakord se vlera e re e propozuar \u00ebsht\u00eb e sakt\u00eb, t\u00eb gjitha nyjet e pranojn\u00eb k\u00ebt\u00eb vler\u00eb dhe vet\u00ebm n\u00eb k\u00ebt\u00eb rast t\u00eb gjith\u00eb mund t\u00eb regjistrojn\u00eb vler\u00ebn e re n\u00eb regjistrim. <\/p>\n

    Me fjal\u00eb t\u00eb tjera: askush nga nyjet nuk kund\u00ebrshtoi se kishte informacion m\u00eb t\u00eb ri, dhe vlera e propozuar ishte e gabuar. Marr\u00ebveshja nd\u00ebrmjet nyjeve dhe pajtimi p\u00ebr nj\u00eb vler\u00eb t\u00eb sakt\u00eb t\u00eb pranuar \u00ebsht\u00eb konsensusi n\u00eb sistemin e shp\u00ebrndar\u00eb. M\u00eb tej do t\u00eb flasim p\u00ebr algoritmet q\u00eb lejojn\u00eb sistemin e shp\u00ebrndar\u00eb t\u00eb arrij\u00eb garantuar konsensus.
    \n\"Miu
    \nM\u00eb formalisht, ne mund t\u00eb p\u00ebrcaktojm\u00eb algoritmin e arritjes s\u00eb konsensusit (ose thjesht algoritmin e konsensusit) si nj\u00eb funksion q\u00eb e \u00e7on nj\u00eb sistem t\u00eb shp\u00ebrndar\u00eb nga gjendja A n\u00eb gjendjen B. N\u00eb ve\u00e7anti, kjo gjendje pranohet nga t\u00eb gjitha nyjt\u00eb dhe t\u00eb gjitha nyjt\u00eb mund ta konfirmojn\u00eb at\u00eb. Si\u00e7 del, ky detyr\u00eb nuk \u00ebsht\u00eb aq triviale sa duket n\u00eb pamje t\u00eb par\u00eb.<\/p>\n

    Atributet e algoritmit t\u00eb konsensusit<\/h4>\n

    \nAlgoritmi i konsensusit duhet t\u00eb ket\u00eb tre ve\u00e7ori q\u00eb sistemi t\u00eb vazhdoj\u00eb t\u00eb ekzistoj\u00eb dhe t\u00eb ket\u00eb ndonj\u00eb p\u00ebrparim n\u00eb kalimin nga nj\u00eb gjendje n\u00eb tjetr\u00ebn:<\/p>\n

      \n
    1. Marr\u00ebveshje <\/b> \u2013 t\u00eb gjitha nyjt\u00eb q\u00eb punojn\u00eb si\u00e7 duhet duhet t\u00eb pranojn\u00eb t\u00eb nj\u00ebjt\u00ebn vler\u00eb (n\u00eb artikuj ky atribut njihet gjithashtu si pron\u00eb e siguris\u00eb). T\u00eb gjitha nyjt\u00eb q\u00eb tani funksionojn\u00eb (nuk jan\u00eb d\u00ebshtuar dhe nuk kan\u00eb humbur lidhjen me t\u00eb tjer\u00ebt) duhet t\u00eb arrijn\u00eb nj\u00eb marr\u00ebveshje dhe t\u00eb pranojn\u00eb nj\u00eb vler\u00eb p\u00ebrfundimtare t\u00eb p\u00ebrbashk\u00ebt.\n

      K\u00ebtu \u00ebsht\u00eb e r\u00ebnd\u00ebsishme t\u00eb kuptohet se nyjt\u00eb n\u00eb sistemin e shp\u00ebrndar\u00eb q\u00eb po shqyrtojm\u00eb duan t\u00eb bien dakord. Pra, tani po flasim p\u00ebr sisteme ku di\u00e7ka mund t\u00eb d\u00ebshtoj\u00eb (p\u00ebr shembull, ndonj\u00eb nyje mund t\u00eb d\u00ebshtoj\u00eb), por n\u00eb k\u00ebt\u00eb sistem nuk ka nyjt\u00eb q\u00eb punojn\u00eb me synim kund\u00ebr t\u00eb tjer\u00ebve (detyra e gjeneral\u00ebve bizantin\u00eb). Fal\u00eb k\u00ebsaj ve\u00e7orie, sistemi mbetet i q\u00ebndruesh\u00ebm.<\/li>\n

    2. Integriteti <\/b> \u2013 n\u00ebse t\u00eb gjitha nyjt\u00eb q\u00eb punojn\u00eb si\u00e7 duhet ofrojn\u00eb t\u00eb nj\u00ebjt\u00ebn vler\u00eb v<\/b>, at\u00ebher\u00eb \u00e7do nyj\u00eb q\u00eb punon si\u00e7 duhet duhet ta pranoj\u00eb k\u00ebt\u00eb vler\u00eb v<\/b>. <\/li>\n
    3. P\u00ebrfundimi <\/b>\u2013 t\u00eb gjitha nyjt\u00eb q\u00eb punojn\u00eb si\u00e7 duhet, n\u00eb fund t\u00eb fundit do t\u00eb pranojn\u00eb nj\u00eb vler\u00eb t\u00eb caktuar (prona e gjall\u00ebris\u00eb), e cila lejon algoritmin t\u00eb ket\u00eb p\u00ebrparim n\u00eb sistem. \u00c7do nyj\u00eb e ve\u00e7ant\u00eb q\u00eb punon si\u00e7 duhet, duhet her\u00ebt a von\u00eb t\u00eb pranoj\u00eb vler\u00ebn p\u00ebrfundimtare dhe ta konfirmoj\u00eb k\u00ebt\u00eb: \"P\u00ebr mua \u2013 kjo vler\u00eb \u00ebsht\u00eb e v\u00ebrtet\u00eb, un\u00eb bie dakord me t\u00eb gjith\u00eb sistemin\".<\/li>\n<\/ol>\n

      <\/p>\n

      Shembulli i funksionimit t\u00eb algoritmit t\u00eb konsensusit<\/h4>\n

      \nNd\u00ebrsa ve\u00e7orit\u00eb e algoritmit mund t\u00eb mos jen\u00eb t\u00eb qarta tani, ne do ta ilustrojm\u00eb me nj\u00eb shembull se \u00e7far\u00eb fazash kalon nj\u00eb algoritmi i thjesht\u00eb i konsensusit n\u00eb nj\u00eb sistem me nj\u00eb model t\u00eb sinkronizuar t\u00eb shk\u00ebmbimit t\u00eb mesazheve, ku t\u00eb gjitha nyjt\u00eb funksionojn\u00eb si\u00e7 duhet, mesazhet nuk humbasin dhe asgj\u00eb nuk d\u00ebshtoi (a ndodh v\u00ebrtet nj\u00eb gj\u00eb e till\u00eb?).<\/p>\n

        \n
      1. \u00c7do gj\u00eb fillon me propozimin e dor\u00ebs dhe zemr\u00ebs (Propose). Le t\u00eb supozojm\u00eb se nj\u00eb klient u lidh me nyj\u00ebn e quajtur \u201cNyja 1\u201d dhe filloi transaksionin duke kaluar nj\u00eb vler\u00eb t\u00eb re - O. Q\u00eb nga ky moment, ne do ta quajm\u00eb \u201cNyja 1\u201d proposer<\/b>. Si proposer, \u201cNyja 1\u201d tani duhet t\u00eb njoftoj\u00eb gjith\u00eb sistemin se ka t\u00eb dh\u00ebna t\u00eb reja dhe d\u00ebrgon mesazhe t\u00eb gjith\u00eb nyjave t\u00eb tjera: \u201cShikoni! M\u00eb erdhi vlera \u201cO\u201d dhe dua ta regjistroj! Ju lutem, konfirmoni q\u00eb do ta regjistroni edhe ju \u201cO\u201d n\u00eb logun tuaj.\u201d\n

        \"Miu<\/li>\n

      2. Faza tjet\u00ebr \u00ebsht\u00eb votimi p\u00ebr vler\u00ebn e propozuar (Voting). P\u00ebr \u00e7far\u00eb \u00ebsht\u00eb kjo? Mund t\u00eb ndodh\u00eb q\u00eb nyjat e tjera t\u00eb ken\u00eb marr\u00eb informacione m\u00eb t\u00eb reja dhe ata kan\u00eb t\u00eb dh\u00ebna p\u00ebr k\u00ebt\u00eb transaksion t\u00eb nj\u00ebjt\u00eb.\n

        \"Miu
        \n
        \nKur nyja \u201cNyja 1\u201d d\u00ebrgon propozimin e saj, nyjat e tjera kontrollojn\u00eb n\u00eb logjet e tyre t\u00eb dh\u00ebnat p\u00ebr k\u00ebt\u00eb ngjarje. N\u00ebse nuk ka asnj\u00eb konflikt, nyjat shpallin: \u201cPo, nuk kam t\u00eb dh\u00ebna t\u00eb tjera p\u00ebr k\u00ebt\u00eb ngjarje. Vlera \u201cO\u201d \u00ebsht\u00eb informacioni m\u00eb i ri q\u00eb kemi arritur.\u201d <\/p>\n

        N\u00eb \u00e7do rast tjet\u00ebr, nyjat mund t\u00eb p\u00ebrgjigjen \u201cNyjes 1\u201d: \u201cListen! Kam t\u00eb dh\u00ebna m\u00eb t\u00eb reja p\u00ebr k\u00ebt\u00eb transaksion. Jo \u201cO\u201d, por di\u00e7ka m\u00eb t\u00eb mir\u00eb.\u201d<\/p>\n

        N\u00eb faz\u00ebn e votimit, nyjat arrijn\u00eb nj\u00eb vendim: ose t\u00eb gjith\u00eb pranojn\u00eb nj\u00eb vler\u00eb, ose ndonj\u00ebra prej tyre voton kund\u00ebr, duke treguar se ka t\u00eb dh\u00ebna m\u00eb t\u00eb reja. <\/li>\n

      3. N\u00ebse rundi i votimit kalon me sukses, dhe t\u00eb gjith\u00eb ishin \u201cpro\u201d, sistemi kalon n\u00eb nj\u00eb faz\u00eb t\u00eb re - pranimin e vler\u00ebs (Accept). \u201cNyja 1\u201d mbledh t\u00eb gjitha p\u00ebrgjigjet nga nyjat e tjera dhe raporton: \u201cT\u00eb gjith\u00eb ran\u00eb dakord me vler\u00ebn \u201cO\u201d! Tani e shpall zyrtarisht se \u201cO\u201d \u00ebsht\u00eb vlera jon\u00eb e re, e vetme p\u00ebr t\u00eb gjith\u00eb! Regjistroheni n\u00eb librin tuaj, mos e harroni. Regjistrojeni n\u00eb logun tuaj!\u201d\n

        \"Miu<\/li>\n

      4. Nyjat e tjera d\u00ebrgojn\u00eb konfirmimin (Accepted) q\u00eb ata e regjistruan vler\u00ebn \u201cO\u201d, nuk ka ardhur asgj\u00eb e re gjat\u00eb k\u00ebsaj kohe (nj\u00eb lloj komit dypal\u00ebsh). Pas k\u00ebtij ngjarjeje t\u00eb r\u00ebnd\u00ebsishme, ne mendojm\u00eb se transaksioni i shp\u00ebrndar\u00eb \u00ebsht\u00eb realizuar.
        \n \"Miu <\/li>\n<\/ol>\n

        \nPra, algoritmi i konsensusit n\u00eb rastin e thjesht\u00eb p\u00ebrb\u00ebhet nga kat\u00ebr hapa: propose, votimi (voting), pranim (accept), konfirmimi i pranimet (accepted).<\/p>\n

        N\u00ebse n\u00eb ndonj\u00eb hap ne nuk arrijm\u00eb t\u00eb b\u00ebjm\u00eb nj\u00eb marr\u00ebveshje, algoritmi nis nga e para, duke marr\u00eb parasysh informacionin q\u00eb do t\u00eb ofrojn\u00eb nyjat q\u00eb refuzuan t\u00eb konfirmojn\u00eb vler\u00ebn e propozuar.<\/p>\n

        Algoritmi i konsensusit n\u00eb nj\u00eb sistem asinkron<\/h2>\n

        \nPara k\u00ebsaj gjith\u00e7ka ishte e qet\u00eb, pasi po flisnim p\u00ebr nj\u00eb model sinkron t\u00eb shk\u00ebmbimit t\u00eb mesazheve. Por ne e dim\u00eb se n\u00eb bot\u00ebn moderne jemi m\u00ebsuar t\u00eb veprojm\u00eb n\u00eb m\u00ebnyr\u00eb asinkrone. Si funksionon nj\u00eb algorit\u00ebm i ngjash\u00ebm n\u00eb nj\u00eb sistem me nj\u00eb model asinkron t\u00eb shk\u00ebmbimit t\u00eb mesazheve, ku besojm\u00eb se koha e pritjes p\u00ebr nj\u00eb p\u00ebrgjigje nga nj\u00eb nod mund t\u00eb jet\u00eb sa t\u00eb doj\u00eb e gjat\u00eb (kurse, dalja e nj\u00eb nodi nga sistemi mund t\u00eb merret gjithashtu si nj\u00eb shembull, kur nj\u00eb nod mund t\u00eb p\u00ebrgjigjet sa t\u00eb doj\u00eb e gjat\u00eb). <\/p>\n

        Tani, kur e dim\u00eb si n\u00eb parim funksionon algoritmi i konsensusit, pyetje p\u00ebr ata lexues kureshtar q\u00eb arrit\u00ebn n\u00eb k\u00ebt\u00eb pik\u00eb: sa nod\u00eb n\u00eb nj\u00eb sistem me N nod\u00eb me model asinkron t\u00eb mesazheve mund t\u00eb dalin nga sistemi, p\u00ebr t\u00eb arritur ende konsensus?<\/p><\/blockquote>\n

        \nP\u00ebrgjigja e sakt\u00eb dhe arsyetimi jan\u00eb pas spoilerit.<\/b>P\u00ebrgjigja e sakt\u00eb: 0<\/b>. N\u00ebse t\u00eb pakt\u00ebn nj\u00eb nod n\u00eb nj\u00eb sistem asinkron del nga sistemi, sistemi nuk do t\u00eb jet\u00eb n\u00eb gjendje t\u00eb arrij\u00eb konsensus. Ky konstatim \u00ebsht\u00eb provuar n\u00eb teorem\u00ebn e njohur n\u00eb disa qarqe FLP (1985, Fischer, Lynch, Paterson, referenca n\u00eb origjinal n\u00eb fund t\u00eb artikullit): \"Pamund\u00ebsia p\u00ebr t\u00eb arritur konsensus t\u00eb shp\u00ebrndar\u00eb kur del jasht\u00eb nj\u00eb nod\".
        \n\"Miu
        \nDjem, at\u00ebher\u00eb kemi nj\u00eb problem, jemi m\u00ebsuar q\u00eb gjith\u00e7ka \u00ebsht\u00eb asinkrone. Dhe tani ky problem. Si mund t\u00eb vazhdojm\u00eb? <\/p>\n

        Ne tani fol\u00ebm p\u00ebr teorin\u00eb, p\u00ebr matematiken. \u00c7far\u00eb do t\u00eb thot\u00eb \"konsensusi nuk mund t\u00eb arrihet\", duke e p\u00ebrkthyer nga gjuha matematike n\u00eb gjuh\u00ebn ton\u00eb \u2013 inxhinierike? Do t\u00eb thot\u00eb se \"nuk mund t\u00eb arrihet gjithmon\u00eb\", pra ekziston nj\u00eb rast, ku konsensusi nuk \u00ebsht\u00eb i arritsh\u00ebm. Po, \u00e7far\u00eb \u00ebsht\u00eb ky rast? <\/p>\n

        Kjo \u00ebsht\u00eb pik\u00ebrisht shkelja e pron\u00ebsis\u00eb s\u00eb liveness, e p\u00ebrmendur m\u00eb sip\u00ebr. Ne nuk kemi nj\u00eb pajtim t\u00eb p\u00ebrbashk\u00ebt, dhe sistemi nuk mund t\u00eb ket\u00eb p\u00ebrparim (nuk mund t\u00eb p\u00ebrfundoj\u00eb brenda nj\u00eb kohe t\u00eb kufizuar) n\u00eb rastin kur nuk kemi p\u00ebrgjigje nga t\u00eb gjith\u00eb nodet. Sepse n\u00eb nj\u00eb sistem asinkron nuk kemi nj\u00eb koh\u00eb p\u00ebrgjigjeje t\u00eb parashikueshme dhe nuk e dim\u00eb n\u00ebse nj\u00eb nod ka dal\u00eb jasht\u00eb apo thjesht po p\u00ebrgjigjet ngadal\u00eb.<\/p>\n

        Por n\u00eb praktik\u00eb mund t\u00eb gjejm\u00eb nj\u00eb zgjidhje. Le t\u00eb themi se algoritmi yn\u00eb mund t\u00eb funksionoj\u00eb gjat\u00eb n\u00eb rastet e d\u00ebshtimeve (potencialisht mund t\u00eb funksionoj\u00eb pafund\u00ebsisht). Por n\u00eb shumic\u00ebn e situatave, kur shumica e nodve funksionojn\u00eb si duhet, do t\u00eb kemi p\u00ebrparim n\u00eb sistem. <\/p>\n

        N\u00eb praktik\u00eb, ne kemi t\u00eb b\u00ebjm\u00eb me modele komunikimi pjes\u00ebrisht asinhron. Pjes\u00ebrisht asinhron kuptohet si dhe: n\u00eb p\u00ebrgjith\u00ebsi kemi nj\u00eb model asinhron, por formalisht introduktohet nj\u00eb koncept \"koha globale e stabilizimit\" e nj\u00eb momenti t\u00eb caktuar. <\/p>\n

        Ky moment kohe mund t\u00eb mos ndodh\u00eb p\u00ebr nj\u00eb periudh\u00eb t\u00eb pakufizuar, por nj\u00ebher\u00eb duhet t\u00eb ndodh\u00eb. Do t\u00eb bjer\u00eb nj\u00eb alarm virtual dhe nga ai moment mund t\u00eb parashikojm\u00eb dyt\u00ebn e koh\u00ebs p\u00ebr t\u00eb cil\u00ebn mesazhet do t\u00eb arrijn\u00eb. Nga ky moment, sistemi kalon nga asinhron n\u00eb sinkron. N\u00eb praktik\u00eb, ne kemi t\u00eb b\u00ebjm\u00eb me k\u00ebto sisteme. <\/p>\n

        Algoritmi Paxos zgjidh problemet e konsensusit<\/h2>\n

        \nPaxos <\/a><\/noindex> \u00ebsht\u00eb nj\u00eb familje algoritmesh q\u00eb zgjidh problemin e konsensusit p\u00ebr sistemet gjysm\u00eb sinjifikante, me kushtin q\u00eb disa nod t\u00eb mund t\u00eb d\u00ebshtojn\u00eb. Autori i Paxos \u00ebsht\u00eb Leslie Lamport<\/a><\/noindex>. Ai propozoi nj\u00eb prov\u00eb formale t\u00eb ekzistenc\u00ebs dhe korrekt\u00ebsis\u00eb s\u00eb algoritmit n\u00eb vitin 1989. <\/p>\n

        Por provimi doli t\u00eb jet\u00eb aspak trivial. Publikimi i par\u00eb u l\u00ebshua vet\u00ebm n\u00eb vitin 1998 (33 faqe) me p\u00ebrshkrimin e algoritmit. Si\u00e7 duket, ajo ishte jasht\u00ebzakonisht e v\u00ebshtir\u00eb p\u00ebr t'u kuptuar, dhe n\u00eb vitin 2001 u publikua nj\u00eb sqarim i artikullit, i cili zuri 14 faqe. V\u00ebllimet e publikimeve jan\u00eb dh\u00ebn\u00eb p\u00ebr t\u00eb treguar se n\u00eb t\u00eb v\u00ebrtet\u00eb problemi i konsensusit nuk \u00ebsht\u00eb aspak i thjesht\u00eb dhe pas k\u00ebtyre algoritmeve q\u00ebndron nj\u00eb pun\u00eb e madhe e njer\u00ebzve m\u00eb t\u00eb men\u00e7ur.<\/p>\n

        \u00cbsht\u00eb interesante se vet\u00eb Leslie Lamport n\u00eb leksionin e tij vuri n\u00eb dukje se n\u00eb artikullin e dyt\u00eb-sqarim ka nj\u00eb pohim, nj\u00eb rresht (nuk specifikoi cili), i cili mund t\u00eb interpretohet n\u00eb m\u00ebnyra t\u00eb ndryshme. Dhe p\u00ebr k\u00ebt\u00eb arsye, nj\u00eb num\u00ebr i madh i implementimeve moderne t\u00eb Paxos punojn\u00eb jo krejt\u00ebsisht si\u00e7 duhet. <\/p><\/blockquote>\n

        \nNj\u00eb analiz\u00eb e detajuar e funksionimit t\u00eb Paxos do t\u00eb k\u00ebrkonte m\u00eb shum\u00eb se nj\u00eb artikull, prandaj do t\u00eb p\u00ebrpiqem ta transmetoj n\u00eb m\u00ebnyr\u00eb shum\u00eb t\u00eb shkurt\u00ebr iden\u00eb kryesore t\u00eb algoritmit. N\u00eb lidhjet n\u00eb fund t\u00eb artikullit tim do t\u00eb gjeni materiale p\u00ebr nj\u00eb thellim m\u00eb t\u00eb madh n\u00eb k\u00ebt\u00eb tem\u00eb.<\/p>\n

        Rolat n\u00eb Paxos<\/h4>\n

        \nN\u00eb algoritmin Paxos ka nj\u00eb koncept rolesh. Le t\u00eb shqyrtojm\u00eb tre t\u00eb par\u00ebt (ka modifikime me role shtes\u00eb):<\/p>\n

          \n
        1. Proposers (terminet lider\u00eb ose koordinues mund t\u00eb p\u00ebrdoren gjithashtu)<\/b>K\u00ebta jan\u00eb djem q\u00eb m\u00ebsojn\u00eb p\u00ebr nj\u00eb dometh\u00ebnie t\u00eb re nga p\u00ebrdoruesi dhe marrin rolin e liderit. Detyra e tyre \u00ebsht\u00eb t\u00eb nisin nj\u00eb raund propozimi t\u00eb dometh\u00ebnies s\u00eb re dhe t\u00eb koordinojn\u00eb veprimet e m\u00ebtejshme t\u00eb nyjave. Ve\u00e7 k\u00ebsaj, Paxos lejon pranin\u00eb e disa lider\u00ebve n\u00eb situata t\u00eb caktuara.<\/li>\n
        2. Pranuesit (Voter\u00ebt)<\/b>K\u00ebta jan\u00eb nyjat q\u00eb votojn\u00eb p\u00ebr miratimin ose refuzimin e nj\u00eb dometh\u00ebnieje t\u00eb caktuar. Roli i tyre \u00ebsht\u00eb shum\u00eb i r\u00ebnd\u00ebsish\u00ebm, sepse pik\u00ebrisht nga ata varen vendimet: n\u00eb cilin gjendje do t\u00eb kaloj\u00eb (apo jo) sistemi pas nj\u00eb faze t\u00eb caktuar t\u00eb algoritmit t\u00eb konsensusit.<\/li>\n
        3. M\u00ebsuesit<\/b>K\u00ebto jan\u00eb nyja q\u00eb thjesht pranojn\u00eb dhe regjistrojn\u00eb dometh\u00ebnien e pranuar t\u00eb re, kur gjendja e sistemit ka ndryshuar. Ata nuk marrin vendime, thjesht marrin t\u00eb dh\u00ebna dhe mund t'i dor\u00ebzojn\u00eb ato p\u00ebrdoruesit p\u00ebrfundimtar. <\/li>\n<\/ol>\n

          \nNj\u00eb nyje mund t\u00eb kombinoj\u00eb disa role n\u00eb situata t\u00eb ndryshme. <\/p>\n

          Koncepci i kuorumit<\/h4>\n

          \nNe supozojm\u00eb se kemi nj\u00eb sistem me N<\/b> nyje. Dhe nga k\u00ebto, maksimumi F<\/b> nyje mund t\u00eb d\u00ebshtojn\u00eb. N\u00ebse F nyje d\u00ebshtojn\u00eb, at\u00ebher\u00eb n\u00eb klasterin ton\u00eb duhet t\u00eb kemi, si\u00e7 \u00ebsht\u00eb minimale 2F + 1<\/b> nodet acceptor. <\/p>\n

          Kjo \u00ebsht\u00eb e nevojshme p\u00ebr t\u00eb siguruar q\u00eb ne gjithmon\u00eb, edhe n\u00eb situat\u00ebn m\u00eb t\u00eb keqe, \"t\u00eb mir\u00ebt\", nyjat q\u00eb funksionojn\u00eb si\u00e7 duhet, t\u00eb ken\u00eb shumic\u00ebn. Pra, kjo do t\u00eb thot\u00eb F + 1<\/b> \"t\u00eb mir\u00ebve\" nyje q\u00eb e pranojn\u00eb, dhe vlera p\u00ebrfundimtare do t\u00eb miratohet. N\u00eb t\u00eb kund\u00ebrt, mund t\u00eb ndodh\u00eb q\u00eb kemi grupe lokale t\u00eb ndryshme q\u00eb miratojn\u00eb vlera t\u00eb ndryshme dhe nuk arrijn\u00eb t\u00eb bien dakord mes tyre. Prandaj na nevojitet nj\u00eb shumic\u00eb absolute p\u00ebr t\u00eb fituar n\u00eb votim.<\/p>\n

          Ideja e p\u00ebrgjithshme e funksionimit t\u00eb algoritmit t\u00eb konsensusit Paxos<\/h4>\n

          \nAlgoritmi Paxos supozon dy faza t\u00eb m\u00ebdha, t\u00eb cilat nga ana e tyre ndahen n\u00eb dy hapa \u00e7do nj\u00ebra:<\/p>\n

            \n
          1. Faza 1a: P\u00ebrgatitja<\/b>. N\u00eb faz\u00ebn e p\u00ebrgatitjes, lideri (proposer) i njofton t\u00eb gjitha nyjet: \"Ne fillojm\u00eb nj\u00eb faz\u00eb t\u00eb re votimi. Kemi nj\u00eb raund t\u00eb ri. Numri i k\u00ebtij raundi \u00ebsht\u00eb n. Tani do t\u00eb fillojm\u00eb t\u00eb votojm\u00eb\". Kryesisht ai njofton fillimin e ciklit t\u00eb ri, por nuk jep nj\u00eb vler\u00eb t\u00eb re. Q\u00ebllimi i k\u00ebsaj faze \u00ebsht\u00eb t\u00eb filloj\u00eb nj\u00eb raund t\u00eb ri dhe t\u00eb njoftoj\u00eb t\u00eb gjith\u00eb p\u00ebr numrin e tij unik. Numri i raundit \u00ebsht\u00eb i r\u00ebnd\u00ebsish\u00ebm, duhet t\u00eb jet\u00eb nj\u00eb vler\u00eb m\u00eb e madhe se t\u00eb gjitha numrat e m\u00ebparsh\u00ebm t\u00eb votimeve nga t\u00eb gjith\u00eb lider\u00ebt e m\u00ebparsh\u00ebm. Pik\u00ebrisht p\u00ebrmes numrit t\u00eb raundit, nyjet e tjera n\u00eb sistem do t\u00eb kuptojn\u00eb se sa t\u00eb fresk\u00ebta jan\u00eb t\u00eb dh\u00ebnat nga lideri. Ndoshta, nyjet e tjera tashm\u00eb kan\u00eb rezultate votimi nga raunde shum\u00eb m\u00eb t\u00eb vonshme dhe thjesht do t'i tregojn\u00eb liderit se ai ka ngecur pas.<\/li>\n
          2. Faza 1b: Premtimi<\/b>. Kur nodet-acceptor kan\u00eb marr\u00eb numrin e nj\u00eb faze t\u00eb re t\u00eb votimit, mund t\u00eb ndodhin dy rezultate: \n