Ku kituna, hayu urang ngabayangkeun. Aya 5 ucing dikonci di kamar, sarta dina raraga balik hudang nepi nu boga, maranéhanana kabéh kudu satuju dina ieu diantara sorangan, sabab ngan bisa muka panto jeung lima di antarana condong kana eta. Upami salah sahiji ucing nyaéta ucing Schrödinger, sareng ucing sanésna henteu terang ngeunaan kaputusanna, patarosan timbul: "Kumaha aranjeunna tiasa ngalakukeunana?"
Dina artikel ieu, kuring bakal ngabejaan Anjeun dina istilah basajan ngeunaan komponén téoritis dunya sistem disebarkeun jeung prinsip operasi maranéhanana. Kuring ogé bakal superficially nalungtik gagasan utama kaayaan Paxos.
Nalika pamekar ngagunakeun infrastruktur awan, rupa-rupa basis data, sareng dianggo dina klaster sajumlah ageung titik, aranjeunna yakin yén datana bakal lengkep, aman, sareng salawasna sayogi. Tapi dimana jaminan?
Intina, jaminan anu kami gaduh nyaéta jaminan supplier. Éta dijelaskeun dina dokuméntasi sapertos kieu: "Layanan ieu cukup dipercaya, éta ngagaduhan SLA anu dipasihkeun, tong hariwang, sadayana bakal dianggo sacara disebarkeun sakumaha anu anjeun ngarepkeun."
Urang condong percanten ka pangalusna, sabab guys pinter ti pausahaan badag assured kami yén sagalana bakal rupa. Kami henteu naroskeun patarosan: naha, kanyataanna, ieu tiasa dianggo pisan? Naha aya alesan resmi pikeun operasi anu leres tina sistem sapertos kitu?
Kuring nembe indit ka sarta ieu pisan diideuan ku topik ieu. Kuliah di sakola éta leuwih kawas kelas kalkulus ti hal nu patali jeung sistem komputer. Tapi ieu persis kumaha algoritma anu paling penting anu kami anggo unggal dinten, tanpa terang, dibuktikeun dina hiji waktos.
Paling sistem disebarkeun modern ngagunakeun algoritma konsensus Paxos jeung sagala rupa modifikasi na. Hal anu paling keren nyaéta validitas sareng, prinsipna mah, kamungkinan ayana algoritma ieu tiasa dibuktikeun ngan saukur ku pulpén sareng kertas. Dina prakték, algoritma dipaké dina sistem badag ngajalankeun on jumlah badag titik dina awan.
Hiji ilustrasi lampu naon bakal dibahas salajengna: tugas dua jenderalHayu urang tingali pikeun pemanasan .
Urang boga dua tentara - beureum jeung bodas. Pasukan bodas dumasar di kota anu dikepung. Pasukan beureum anu dipimpin ku jenderal A1 sareng A2 aya di dua sisi kota. tugas redheads 'nyaéta narajang kota bodas tur meunang. Sanajan kitu, tentara unggal jenderal beureum individual leuwih leutik batan tentara bodas.
Kaayaan meunangna pikeun anu beureum: duanana jenderal kedah nyerang dina waktos anu sami supados gaduh kaunggulan numerik tibatan bodas. Jang ngalampahkeun ieu, jenderal A1 jeung A2 kudu datang ka hiji perjangjian saling. Lamun dulur nyerang misah, nu redheads bakal leungit.
Pikeun ngahontal kasapukan, jenderal A1 sareng A2 tiasa ngirim utusan ka silih ngalangkungan wilayah kota bodas. Utusan éta tiasa suksés ngahontal jenderal sekutu atanapi tiasa dicegat ku musuh. Patarosan: naha aya sekuen sapertos komunikasi antara jenderal berambut beureum (runtuyan ngirim utusan ti A1 ka A2 sabalikna ti A2 ka A1), dimana aranjeunna dijamin satuju kana serangan dina jam X. Ieuh, jaminan hartina duanana jenderal bakal boga konfirmasi unambiguous yén hiji sekutu (jendral sejen) pasti bakal narajang dina waktu nu ditunjuk X.
Anggap A1 ngirim utusan ka A2 kalayan pesen: "Hayu urang nyerang ayeuna tengah wengi!" Umum A1 teu bisa nyerang tanpa konfirmasi ti Umum A2. Upami utusan ti A1 parantos sumping, maka Jenderal A2 ngirim konfirmasi kalayan pesen: "Leres, hayu urang maéhan bule ayeuna." Tapi ayeuna Jenderal A2 henteu terang naha utusanna parantos sumping atanapi henteu, anjeunna henteu ngajamin naha seranganna bakal sakaligus. Ayeuna Umum A2 deui peryogi konfirmasi.
Lamun urang ngajelaskeun salajengna komunikasi maranéhanana, janten jelas yén euweuh urusan sabaraha siklus bursa pesen aya, euweuh jalan pikeun ngajamin yén duanana jenderal geus narima pesen maranéhanana (asumsina yén boh utusan bisa disadap).
Masalah Dua Jendral mangrupikeun ilustrasi anu saé ngeunaan sistem distribusi anu saderhana pisan dimana aya dua titik kalayan komunikasi anu teu tiasa dipercaya. Ieu ngandung harti yén urang teu boga 100% jaminan yén maranéhna téh nyingkronkeun. Masalah anu sami dibahas ngan dina skala anu langkung ageung engké dina tulisan.
Urang ngawanohkeun konsép sistem disebarkeun
Sistem anu disebarkeun nyaéta sakumpulan komputer (satuluyna urang bakal disebut titik) anu tiasa tukeur pesen. Unggal titik individu mangrupikeun sababaraha éntitas otonom. Hiji titik tiasa ngolah tugas nyalira, tapi pikeun komunikasi sareng titik anu sanés, éta kedah ngirim sareng nampi pesen.
Kumaha persisna pesen dilaksanakeun, naon protokol anu dianggo - ieu henteu dipikaresep ku urang dina kontéks ieu. Penting yén titik-titik tina sistem anu disebarkeun tiasa silih tukeur data ku cara ngirim pesen.
Definisi sorangan teu kasampak pisan pajeulit, tapi urang kudu tumut kana akun yén sistem disebarkeun ngabogaan sajumlah atribut anu bakal penting pikeun urang.
Atribut tina sistem disebarkeun
- Konflik - kamungkinan kajadian sakaligus atanapi sakaligus lumangsung dina sistem. Sumawona, urang bakal nganggap kajadian anu lumangsung dina dua titik anu béda janten berpotensi babarengan salami urang henteu gaduh urutan anu jelas ngeunaan kajadian ieu. Tapi, sakumaha aturan, urang teu boga eta.
- Taya jam global. Kami henteu gaduh urutan acara anu jelas kusabab kurangna jam global. Di dunya jalma biasa, urang biasa kanyataan yén urang gaduh jam sareng waktos leres pisan. Sagalana robah lamun datang ka sistem disebarkeun. Malah jam atom ultra-tepat geus drift, sarta meureun aya kaayaan dimana urang teu bisa ngabejaan mana tina dua kajadian munggaran. Ku alatan éta, urang ogé teu bisa ngandelkeun waktu.
- Gagalna mandiri tina titik sistem. Aya masalah anu sanés: aya anu salah kusabab titik-titik kami henteu salamina. Hard drive tiasa gagal, mesin virtual dina awan tiasa reboot, jaringan tiasa kedip-kedip sareng pesen bakal leungit. Sumawona, meureun aya kaayaan dimana titik dianggo, tapi dina waktos anu sami dianggo ngalawan sistem. Kelas panungtungan masalah malah narima ngaran misah: masalah . Conto anu paling populér tina sistem anu disebarkeun kalayan masalah ieu nyaéta Blockchain. Tapi ayeuna urang moal nganggap kelas husus ieu masalah. Urang bakal kabetot dina kaayaan anu ngan saukur hiji atanapi langkung titik tiasa gagal.
- Modél komunikasi (model olahtalatah) antara titik. Kami parantos netepkeun yén titik komunikasi ku cara tukeur pesen. Aya dua model olahtalatah anu terkenal: sinkron sareng asinkron.
Model komunikasi antara titik dina sistem disebarkeun
Modél sinkron - urang terang pasti yén aya délta anu dipikanyaho waktos salami pesen dijamin ngahontal ti hiji titik ka titik anu sanés. Upami waktos ieu parantos lami sareng pesenna teu acan sumping, urang aman tiasa nyarios yén titik éta gagal. Dina modél ieu kami gaduh waktos ngantosan anu tiasa diprediksi.
Modél Asynchronous - dina model Asynchronous urang nganggap yén waktu antosan téh terhingga, tapi euweuh délta misalna waktu sanggeus nu bisa ngajamin yén titik geus gagal. Jelema. Waktu ngantosan pesen ti node tiasa panjang. Ieu mangrupa harti penting, sarta kami bakal ngobrol ngeunaan eta salajengna.
Konsep konsensus dina sistem disebarkeun
Sateuacan sacara resmi netepkeun konsép konsensus, hayu urang tingali conto kaayaan dimana urang peryogina, nyaéta - Réplikasi Mesin kaayaan.
Simkuring gaduh sababaraha log disebarkeun. Kami hoyong éta konsisten sareng ngandung data anu sami dina sadaya titik sistem anu disebarkeun. Nalika salah sahiji titik diajar hiji nilai anyar nu eta bade nulis log, tugas na janten nawiskeun nilai ieu ka sadaya titik lianna ku kituna log ieu diropéa dina sakabéh titik sarta sistem pindah ka kaayaan konsisten anyar. Dina hal ieu, penting yén titik-titik satuju diantarana: sadaya titik satuju yén nilai anyar anu diusulkeun leres, sadaya titik nampi nilai ieu, sareng ngan dina hal ieu sadayana tiasa nyerat nilai énggal kana log.
Kalayan kecap séjén: taya sahiji titik objected yén éta miboga émbaran leuwih relevan, sarta nilai diusulkeun éta lepat. Kasapukan antara titik jeung perjangjian dina nilai katampa bener tunggal mangrupakeun konsensus dina sistem disebarkeun. Salajengna, urang bakal ngobrol ngeunaan algoritma anu ngamungkinkeun sistem disebarkeun pikeun ngahontal konsensus dijamin.
Leuwih formal, urang bisa nangtukeun hiji algoritma konsensus (atawa ngan saukur algoritma konsensus) salaku fungsi nu tangtu nu mindahkeun sistem disebarkeun ti kaayaan A ka kaayaan B. Leuwih ti éta, kaayaan ieu ditarima ku sakabeh titik, sarta sakabeh titik bisa mastikeun eta. Salaku tétéla, tugas ieu teu pisan trivial sakumaha sigana di glance kahiji.
Pasipatan tina Algoritma Konsensus
Algoritma konsensus kedah gaduh tilu sipat supados sistem tetep aya sareng gaduh sababaraha kamajuan dina mindahkeun tina kaayaan ka nagara:
- perjangjian - sadaya titik operasi anu leres kedah nyandak nilai anu sami (dina artikel sipat ieu ogé disebut salaku harta kaamanan). Sadaya titik anu ayeuna fungsina (henteu gagal atanapi leungit kontak sareng anu sanés) kedah sumping ka perjanjian sareng nampi sababaraha nilai umum anu terakhir.
Kadé ngartos didieu yén titik dina sistem disebarkeun kami tempo hoyong satuju. Hartina, ayeuna urang ngobrol ngeunaan sistem nu hal bisa saukur gagal (contona, sababaraha titik gagal), tapi dina sistem ieu pasti euweuh titik nu ngahaja dianggo ngalawan batur (tugas jenderal Bizantium). Alatan sipat ieu, sistem tetep konsisten.
- kajembaran ati - upami sadaya titik anu leres dianggo nawiskeun nilai anu sami v, anu hartosna unggal titik operasi anu leres kedah nampi nilai ieu v.
- saenggeus - sadaya titik operasi leres antukna bakal nyandak hiji nilai nu tangtu (milik liveness), nu ngidinan algoritma pikeun nyieun kamajuan dina sistem. Masing-masing individu anu leres-leres operasi kedah gancang-gancang nampi nilai akhir sareng mastikeun: "Kanggo kuring, nilai ieu leres, kuring satuju sareng sadayana sistem."
Conto kumaha algoritma konsensus jalan
Sedengkeun sipat algoritma bisa jadi teu sagemblengna jelas. Kituna, urang bakal ngagambarkeun kalayan conto naon tahapan algoritma konsensus pangbasajanna ngaliwatan dina sistem kalawan model olahtalatah sinkron, nu sagala titik fungsi saperti nu diharapkeun, pesen teu leungit jeung euweuh ngarecah (naha ieu bener kajadian?).
- Eta sadayana dimimitian ku proposal nikah (Ngalamar). Hayu urang nganggap yén hiji klien disambungkeun ka titik disebut "titik 1" na dimimitian transaksi, ngalirkeun nilai anyar pikeun titik - O. Ti ayeuna, urang bakal nelepon "titik 1" ngalamar. Salaku proposer a, "Node 1" ayeuna kudu ngabéjaan sakabéh sistem nu boga data seger, sarta eta ngirimkeun pesen ka sadaya titik lianna: "Tingali! Harti "O" sumping ka kuring sareng abdi hoyong nyeratna! Punten pastikeun yén anjeun ogé bakal ngarékam "O" dina log anjeun."
- Tahap salajengna nyaéta voting pikeun nilai anu diusulkeun (Voting). Keur naon eta? Ieu bisa lumangsung yén titik lianna geus narima informasi leuwih panganyarna, sarta aranjeunna gaduh data dina urus sarua.
Nalika titik "Node 1" ngirimkeun proposalna, titik-titik anu sanés pariksa logna pikeun data ngeunaan acara ieu. Upami teu aya kontradiksi, titik-titik ngumumkeun: "Leres, kuring henteu gaduh data sanés pikeun acara ieu. Nilai "O" mangrupikeun inpormasi panganyarna anu pantes pikeun urang.Dina kasus anu sanés, titik tiasa ngabales "Node 1": "Dengekeun! Kuring boga data leuwih panganyarna dina transaksi ieu. Henteu 'O', tapi anu langkung saé."
Dina tahap voting, titik datang ka kaputusan: boh aranjeunna sadayana nampi nilai anu sami, atanapi salah sahijina milih ngalawan, nunjukkeun yén anjeunna gaduh data anu langkung énggal.
- Lamun babak voting éta suksés jeung dulur éta dina kahadean, lajeng sistem ngalir ka tahap anyar - Narima nilai. "Node 1" ngumpulkeun sagala réspon ti titik sejen tur laporan: "Sarerea sapuk dina nilai "O"! Ayeuna kuring sacara resmi nyatakeun yén "O" mangrupikeun hartos énggal urang, sami pikeun sadayana! Tuliskeun dina buku leutik anjeun, tong hilap. Tuliskeun dina log anjeun!”
- Titik sésa ngirimkeun konfirmasi (Ditampa) yén aranjeunna parantos nyerat nilai "O"; teu aya anu énggal dugi ka waktos ieu (sajenis komitmen dua fase). Saatos kajadian anu penting ieu, urang nganggap yén transaksi anu disebarkeun parantos réngsé.
Ku kituna, algoritma konsensus dina pasualan basajan diwangun ku opat léngkah: ngajukeun, milih (voting), narima (narima), mastikeun ditampa (ditampi).
Upami dina sababaraha léngkah kami henteu tiasa ngahontal kasapukan, teras algoritmana dimimitian deui, kalayan ngémutan inpormasi anu disayogikeun ku titik-titik anu nolak pikeun ngonfirmasi nilai anu diusulkeun.
Algoritma konsensus dina sistem asynchronous
Sateuacan ieu, sadayana lancar, sabab urang ngobrol ngeunaan modél olahtalatah sinkron. Tapi urang terang yén di dunya modéren urang biasa ngalakukeun sagalana asynchronously. Kumaha algoritma anu sami tiasa dianggo dina sistem anu nganggo modél olahtalatah asinkron, dimana kami yakin yén waktos ngantosan réspon ti node tiasa sawenang-wenang panjang (ku jalan kitu, gagalna node ogé tiasa dianggap salaku conto nalika titik hiji bisa ngabales pikeun lila wenang).
Ayeuna urang terang kumaha algoritma konsensus tiasa dianggo prinsipna, patarosan pikeun pamiarsa anu hoyong terang anu parantos dugi ka: sabaraha titik dina sistem titik N kalayan modél pesen asinkron tiasa gagal sahingga sistem masih tiasa ngahontal konsensus?
Jawaban anu leres sareng leresan aya di tukangeun spoiler.jawaban nu bener: 0. Upami salah sahiji titik dina sistem asinkron gagal, sistem moal tiasa ngahontal konsensus. Pernyataan ieu dibuktikeun dina téoréma FLP, dipikawanoh di kalangan tangtu (1985, Fischer, Lynch, Paterson, numbu ka aslina dina ahir artikel): "The impossibility tina achieving konsensus disebarkeun lamun sahanteuna hiji titik gagal. .”
Lalaki, teras urang gaduh masalah, urang biasa sadayana henteu sinkron. Sarta di dieu éta. Kumaha neruskeun hirup?
Kami ngan ngobrol ngeunaan teori, ngeunaan matematika. Naon hartosna "konsensus teu tiasa dihontal", narjamahkeun tina basa matematika kana basa urang - rékayasa? Ieu ngandung harti yén "teu salawasna bisa dihontal", i.e. Aya kasus dimana konsensus henteu tiasa dicapai. Kasus naon ieu?
Ieu persis palanggaran harta liveness ditétélakeun di luhur. Urang teu boga perjangjian umum, jeung sistem teu bisa boga kamajuan (teu bisa ngalengkepan dina jangka waktu nu tangtu) dina kasus dimana urang teu boga respon ti sadaya titik. Kusabab dina sistem asynchronous urang teu boga waktu respon bisa diprediksi tur urang teu bisa nyaho naha titik geus nabrak atawa ngan butuh waktu lila pikeun ngabales.
Tapi dina prakna urang bisa manggihan solusi. Hayu algoritma urang tiasa dianggo pikeun lila bisi gagal (berpotensi bisa dianggo salamina). Tapi dina sabagéan ageung kaayaan, nalika kalolobaan titik berpungsi leres, urang bakal ngagaduhan kamajuan dina sistem.
Dina prakna, urang nungkulan model komunikasi sawaréh sinkron. Sinkronisasi parsial dipikaharti saperti kieu: dina kasus umum, urang boga model Asynchronous, tapi konsép tangtu "waktu stabilisasi global" tina titik nu tangtu dina jangka waktu anu resmi diwanohkeun.
Momen dina jangka waktu ieu bisa jadi teu datang pikeun lila, tapi kudu datangna hiji poé. Jam alarm virtual bakal hurung, sareng ti waktos éta urang tiasa ngaduga délta waktos dimana pesen bakal sumping. Ti momen ieu, sistem robah tina asynchronous ka sinkron. Dina prakték, urang nungkulan persis sistem sapertos.
Algoritma Paxos ngarengsekeun masalah konsensus
mangrupakeun kulawarga algoritma nu ngajawab masalah konsensus pikeun sistem sawaréh sinkron, tunduk kana kamungkinan yén sababaraha titik bisa gagal. Panulis Paxos nyaéta . Anjeunna ngusulkeun bukti resmi ngeunaan ayana sareng kabeneran algoritma dina 1989.
Tapi buktina tétéla jauh tina hal anu teu pati penting. Publikasi munggaran dirilis ngan dina 1998 (33 kaca) ngajéntrékeun algoritma. Salaku tétéla, éta pisan hésé ngarti, sarta dina 2001 diterbitkeun katerangan artikel, nu nyandak 14 kaca. Volume publikasi dirumuskeun dina urutan pikeun mintonkeun yen dina kanyataanana masalah konsensus teu pisan basajan, sarta di balik algoritma sapertos perenahna jumlah badag karya jalma smartest.
Éta metot yén Leslie Lamport dirina nyatet dina ceramah na yén dina artikel explanatory kadua aya hiji pernyataan, hiji baris (anjeunna teu nangtukeun mana hiji), nu bisa diinterpretasi ku cara béda. Sarta alatan ieu, angka nu gede ngarupakeun palaksanaan Paxos modern teu dianggo sagemblengna leres.
Analisis detil karya Paxos bakal nyandak langkung ti hiji artikel, ku kituna kuring bakal nyobian sakedap pisan nepikeun ide utama algoritma éta. Dina tautan di tungtung tulisan kuring anjeun bakal mendakan bahan pikeun nyilem salajengna kana topik ieu.
Kalungguhan di Paxos
Algoritma Paxos ngagaduhan konsép peran. Hayu urang nganggap tilu utama (aya modifikasi jeung kalungguhan tambahan):
- Proposer (istilahna ogé tiasa dianggo: pamimpin atanapi koordinator). Ieu mangrupikeun jalma-jalma anu diajar ngeunaan sababaraha nilai anyar ti pangguna sareng nyandak peran pamimpin. Tugasna nyaéta ngaluncurkeun usulan pikeun nilai anyar sareng koordinat tindakan salajengna tina titik. Sumawona, Paxos ngamungkinkeun ayana sababaraha pamimpin dina kaayaan anu tangtu.
- Akséptor (Pamilih). Ieu mangrupikeun titik anu milih nampi atanapi nampik nilai khusus. Peranna penting pisan, sabab kaputusan gumantung kana aranjeunna: naon kaayaan sistem bakal (atanapi henteu) angkat saatos tahap salajengna tina algoritma konsensus.
- Peserta. Titik anu ngan ukur nampi sareng nyerat nilai anu katampi nalika kaayaan sistem parantos robih. Aranjeunna henteu nyandak kaputusan, aranjeunna ngan ukur nampi data sareng tiasa masihan ka pangguna akhir.
Hiji titik bisa ngagabungkeun sababaraha peran dina situasi béda.
Konsep kuorum
Urang nganggap yen urang boga sistem tina N titik-titik Jeung di antarana maksimum F titik bisa gagal. Lamun titik F gagal, mangka urang kudu boga sahanteuna 2F+1 titik akséptor.
Ieu diperlukeun ku kituna urang salawasna mibanda mayoritas, sanajan dina kaayaan awon, titik "alus" anu jalan leres. nyaeta F+1 titik "alus" nu sapuk, sarta nilai final bakal katampa. Upami teu kitu, meureun aya kaayaan dimana grup lokal urang béda nyandak harti béda jeung teu bisa akur diantara sorangan. Ku alatan éta, urang peryogi mayoritas mutlak pikeun meunang sora.
Gagasan umum kumaha algoritma konsensus Paxos jalan
Algoritma Paxos ngalibatkeun dua fase ageung, anu masing-masing dibagi jadi dua léngkah:
- Fase 1a: Nyiapkeun. Salila fase persiapan, pamimpin (proposer) nginpokeun ka sadaya titik: "Kami ngamimitian fase voting anyar. Urang boga babak anyar. Jumlah babak ieu n. Ayeuna urang bakal ngamimitian milih." Pikeun ayeuna, éta ngan saukur ngalaporkeun mimiti siklus anyar, tapi henteu ngalaporkeun nilai anyar. Tugas tahap ieu nyaéta pikeun ngamimitian babak anyar sareng nginpokeun ka sadayana ngeunaan nomer unikna. Jumlah babak penting, eta kudu jadi nilai gede ti sakabeh nomer voting saméméhna ti sakabeh pamingpin saméméhna. Kusabab éta hatur nuhun kana jumlah buleud anu titik-titik anu sanés dina sistem bakal ngartos kumaha data pamimpin panganyarna. Éta kamungkinan yén titik-titik sanés parantos gaduh hasil voting ti babak-babak engké sareng ngan saukur bakal nyarioskeun ka pamimpin yén anjeunna tinggaleun jaman.
- Fase 1b: Jangji. Nalika titik akséptor nampi jumlah tahap voting anyar, dua hasil anu mungkin:
- Jumlah n tina sora anyar leuwih gede ti jumlah sagala sora saméméhna nu akseptor milu. Lajeng acceptor ngirimkeun jangji ka pamimpin yén éta moal ilubiung dina sagala sora deui kalawan jumlah leuwih handap n. Upami anu nampi parantos milih hiji hal (nyaéta, éta parantos nampi sababaraha nilai dina fase kadua), teras éta nempelkeun nilai anu ditampi sareng jumlah sora anu anjeunna milu kana jangjina.
- Upami teu kitu, upami anu akseptor parantos terang ngeunaan sora anu langkung ageung, éta tiasa waé teu malire léngkah persiapan sareng henteu ngabales pamimpin.
- Fase 2a: Narima. Pamimpin kedah ngantosan réspon ti kuorum (seuseueurna titik dina sistem) sareng, upami jumlah réspon anu diperyogikeun ditampi, maka anjeunna gaduh dua pilihan pikeun ngembangkeun acara:
- Sababaraha akséptor ngirimkeun nilai anu aranjeunna parantos milih. Dina hal ieu, pamimpin milih nilai tina sora kalayan jumlah maksimum. Nyauran nilai ieu x, sareng éta ngirim pesen ka sadaya titik sapertos: "Tampa (n, x)", dimana nilai anu munggaran nyaéta nomer voting tina léngkah Usul sorangan, sareng nilai anu kadua nyaéta naon anu dikumpulkeun ku sadayana. i.e. nilai nu sabenerna urang milih.
- Upami teu aya anu nampi nilai anu dikirimkeun, tapi aranjeunna ngan ukur janji pikeun milih dina babak ieu, pamimpin tiasa ngajak aranjeunna milih nilaina, nilai anu anjeunna janten pamimpin di tempat munggaran. Hayu urang sebut wae y. Ieu ngirimkeun pesen ka sadaya titik kawas: "Tampa (n, y)", sarupa jeung hasil saméméhna.
- Fase 2b: Ditampa. Salajengna, titik akséptor, nalika nampi pesen "Tampa (...)" ti pamimpin, satuju sareng éta (ngirim konfirmasi ka sadaya titik yén aranjeunna satuju sareng nilai énggal) ngan upami aranjeunna henteu ngajangjikeun sababaraha (lain) ) pamingpin pikeun ilubiung dina voting kalawan nomer buleud n' > n, disebutkeun aranjeunna malire pamundut konfirmasi.
Upami seuseueurna titik ngaréspon pamimpin, sareng sadayana dikonfirmasi nilai énggal, maka nilai énggal dianggap katampi. Horeeee! Upami seuseueurna henteu ngahontal atanapi aya titik anu nampik nampi nilai énggal, maka sadayana ngamimitian deui.
Ieu kumaha algoritma Paxos jalan. Masing-masing tahapan ieu ngagaduhan seueur subtleties, urang sacara praktis henteu nganggap rupa-rupa kagagalan, masalah sababaraha pamimpin sareng seueur deui, tapi tujuan tulisan ieu ngan ukur pikeun ngenalkeun pamaca ka dunya komputasi anu disebarkeun dina tingkat anu luhur.
Perhatos ogé yén Paxos sanés ngan ukur jinisna, aya algoritma anu sanés, contona, , tapi ieu topik pikeun artikel séjén.
Tumbu ka bahan pikeun ulikan salajengna
Tingkat pemula:
- , Preethi Kasireddy, artikel blog on Medium
- , Adi Kancherla, artikel blog on Medium
- , Ittai Abraham, blog
- , Ittai Abraham, artikel blog
Tingkat Leslie Laport:
- , Fischer, Lynch jeung Paterson, makalah panalungtikan, 1985
- , Leslie Lamport, makalah panalungtikan, 1998
- , Leslie Lamport, makalah panalungtikan, 2001
sumber: www.habr.com