Mar sin, déanaimis a shamhlú. Tá 5 cait faoi ghlas sa seomra, agus chun an t-úinéir a dhúiseacht, ní mór dóibh go léir aontú ar seo eatarthu féin, toisc nach féidir leo an doras a oscailt ach le cúigear acu ag leanúint air. Más cat Schrödinger ceann de na cait, agus nach bhfuil a fhios ag na cait eile faoina chinneadh, éiríonn an cheist: “Conas is féidir leo é a dhéanamh?”
San Airteagal seo, inseoidh mé duit i dtéarmaí simplí faoin gcomhpháirt theoiriciúil de shaol na gcóras dáilte agus na prionsabail a bhaineann lena n-oibriú. Déanfaidh mé scrúdú dromchla freisin ar an bpríomhsmaoineamh atá mar bhunús ag Paxos.
Nuair a úsáideann forbróirí bonneagair scamall, bunachair shonraí éagsúla, agus a oibríonn i gcnuasaigh de líon mór nóid, tá siad muiníneach go mbeidh na sonraí iomlán, slán, agus ar fáil i gcónaí. Ach cá bhfuil na ráthaíochtaí?
Go bunúsach, is ráthaíochtaí soláthraithe iad na ráthaíochtaí atá againn. Déantar cur síos orthu sa doiciméadú mar seo a leanas: “Tá an tseirbhís seo iontaofa go leor, tá CLS tugtha aici, ná bíodh imní ort, oibreoidh gach rud go dáileadh mar a bheifeá ag súil leis.”
Is gnách linn a chreidiúint sa chuid is fearr, mar gheall ar dheimhnigh guys cliste ó chuideachtaí móra dúinn go mbeidh gach rud go breá. Ní chuirimid an cheist: cén fáth, i ndáiríre, is féidir é seo a oibriú ar chor ar bith? An bhfuil aon údar foirmiúil le feidhmiú ceart na gcóras sin?
Chuaigh mé go dtí le déanaí agus bhí an-spreagadh ag an ábhar seo. Bhí léachtaí ar scoil níos cosúla le ranganna calcalais ná le rud éigin a bhain le córais ríomhaireachta. Ach is é seo go díreach conas a cruthaíodh na halgartaim is tábhachtaí a úsáidimid gach lá, gan fiú a fhios agam é, ag aon am amháin.
Úsáideann formhór na gcóras dáilte nua-aimseartha algartam comhdhearcadh Paxos agus na modhnuithe éagsúla a bhaineann leis. Is é an rud is fuaire ná gur féidir bailíocht agus, i bprionsabal, an fhéidearthacht go bhfuil an algartam seo ann a chruthú go simplí le peann agus páipéar. Go praiticiúil, úsáidtear an algartam i gcórais mhóra a ritheann ar líon mór nóid sna scamaill.
Léiriú éadrom ar a mbeidh á phlé ina dhiaidh sin: tasc beirt GhinearáltaA ligean ar ghlacadh breathnú ar feadh te-suas .
Tá dhá arm againn - dearg agus bán. Tá trúpaí bána lonnaithe sa chathair faoi léigear. Tá trúpaí dearga faoi stiúir ginearálta A1 agus A2 suite ar dhá thaobh na cathrach. Is é tasc na Redheads ionsaí a dhéanamh ar an gcathair bán agus buaigh. Mar sin féin, tá arm gach ginearálta dearg ina n-aonar níos lú ná an arm bán.
Coinníollacha bua do na cinn dearga: caithfidh an dá Ghinearálta ionsaí ag an am céanna chun buntáiste uimhriúil a bheith acu thar na bánna. Chun seo a dhéanamh, ní mór do na ginearálaithe A1 agus A2 teacht ar chomhaontú lena chéile. Má dhéanann gach duine ionsaí ar leithligh, caillfidh na cinn dhearga.
Chun teacht ar chomhaontú, is féidir le ginearál A1 agus A2 teachtairí a sheoladh chuig a chéile trí chríoch na cathrach bán. Féadfaidh an teachtaire ginearál comhghuaillithe a bhaint amach go rathúil nó féadfaidh an namhaid é a idircheapadh. Ceist: an bhfuil a leithéid de sheicheamh cumarsáide ann idir na ginearál rua (an t-ord ina gcuirtear teachtairí ó A1 go A2 agus vice versa ó A2 go A1), ina dtugtar ráthaíocht dóibh aontú ar ionsaí ag uair X. Anseo, Ciallaíonn ráthaíochtaí go mbeidh deimhniú gan athbhrí ag an dá Ghinearál go ndéanfaidh comhghuaillí (ginearál eile) ionsaí cinnte ag an am ceaptha X.
Abair go seolann A1 teachtaire chuig A2 leis an teachtaireacht: “Déanaimis ionsaí inniu ag meán oíche!” Ní féidir le Ginearálta A1 ionsaí gan deimhniú ón nGinearál A2. Má tá an teachtaire ó A1 tagtha, ansin seolann Ginearálta A2 deimhniú leis an teachtaireacht: "Sea, a mharú muid na whites inniu." Ach anois níl a fhios ag Ginearálta A2 an bhfuil a theachtaire tagtha nó nach bhfuil, níl aon ráthaíocht aige an mbeidh an t-ionsaí comhuaineach. Anois tá deimhniú de dhíth ar Ghinearálta A2.
Léiríonn cur síos ar a gcuid cumarsáide an méid seo a leanas a thuilleadh: is cuma cé mhéad timthriallta teachtaireachta atá ann, níl aon bhealach le ráthaíocht a thabhairt go bhfuil fógra tugtha don bheirt ghinearálta go bhfuarthas a dteachtaireachtaí (ag glacadh leis gur féidir ceachtar den dá theachtaire a idircheapadh).
Is léiriú iontach é Fadhb an Dá Ghinearálta ar chóras dáilte an-simplí ina bhfuil dhá nód le cumarsáid neamhiontaofa. Ciallaíonn sé seo nach bhfuil ráthaíocht 100% againn go bhfuil siad sioncronaithe. Ní phléitear fadhbanna cosúla ach ar scála níos mó níos déanaí san alt.
Cuirimid isteach coincheap na gcóras dáilte
Is éard is córas dáilte ann ná grúpa ríomhairí (cuirfimid nóid orthu anseo feasta) ar féidir leo teachtaireachtaí a mhalartú. Is eintiteas uathrialach de chineál éigin é gach nód aonair. Is féidir le nód tascanna a phróiseáil leis féin, ach chun cumarsáid a dhéanamh le nóid eile, ní mór dó teachtaireachtaí a sheoladh agus a fháil.
Conas go díreach a chuirtear teachtaireachtaí i bhfeidhm, cad iad na prótacail a úsáidtear - ní ábhar spéise dúinn é seo sa chomhthéacs seo. Tá sé tábhachtach gur féidir le nóid chórais dáilte sonraí a mhalartú lena chéile trí theachtaireachtaí a sheoladh.
Níl cuma an-chasta ar an sainmhíniú féin, ach ní mór dúinn a chur san áireamh go bhfuil roinnt tréithe ag córas dáilte a bheidh tábhachtach dúinn.
Tréithe na gcóras dáilte
- Trédhearcacht – an fhéidearthacht go dtarlódh teagmhais chomhuaineacha nó chomhthráthacha sa chóras. Ina theannta sin, measfaimid go bhféadfadh imeachtaí a tharlaíonn ar dhá nód éagsúla a bheith comhthráthach chomh fada agus nach bhfuil ord soiléir na n-imeachtaí seo againn. Ach, mar riail, níl sé againn.
- Uimh clog domhanda. Níl ord soiléir imeachtaí againn mar gheall ar an easpa clog domhanda. I ngnáthdhomhan na ndaoine, táimid i dtaithí ar an bhfíric go bhfuil cloig agus am againn go hiomlán. Athraíonn gach rud nuair a thagann sé le córais dáilte. Tá sileadh fiú ag cloig adamhach ultra-bheachta, agus d’fhéadfadh cásanna a bheith ann nach féidir linn a rá cé acu den dá theagmhas a tharla ar dtús. Mar sin, ní féidir linn brath ar am ach an oiread.
- Teip neamhspleách ar nóid an chórais. Tá fadhb eile ann: is féidir go n-imíonn rud éigin mícheart go simplí toisc nach mairfidh ár nóid go deo. D’fhéadfadh go dteipfidh ar an tiomántán crua, féadfaidh an meaisín fíorúil sa scamall atosaigh, féadfaidh an líonra blink agus caillfear teachtaireachtaí. Thairis sin, d'fhéadfadh go mbeadh cásanna ann ina n-oibríonn nóid, ach ag an am céanna ag obair i gcoinne an chórais. Fuair an rang fadhbanna deiridh fiú ainm ar leith: fadhb . Is é an sampla is coitianta de chóras dáilte leis an bhfadhb seo ná Blockchain. Ach inniu ní bhreithnímid an rang speisialta fadhbanna seo. Beidh suim againn i gcásanna ina dteipfeadh ar nód amháin nó níos mó.
- Samhlacha cumarsáide (samhlacha teachtaireachta) idir nóid. Tá sé bunaithe againn cheana féin go ndéanann nóid cumarsáid trí theachtaireachtaí a mhalartú. Tá dhá mhúnla teachtaireachtaí aitheanta: sioncrónach agus asincrónach.
Samhlacha cumarsáide idir nóid i gcórais dáilte
Múnla sioncrónach – tá a fhios againn go cinnte go bhfuil deilte ama teoranta aitheanta a bhfuil ráthaíocht ann go sroichfidh teachtaireacht ó nód amháin go chéile lena linn. Má tá an t-am seo caite agus nár tháinig an teachtaireacht, is féidir linn a rá go sábháilte gur theip ar an nód. Sa mhúnla seo tá amanna feithimh intuartha againn.
Múnla asincrónach – i múnlaí asincrónacha measaimid go bhfuil an t-am feithimh críochta, ach níl a leithéid de deilte ama ann ar féidir linn a ráthú ina dhiaidh sin gur theip ar an nód. Iad siúd. Féadfaidh an t-am feithimh do theachtaireacht ó nód a bheith treallach fada. Is sainmhíniú tábhachtach é seo, agus labhróimid faoi a thuilleadh.
Coincheap na comhthola i gcórais dáilte
Sula ndéantar coincheap an chomhaontaithe a shainiú go foirmiúil, déanaimis machnamh ar shampla de chás ina dteastaíonn sé uainn, eadhon - Macasamhlú Meaisín Stáit.
Tá roinnt loga dáilte againn. Ba mhaith linn go mbeadh sé comhsheasmhach agus go mbeadh sonraí comhionanna ann ar gach nóid den chóras dáilte. Nuair a fhoghlaimíonn ceann de na nóid luach nua go bhfuil sé chun scríobh chuig an loga, beidh sé de chúram air an luach seo a thairiscint do gach nóid eile ionas go nuashonraítear an logáil isteach ar gach nóid agus bogann an córas chuig staid chomhsheasmhach nua. Sa chás seo, tá sé tábhachtach go n-aontaíonn na nóid eatarthu féin: aontaíonn na nóid go léir go bhfuil an luach nua atá beartaithe ceart, go nglacann na nóid go léir an luach seo, agus ní féidir ach sa chás seo gach duine an luach nua a scríobh chuig an logáil.
I bhfocail eile: níor chuir aon cheann de na nóid in aghaidh go raibh faisnéis níos ábhartha ann, agus bhí an luach molta mícheart. Is comhdhearcadh é comhaontú idir nóid agus comhaontú ar luach ceart inghlactha amháin i gcóras dáilte. Ansin, beidh muid ag caint faoi halgartaim a cheadaíonn córas dáilte a ráthú chun teacht ar chomhdhearcadh.
Níos foirmeálta, is féidir linn algartam comhdhearcadh a shainiú (nó go simplí algartam comhdhearcadh) mar fheidhm áirithe a aistríonn córas dáilte ó stát A go stát B. Thairis sin, glactar leis an stát seo ag gach nóid, agus is féidir le gach nóid é a dhearbhú. Mar a tharla sé, níl an tasc seo ar chor ar bith chomh fánach agus is cosúil ar an gcéad amharc.
Airíonna an Algartam Comhthoil
Caithfidh trí airí a bheith ag an algartam comhaontaithe ionas gur féidir leis an gcóras leanúint de bheith ann agus roinnt dul chun cinn a dhéanamh maidir le bogadh ó stát go stát:
- Comhaontú – caithfidh an luach céanna a bheith ag gach nóid a fheidhmíonn i gceart (tugtar airí sábháilteachta freisin sna hairteagail seo). Ní mór do gach nód atá ag feidhmiú faoi láthair (nár theip nó nár chaill teagmháil leis na cinn eile) teacht ar chomhaontú agus glacadh le luach coiteann deiridh éigin.
Tá sé tábhachtach a thuiscint anseo gur mian leis na nóid sa chóras dáilte a bhfuilimid ag smaoineamh orthu aontú. Is é sin, táimid ag caint anois faoi chórais inar féidir le rud éigin a theipeann go simplí (mar shampla, teipeann ar roinnt nód), ach sa chóras seo níl aon nóid ann a oibríonn d'aon ghnó i gcoinne daoine eile (tasc na n-ard Byzantine). Mar gheall ar an maoin seo, tá an córas fós comhsheasmhach.
- Ionracas — má thairgeann na nóid atá ag obair i gceart an luach céanna v, rud a chiallaíonn go gcaithfidh gach nód atá ag feidhmiú i gceart glacadh leis an luach seo v.
- Foirceannadh – glacfaidh gach nód a fheidhmíonn i gceart ar deireadh thiar luach áirithe (airí beocht), rud a ligeann don algartam dul chun cinn a dhéanamh sa chóras. Ní mór do gach nód atá ag feidhmiú i gceart glacadh leis an luach deiridh luath nó mall agus é a dhearbhú: “Maidir liomsa, tá an luach seo fíor, aontaím leis an gcóras iomlán.”
Sampla den chaoi a n-oibríonn an t-algartam comhaontaithe
Cé nach féidir airíonna an algartam a bheith go hiomlán soiléir. Mar sin, léireoimid le sampla cad iad na céimeanna a théann an t-algartam comhdhearcadh is simplí i gcóras le múnla teachtaireachtaí sioncrónacha, ina bhfeidhmíonn gach nóid mar a bhíothas ag súil leis, nach gcailltear teachtaireachtaí agus ní bhriseann aon rud (an dtarlaíonn sé seo i ndáiríre?).
- Tosaíonn sé ar fad le togra pósadh (Moltaí). Glacaimid leis go bhfuil cliant ceangailte le nód ar a dtugtar "Nód 1" agus thosaigh sé idirbheart, a rith luach nua ar an nód - O. As seo amach, beidh muid ag glaoch "Nód 1" a mholadh. Mar mholtóir, ní mór do “Nód 1” a chur in iúl don chóras iomlán anois go bhfuil sonraí úra aige, agus seolann sé teachtaireachtaí chuig gach nóid eile: “Féach! Tháinig an bhrí “O” chugam agus ba mhaith liom é a scríobh síos! Deimhnigh le do thoil go ndéanfaidh tú “O” a thaifeadadh i do loga freisin.”
- Is í an chéad chéim eile vótáil ar son an luacha atá beartaithe (Vótáil). Cad atá i gceist leis? D'fhéadfadh sé tarlú go bhfuair nóid eile faisnéis níos déanaí, agus tá sonraí acu ar an idirbheart céanna.
Nuair a sheolann nód “Nód 1” a bheart, seiceálann na nóid eile a logaí le haghaidh sonraí ar an imeacht seo. Mura bhfuil aon contrárthachtaí ann, fógraíonn na nóid: “Tá, níl aon sonraí eile agam don imeacht seo. Is é an luach “O” an t-eolas is déanaí atá tuillte againn.”In aon chás eile, is féidir le nóid freagairt do “Nód 1”: “Éist! Tá sonraí níos déanaí agam faoin idirbheart seo. Ní 'O', ach rud éigin níos fearr."
Ag an gcéim vótála, tagann na nóid ar chinneadh: glacann siad go léir an luach céanna, nó vótálann duine acu ina choinne, rud a thugann le fios go bhfuil sonraí níos deireanaí aige.
- Má bhí an babhta vótála rathúil agus bhí gach duine i bhfabhar, ansin bogann an córas go dtí céim nua - Glacadh leis an luach. Bailíonn “Nóid 1” na freagraí go léir ó nóid agus tuairiscí eile: “D’aontaigh gach duine ar an luach “O”! Anois dearbhaím go hoifigiúil gurb é “O” an bhrí nua atá againn, mar an gcéanna do chách! Scríobh síos i do leabhar beag é, ná déan dearmad. Scríobh síos i do loga é!"
- Seolann na nóid atá fágtha deimhniú (Glactha) go bhfuil an luach “O” scríofa síos acu; níor tháinig aon rud nua isteach i rith an ama seo (gealltanas dhá chéim). Tar éis an teagmhais shuntasach seo, measaimid go bhfuil an t-idirbheart dáilte curtha i gcrích.
Mar sin, tá ceithre chéim san algartam comhdhearcaidh i gcás simplí: moladh, vótáil (vótáil), glacadh (glac leis), deimhnigh go nglacfar leis (glactar leis).
Más rud é ag céim éigin nach raibh muid in ann teacht ar chomhaontú, ansin tosaíonn an algartam arís, ag cur san áireamh an fhaisnéis a sholáthraíonn na nóid a dhiúltaigh an luach atá beartaithe a dhearbhú.
Algartam comhdhearcadh i gcóras asincrónach
Roimhe seo, bhí gach rud réidh, toisc go raibh muid ag caint faoi mhúnla teachtaireachtaí sioncrónacha. Ach tá a fhios againn go bhfuil taithí againn sa domhan nua-aimseartha ar gach rud a dhéanamh go neamhshioncronach. Conas a oibríonn algartam den chineál céanna i gcóras le múnla teachtaireachtaí asincrónacha, áit a gcreidimid gur féidir an t-am feithimh le haghaidh freagra ó nód a bheith treallach fada (dála an scéil, is féidir teip nód a mheas mar shampla freisin nuair a is féidir le nód freagairt ar feadh tréimhse treallach fada).
Anois go bhfuil a fhios againn conas a oibríonn an t-algartam comhdhearcadh i bprionsabal, ceist do na léitheoirí fiosracha sin a rinne é go dtí seo: cé mhéad nóid i gcóras nóid N le múnla teachtaireachta asincrónach a dteipeann orthu ionas gur féidir leis an gcóras teacht ar chomhdhearcadh fós?
Tá an freagra ceart agus an bonn cirt taobh thiar den spoiler.Is é an freagra ceart: 0. Má theipeann fiú nód amháin i gcóras asincrónach, ní bheidh an córas in ann teacht ar chomhdhearcadh. Tá an ráiteas seo cruthaithe sa teoirim FLP, a bhfuil aithne mhaith uirthi i gciorcail áirithe (1985, Fischer, Lynch, Paterson, nasc leis an mbunleagan ag deireadh an ailt): “An dodhéanta comhdhearcadh dáilte a bhaint amach má theipeann ar nód amháin ar a laghad. .”
Guys, ansin tá fadhb againn, táimid i dtaithí ar gach rud a bheith asincrónach. Agus anseo tá sé. Conas leanúint ar aghaidh ag maireachtáil?
Ní raibh muid ach ag caint faoi theoiric, faoi mhatamaitic. Cad is brí le “ní féidir comhdhearcadh a bhaint amach”, ag aistriú ó theanga na matamaitice go teanga na matamaitice againne – innealtóireacht? Ciallaíonn sé seo “nach féidir a bhaint amach i gcónaí”, i.e. Tá cás ann nach féidir comhaontú a bhaint amach. Cén cineál cáis é seo?
Is é seo go díreach an sárú ar an maoin liveness cur síos orthu thuas. Níl comhaontú coiteann againn, agus ní féidir dul chun cinn a dhéanamh ar an gcóras (ní féidir é a chríochnú in am teoranta) i gcás nach bhfuil freagra againn ó gach nód. Toisc i gcóras asincrónach níl aon am freagartha intuartha againn agus ní féidir a fhios againn cé acu an bhfuil nód tuairteála nó an bhfuil sé ach ag glacadh le tamall fada le freagairt.
Ach i ndáiríre is féidir linn teacht ar réiteach. Lig ár algartam a bheith in ann a bheith ag obair ar feadh i bhfad i gcás teipeanna (d'fhéadfadh sé a bheith ag obair ar feadh tréimhse éiginnte). Ach i bhformhór na gcásanna, nuair a bhíonn an chuid is mó nóid ag feidhmiú i gceart, beidh dul chun cinn againn sa chóras.
Go praiticiúil, déileálann muid le samhlacha cumarsáide atá sioncrónach go páirteach. Tuigtear mar seo a leanas sioncrónú páirteach: sa chás ginearálta, tá múnla asincrónach againn, ach tugtar isteach go foirmiúil coincheap áirithe “am cobhsaithe domhanda” de phointe áirithe ama.
Ní fhéadfaidh an nóiméad seo teacht ar feadh aon achair ama, ach caithfidh sé teacht lá amháin. Beidh an clog aláraim fíorúil ag glaoch, agus ón nóiméad sin is féidir linn a thuar cén t-am a dtiocfaidh na teachtaireachtaí amach. Ón nóiméad seo ar aghaidh, athraíonn an córas ó asincrónach go sioncrónach. Go praiticiúil, déileálaimid go beacht le córais dá leithéid.
Réitíonn algartam Paxos fadhbanna comhthola
Is teaghlach de halgartaim a réitíonn an fhadhb chomhthoil maidir le córais atá sioncrónach go páirteach, faoi réir an fhéidearthacht go dteipeann ar roinnt nóid. Is é an t-údar Paxos . Mhol sé cruthúnas foirmiúil i 1989 ar a bheith ann agus ar cheart an algartam.
Ach iompaigh an cruthúnas amach a bheith i bhfad ó fánach. Níor eisíodh an chéad fhoilseachán ach i 1998 (33 leathanach) ag cur síos ar an algartam. Mar a tharla sé, bhí sé thar a bheith deacair a thuiscint, agus i 2001 foilsíodh míniú ar an alt, a ghlac 14 leathanach. Tugtar líon na bhfoilseachán chun a thaispeáint nach bhfuil fadhb na comhthola simplí ar chor ar bith, agus taobh thiar de na halgartaim sin tá obair ollmhór ag na daoine is cliste.
Is suimiúil gur thug Leslie Lamport féin faoi deara ina léacht go bhfuil sa dara halt míniúcháin ráiteas amháin, líne amháin (níor shonraigh sé cén ceann), ar féidir a léirmhíniú ar bhealaí éagsúla. Agus mar gheall air seo, ní oibríonn líon mór feidhmiúcháin Paxos nua-aimseartha go hiomlán i gceart.
Thógfadh anailís mhionsonraithe ar obair Paxos níos mó ná alt amháin, mar sin déanfaidh mé iarracht príomhsmaoineamh an algartam a chur in iúl go hachomair. Sna naisc ag deireadh m'alt gheobhaidh tú ábhair chun tuilleadh tumadóireachta a dhéanamh ar an ábhar seo.
Róil ag Paxos
Tá coincheap róil ag algartam Paxos. Déanaimis machnamh ar thrí phríomhchinn (tá modhnuithe le róil bhreise):
- Moltóirí (is féidir na téarmaí a úsáid freisin: ceannairí nó comhordaitheoirí). Is iad seo na guys a fhoghlaim faoi roinnt luach nua ón úsáideoir agus a ghlacadh ar an ról mar cheannaire. Is é an tasc atá acu ná babhta moltaí a sheoladh le haghaidh luach nua agus gníomhaíochtaí breise na nóid a chomhordú. Ina theannta sin, ceadaíonn Paxos roinnt ceannairí a bheith i láthair i gcásanna áirithe.
- Glacadóirí (Vótálaithe). Is nóid iad seo a vótálann chun glacadh le luach áirithe nó diúltú dó. Tá a ról an-tábhachtach, toisc go mbraitheann an cinneadh orthu: cén stát a rachaidh (nó nach rachaidh) an córas tar éis an chéad chéim eile den algartam comhdhearcadh.
- Foghlaimeoirí. Nóid a ghlacann agus a scríobhann an luach nua a nglactar leis go simplí nuair a bhíonn staid an chórais athraithe. Ní dhéanann siad cinntí, ní fhaigheann siad ach na sonraí agus is féidir leo é a thabhairt don úsáideoir deiridh.
Is féidir le nód amháin róil éagsúla a chomhcheangal i gcásanna éagsúla.
Coincheap an chóram
Glacaimid leis go bhfuil córas de N nóid Agus acu an t-uasmhéid F féadfaidh nóid theipeann. Má theipeann ar nóid F, ansin ní mór dúinn a bheith ar a laghad 2F+1 nóid ghlacadóra.
Tá sé seo riachtanach ionas go mbeidh an chuid is mó againn i gcónaí, fiú amháin sa chás is measa, de nóid “mhaith” a oibríonn i gceart. Is é sin F+1 nóid "maith" a d'aontaigh, agus glacfar leis an luach deiridh. Seachas sin, d'fhéadfadh go mbeadh cás ann ina nglacann ár ngrúpaí áitiúla difriúla bríonna éagsúla agus nach féidir leo aontú eatarthu féin. Mar sin, teastaíonn tromlach glan uainn chun an vóta a bhuachan.
An smaoineamh ginearálta ar conas a oibríonn algartam comhdhearcadh Paxos
Tá dhá chéim mhóra i gceist le algartam Paxos, atá roinnte ina dhá chéim an ceann:
- Céim 1a: Ullmhaigh. Le linn na céime ullmhúcháin, cuireann an ceannaire (tairgeoir) gach nód ar an eolas: “Táimid ag tosú ar chéim nua vótála. Tá babhta nua againn. Is é uimhir an bhabhta seo ná n. Anois cuirfimid tús le vótáil." Go dtí seo, ní tuairiscíonn sé ach tús timthriall nua, ach ní thuairiscíonn sé luach nua. Is é tasc na céime seo ná babhta nua a thionscnamh agus gach duine a chur ar an eolas faoina uimhir uathúil. Tá an uimhir bhabhta tábhachtach, caithfidh sé a bheith ina luach níos mó ná na huimhreacha vótála go léir ó na ceannairí roimhe seo. Toisc gurb é a bhuíochas leis an uimhir bhabhta a thuigfidh nóid eile sa chóras cé chomh déanaí is atá sonraí an cheannaire. Is dócha go bhfuil torthaí vótála ag nóid eile cheana féin ó bhabhtaí i bhfad níos déanaí agus go simplí inseoidh siad don cheannaire go bhfuil sé taobh thiar de na hamanna.
- Céim 1b: Gealltanas. Nuair a fhaigheann na nóid glactha uimhir na céime nua vótála, is féidir dhá thoradh a dhéanamh:
- Is mó uimhir n an vóta nua ná uimhir aon vóta roimhe sin inar ghlac an glacadóir páirt. Ansin cuireann an glacadóir gealltanas chuig an gceannaire nach nglacfaidh sé páirt i níos mó vótaí le líon níos ísle ná n. Má tá an glacadóir vótáil ar son rud éigin cheana féin (is é sin, tá sé glactha cheana féin ar luach éigin sa dara céim), ansin cuireann sé an luach glactha agus uimhir na vótála inar ghlac sé lena gheallúint.
- Seachas sin, má tá a fhios ag an nglacadóir cheana féin faoin vóta a bhfuil a uimhriú níos airde, is féidir leis neamhaird a dhéanamh den chéim ullmhúcháin agus gan freagra a thabhairt don cheannaire.
- Céim 2a: Glac leis. Ní mór don cheannaire fanacht le freagra ón gcóram (tromlach na nóid sa chóras) agus, má fhaightear an líon riachtanach freagraí, tá dhá rogha aige maidir le forbairt imeachtaí:
- Sheol cuid de na glacadóirí luachanna a raibh vóta acu cheana féin ar a son. Sa chás seo, roghnaíonn an ceannaire an luach ón vóta leis an uaslíon. Glaoimis x ar an luach seo, agus seolann sé teachtaireacht chuig gach nód mar: “Glac (n, x)”, áit arb é an chéad luach an uimhir vótála óna chéim Molta féin, agus is é an dara luach an rud a bhailigh gach duine dó, i.e. an luach a ndéanaimid vótáil air.
- Mura sheol aon cheann de na glacadóirí aon luachanna, ach go simplí gheall siad vótáil sa bhabhta seo, is féidir leis an gceannaire cuireadh a thabhairt dóibh vótáil ar son a luach, arbh é an luach a tháinig sé ina cheannaire sa chéad áit. Glaoimis y air. Seolann sé teachtaireacht chuig gach nóid mar: “Glac (n, y)”, cosúil leis an toradh roimhe seo.
- Céim 2b: Glactha. Thairis sin, aontaíonn nóid an ghlacadóra, tar éis dóibh an teachtaireacht “Glac (...)” a fháil ón gceannaire, (cuir deimhniú chuig na nóid go léir go n-aontaíonn siad leis an luach nua) ach amháin mura bhfuil roinnt (eile) geallta acu ) ceannaire páirt a ghlacadh sa vótáil le huimhir bhabhta n' > n, ar shlí eile déanann siad neamhaird den iarratas deimhnithe.
Má d'fhreagair tromlach na nóid don cheannaire, agus dhearbhaigh gach ceann acu an luach nua, ansin meastar go nglactar leis an luach nua. Hooray! Mura sroichtear an tromlach nó má tá nóid ann a dhiúltaigh glacadh leis an luach nua, tosaíonn gach rud thart.
Seo mar a oibríonn algartam Paxos. Tá go leor subtleties ag gach ceann de na céimeanna seo, níor mheasamar go praiticiúil cineálacha éagsúla teipeanna, fadhbanna ceannairí iolracha agus i bhfad níos mó, ach is é cuspóir an ailt seo ach an léitheoir a thabhairt isteach i saol na ríomhaireachta dáilte ag leibhéal ard.
Is fiú a thabhairt faoi deara freisin nach é Paxos an t-aon cheann dá leithéid, tá halgartaim eile ann, mar shampla, , ach is ábhar é seo le haghaidh alt eile.
Naisc chuig ábhair le haghaidh tuilleadh staidéir
Bunleibhéal:
- , Preethi Kasireddy, alt blag ar Meánach
- , Adi Kancherla, alt blag ar Meánach
- , Ittai Abraham, blog
- , Ittai Abraham, blog alt
Leibhéal Leslie Lamport:
- , Fischer, Lynch agus Paterson, páipéar taighde, 1985
- , Leslie Lamport, páipéar taighde, 1998
- , Leslie Lamport, páipéar taighde, 2001
Foinse: will.com