Оддын зөвшилцлийн протоколыг анх өгүүлсэн Дэвид Мазиер 2015 онд. Энэ нь төвлөрсөн бус, удирдагчгүй тооцоолох сүлжээнүүдэд шийдвэр дээр үр дүнтэй зөвшилцөлд хүрэх боломжийг олгодог "холбооны Византийн гэрээний систем" юм. Stellar төлбөрийн сүлжээ нь бүх оролцогчдод харагдахуйц гүйлгээний түүхийг тогтвортой байлгахын тулд Оддын зөвшилцлийн протоколыг (SCP) ашигладаг.
Зөвшилцлийн протоколыг ойлгоход хэцүү гэж үздэг. Шинжлэх ухааны нийтлэлийн эхний хагасын сэдэв болох "холбооны санал хураалт" нь SCP гэсэн буруу ойлголттой холбоотой SCP нь тэдний ихэнхийг бодвол энгийн боловч энэ нэр хүндийг хуваалцдаг. Гэхдээ энэ нь үнэн биш юм! Энэ бол нийтлэлийн хоёрдугаар хагаст бүтээхэд ашигладаг чухал барилгын блок юм бодит Оддын зөвшилцлийн протокол.
Энэ нийтлэлд бид "гэрээний систем" гэж юу болох, түүнийг "Византийн" болгож чадах зүйл, яагаад Византийн системийг "холбооны" болгох талаар товч тайлбарлах болно. Дараа нь бид SCP-ийн нийтлэлд дурдсан нэгдсэн санал хураалтын журмыг тайлбарлаж, эцэст нь бид SCP протоколыг өөрөө тайлбарлах болно.
Гэрээний системүүд
Хэлэлцээрийн систем нь хэсэг оролцогчдод үдийн хоолонд юу захиалах гэх мэт сэдвээр зөвшилцөх боломжийг олгодог.
Interstellar-д бид өөрсдийн хоолны гэрээний системийг хэрэгжүүлсэн: үйл ажиллагааны менежер Жонын хэлснээр бид захиалга өгдөг. Энэ бол энгийн бөгөөд үр дүнтэй гэрээний систем юм. Бид бүгд Жонд итгэж, түүнийг өдөр бүр сонирхолтой, тэжээллэг зүйл олж авна гэдэгт итгэдэг.
Гэхдээ Жон бидний итгэлийг урвуулан ашигласан бол яах вэ? Тэр бид бүгдээрээ веган болох ёстой гэж ганцаараа шийдэж чадна. Нэг, хоёр долоо хоногийн дараа бид түүнийг түлхэн унагаж, эрх мэдлийг Элизабетт өгөх байх. Гэтэл гэнэт тэр анчоустай авокадонд дуртай болж, хүн бүр ийм байх ёстой гэж боддог. Эрх мэдэл нь сүйрүүлдэг. Тиймээс илүү ардчилсан аргыг хайж олох нь дээр: өөр өөр сонголтыг анхаарч үзэхийн тулд цаг тухайд нь бөгөөд тодорхой үр дүнд хүрэхийн тулд хэн ч үдийн хоол захиалахгүй, эсвэл таван хүн өөр захиалга өгөхгүй байх, эсвэл хэлэлцүүлэг хийхгүй байхыг баталгаажуулах арга зам юм. орой руу чирдэг.
Шийдэл нь энгийн юм шиг санагдаж байна: санал хураалт явуулаарай! Гэхдээ энэ бол төөрөгдүүлсэн сэтгэгдэл юм. Саналын хуудсыг хэн цуглуулж дүнг мэдээлэх вэ? Түүний хэлсэн үгэнд бусад хүмүүс яагаад итгэх ёстой гэж? Магадгүй бид чадна эхэндээ санал хураалтыг удирдана гэдэгт итгэлтэй байгаа удирдагчдаа саналаа өг, гэхдээ хэн удирдах вэ Эхнийх нь санал хураалтаар? Хэрэв бид удирдагчийн талаар тохиролцож чадахгүй бол яах вэ? Эсвэл тохиролцоонд хүрсэн ч энэ дарга хурал дээр гацах юм уу өвчний чөлөөнд гарвал яах вэ?
Үүнтэй төстэй асуудал нь тархсан компьютерийн сүлжээнд тохиолддог. Нийт оролцогчид эсвэл зангилаа нь хуваалцсан файлыг шинэчлэх эсвэл боловсруулах дарааллаас даалгаврыг устгах ээлж хэнийх вэ гэх мэт шийдвэрийн талаар санал нэгдэх ёстой. Криптовалютын сүлжээнд зангилаа нь зарим тохиолдолд зөрчилддөг хэд хэдэн хувилбараас бүрэн түүхийг нь сонгох шаардлагатай болдог. Энэхүү сүлжээний гэрээ нь зоос (a) хүчинтэй (хуурамч биш) болон (б) өөр газар зарцуулаагүй гэсэн баталгааг хүлээн авагчид өгдөг. Энэ нь шинэ хүлээн авагч нь ижил шалтгаанаар ижил баталгаатай байх тул ирээдүйд зоосыг зарцуулах боломжтой болно.
Түгээмэл тооцоолох сүлжээн дэх аливаа зөвшилцлийн систем нь алдааг тэсвэрлэх ёстой: энэ нь удаан холбоос, хариу өгөхгүй зангилаа, буруу мессежийн дараалал зэрэг алдаанаас үл хамааран тогтвортой үр дүнг гаргах ёстой. Византийн Гэрээний систем нь "Византийн" алдаануудад нэмэлт тэсвэртэй байдаг: алдааны улмаас эсвэл системийг сулруулж эсвэл ямар нэгэн давуу тал олж авах гэсэн санаатайгаар буруу мэдээлэл өгдөг зангилаанууд. "Византийн" алдааг тэсвэрлэх чадвар - бүлгийн зарим гишүүд худал хэлж, шийдвэр гаргах дүрмийг дагаж мөрддөггүй байсан ч бүлгийн шийдвэрт итгэх чадварыг гэнэ. довтолгоог зохицуулах гэж оролдсон хүн. Энтони Стивенс дээр.
Бобоос амттай зайрмаг худалдаж авах, Каролын өрийг төлөх хоёрын аль нэгийг сонгох ёстой крипто зоосны эзэн Алисыг бодоорой. Магадгүй Алис нэг зоосыг хууран мэхлэх замаар хоёуланг нь нэг дор төлөхийг хүсч байгаа байх. Үүнийг хийхийн тулд тэр зоосыг хэзээ ч Каролд төлөөгүй гэж Бобын компьютерт итгүүлэх ёстой бөгөөд Каролын компьютерт зоосыг Бобд хэзээ ч төлөөгүй гэж итгүүлэх ёстой. Византийн хэлэлцээрийн систем нь олонхийн засаглалын хэлбэрийг ашиглан үүнийг бараг боломжгүй болгодог чуулга. Ийм сүлжээний зангилаа нь хангалттай тооны үе тэнгийнхэн буюу чуулга ийм шилжилтийг зөвшөөрч байгааг харах хүртэл түүхийн тодорхой хувилбар руу шилжихээс татгалздаг. Ийм зүйл тохиолдсоны дараа тэд үлдсэн сүлжээний зангилааг өөрсдийн шийдвэртэй санал нийлэхийг шаардах хангалттай том санал хураах блок байгуулах болно. Алис зарим зангилааг өөрийнх нь өмнөөс худал хэлэхийг албадах боловч хэрвээ сүлжээ хангалттай том бол түүний оролдлого нь шударга зангилааны саналд дарагдах болно.
Чуулгад хэдэн зангилаа шаардлагатай вэ? Алдаа, луйвартай тэмцэхийн тулд наад зах нь олонхи, эс тэгвээс мэргэшсэн олонхи. Гэхдээ олонхийг тоолохын тулд нийт оролцогчдын тоог мэдэх хэрэгтэй. Interstellar оффис эсвэл дүүргийн сонгуулийн үеэр эдгээр тоог олоход хялбар байдаг. Гэхдээ хэрэв танай бүлэг нь төвөөс зөвшөөрөл авалгүйгээр зангилаанууд нь хүссэн үедээ орж, гарч чаддаг сул тодорхойлогдсон сүлжээ юм бол танд хэрэгтэй. холбооны Урьдчилан тогтоосон зангилааны жагсаалтаас бус харин динамикаар, өгөгдсөн цэг дэх зангилааны байнга өөрчлөгддөг, зайлшгүй бүрэн бус агшин зуурын зургаас тодорхойлох чадвартай Византийн гэрээний систем.
Өргөн уудам сүлжээн дэх ганц зангилааны үүднээс чуулга үүсгэх боломжгүй мэт санагдаж болох ч боломжтой. Ийм ирц бүрдсэн нь төвлөрсөн бус санал хураалтын үр дүнг баталгаажуулж ч чадна. гэж нэрлэгддэг процедурыг ашиглан үүнийг хэрхэн хийхийг SCP цагаан цаасан дээр харуулав холбооны саналаар.
Тэвчээргүй хүмүүсийн хувьд
Өгүүллийн үлдсэн хэсэгт нэгдсэн санал хураалт болон Оддын зөвшилцлийн протоколыг илүү дэлгэрэнгүй тайлбарласан болно. Хэрэв та нарийн ширийнийг сонирхохгүй бол үйл явцын ерөнхий тоймыг эндээс үзнэ үү.
- Зангилаанууд "нэр дэвшүүлэгчид" дээр холбооны санал хураалтыг явуулдаг. Холбооны санал хураалт гэдэг нь:
- Зангилаа нь зарим мэдэгдэлд санал өгдөг, жишээлбэл, "Би V-ийн утгыг санал болгож байна";
- Зангилаа нь "хүлээн авах" боломжтой нэгийг олох хүртэл үе тэнгийнхний дуу хоолойг сонсдог;
- Зангилаа нь энэ батламжийн хувьд "чуулга" хайж байна. Чуулга нь нэр дэвшигчийг "баталгаажуулдаг".
- Зангилаа нэг буюу хэд хэдэн нэр дэвшигчийг баталгаажуулж чадвал хэд хэдэн үе шаттайгаар нэгдсэн санал хураалтаар "саналын хуудас"-ыг "бэлтгэх" оролдлого хийдэг.
- Зангилаа нь саналын хуудас бэлэн болсон эсэхийг шалгах боломжтой болвол илүү олон үе шаттайгаар нэгдсэн санал хураалт явуулахыг оролддог.
- Зангилаа саналын хуудсыг баталгаажуулсны дараа саналын хуудасны үнэ цэнийг зөвшилцлийн үр дүнд ашиглах замаар "гадна" болгож чадна.
Эдгээр алхмууд нь нэгдсэн санал хураалтын олон үе шатыг хамардаг бөгөөд энэ нь хамтдаа нэг SCP-ийг бүрдүүлдэг. Алхам бүрт юу болж байгааг нарийвчлан авч үзье.
Холбооны санал хураалт
Холбооны санал хураалт нь сүлжээний санал дээр тохиролцож чадах эсэхийг тодорхойлох журам юм. Санал хураалтын шатанд зангилаа бүр боломжит олон утгын аль нэгийг сонгох ёстой. Сүлжээний бусад зангилаа өөр үр дүнг сонгохгүй гэдэгт итгэлтэй биш л бол үүнийг хийж чадахгүй. Үүнийг баталгаажуулахын тулд зангилаанууд олон тооны мессежийг нааш цааш солилцдог бөгөөд ингэснээр хүн бүр батлагдсан, тэр чуулга зангилаа Явж байна адилхан решение. Энэ хэсгийн үлдсэн хэсэг нь энэ өгүүлбэр дэх нэр томъёо, бүх процедур хэрхэн явагддагийг тайлбарладаг.
Чуулга болон чуулгын зүсмэлүүд
Чуулганы тодорхойлоос эхэлье. Дээр дурдсанчлан, динамик гишүүнчлэл бүхий төвлөрсөн бус сүлжээнд зангилааны тоог урьдчилан мэдэх боломжгүй, тиймээс олонхи нь хэд байх ёстойг мэдэх боломжгүй юм. Холбооны санал хураалт нь шинэ санаа гаргах замаар энэ асуудлыг шийддэг чуулга тасарсан (чуулгын зүсмэлүүд): Санал хураалтын төлөвийн мэдээллийг сүлжээний бусад хэсэгт дамжуулахын тулд зангилаа итгэдэг үе тэнгийн гишүүдийн жижиг багц. Зангилаа бүр өөрийн чуулгын зүсмэлийг тодорхойлдог (түүний де факто гишүүн болдог).
Чуулга бүрэлдэх нь чуулгыг таслахаас эхэлдэг. Зангилаа бүрийн хувьд түүний зүссэн зангилаанууд нэмэгддэг. Дараа нь зүсмэлийн нэр томъёо нэмэгдэнэ эдгээр зангилаа гэх мэт. Үргэлжлүүлэн үргэлжлүүлэх тусам зүсмэл дотор аль хэдийн орсон байгаа тул нэмж чадахгүй цэгүүд нэмэгдсээр байна. Нэмэх шинэ зангилаа байхгүй үед процесс зогсдог: бид эхний зангилааны чуулгын зүсмэлийг "шилжилтийн хаалт"-аар бүрдүүлсэн.
Өгөгдсөн зангилаанаас чуулга олохын тулд...
... түүний зүсмэлийн гишүүдийг нэмэх...
... дараа нь бид эдгээр зангилааны зүсмэл гишүүдийг нэмнэ.
Бид нэмэх зангилаа үлдэхгүй болтол үргэлжлүүлнэ.
Нэмэх зангилаа үлдсэнгүй. Энэ бол чуулга юм.
Үнэн хэрэгтээ, зангилаа бүр нэгээс олон зүсмэлээр гарч ирж болно. Чуулга үүсгэхийн тулд зөвхөн нэг хэсгийг сонгоод гишүүдийг нэмнэ үү; дараа нь гишүүдийн аль нэг хэсгийг сонгоод гишүүд нэмнэ энэ нь зүсэх гэх мэт. Энэ нь зангилаа бүр олон боломжит чуулгын гишүүн гэсэн үг юм.
Алхам бүрт зөвхөн нэг чуулгын хэсгийг сонго.
Нэг байж болох чуулга. Эсвэл өөр хувилбар ...
...бусад зүсмэлүүдийг сонгох...
…(боломжтой үед)…
... өөр чуулга үүсгэдэг.
Зангилаа нь бусад зангилаа аль зүсмэлүүд дотор байгааг яаж мэдэх вэ? Бусад зангилааны талаархи бусад мэдээллийн нэгэн адил: зангилаа бүр санал өгөх төлөв өөрчлөгдөхөд сүлжээнд цацдаг дамжуулалтаас. Нэвтрүүлэг бүр нь илгээж буй зангилааны зүсмэлүүдийн талаарх мэдээллийг агуулдаг. SCP цагаан цаас нь харилцааны механизмыг заагаагүй болно. Хэрэгжилтийг ихэвчлэн ашигладаг сүлжээгээр баталгаатай мессеж дамжуулах зориулалттай.
Холбооны бус Византийн гэрээний тогтолцоонд чуулга нь бүх зангилааны дийлэнх нь гэж тодорхойлогддог гэдгийг санаарай. Византийн хэлэлцээрийн систем нь хэд хэдэн шударга бус зангилааг систем тэсвэрлэж чадах вэ гэсэн асуултын үүднээс боловсруулсан болно. f бүтэлгүйтлийг даван туулахад зориулагдсан N зангилааны системд зангилаа нь N−f үе тэнгийнхний санал хүсэлтийг хүлээн авснаар ахиц дэвшил гаргах боломжтой байх ёстой, учир нь тэдгээрийн f нь унтарсан байж болно. Гэхдээ N−f үе тэнгийнхнээс хариу хүлээн авснаар бид бүх f үе тэнгийнхэн (зангилаа нь хариу аваагүй) үнэнч шударга гэж үзэж болно. Тиймээс N−f үе тэнгийнхний (хариу хүлээн авсан) f нь хортой юм. Зангилаанууд ижил зөвшилцөлд хүрэхийн тулд үлдсэн зангилааны дийлэнх нь шударга байх ёстой, өөрөөр хэлбэл N−f нь 2f эсвэл N > 3f-ээс их байх шаардлагатай. Иймээс ихэвчлэн f бүтэлгүйтлийг даван туулахад зориулагдсан систем нь нийт N=3f+1 зангилаа, 2f+1 чуулгын хэмжээтэй байх болно. Санал чуулгын босгыг давсны дараа бусад сүлжээнийхэн өрсөлдөгч саналууд амжилтгүй болно гэдэгт итгэлтэй байна. Сүлжээ үр дүндээ ингэж нийлдэг.
Гэхдээ холбооны Византийн гэрээний тогтолцоонд олонхи байх боломжгүй (учир нь сүлжээний нийт хэмжээг хэн ч мэдэхгүй) төдийгүй олонхи гэдэг ойлголт огт хэрэггүй юм! Хэрэв системийн гишүүнчлэл нээлттэй бол хэн нэгэн Sybil халдлагыг хийснээр олонхи болж чадна: хэд хэдэн зангилаагаар сүлжээнд дахин дахин нэгдэх. Тэгэхээр яагаад шилжилтийн зүсмэлийн хаалтыг нэрлэж болох вэ? чуулга, мөн энэ нь өрсөлдөгч саналуудыг хэрхэн дарах боломжтой вэ?
Техникийн хувьд ямар ч боломжгүй! Хоёр гурвалсан бие биенийхээ чуулгын зүсмэлүүдээр тусгаарлагдсан зургаан зангилаатай сүлжээг төсөөлөөд үз дээ. Эхний дэд бүлэг нь хоёр дахь нь хэзээ ч сонсохгүй шийдвэр гаргаж болно, эсвэл эсрэгээр. Энэ сүлжээний зөвшилцөлд хүрэх арга байхгүй (санамсаргүй тохиолдлоос бусад).
Тиймээс SCP нь нэгдсэн санал хураалтад (мөн нийтлэлийн чухал теоремуудыг хэрэгжүүлэхийн тулд) сүлжээ нь нэртэй өмчтэй байхыг шаарддаг. чуулгын уулзвар. Энэ өмчтэй сүлжээнд барьж болох аливаа хоёр чуулга дор хаяж нэг зангилаанд үргэлж давхцдаг. Сүлжээнд давамгайлж буй мэдрэмжийг тодорхойлохын тулд энэ нь олонхи байхтай адил сайн хэрэг юм. Зөн совингийн хувьд энэ нь хэрэв аль ч чуулга Х мэдэгдлийг зөвшөөрвөл өөр ямар ч чуулга хэзээ ч өөр зүйлтэй санал нийлэхгүй гэсэн үг, учир нь энэ нь X-ийн төлөө саналаа өгсөн эхний чуулгын зарим зангилааг заавал оруулах болно.
Сүлжээнд чуулгын уулзвар байгаа бол...
... тэгвэл та хоёр чуулга байгуулж болно ...
... үргэлж огтлолцох болно.
(Мэдээжийн хэрэг, давхцаж буй зангилаанууд нь Византийн хэв маягтай эсвэл өөр муу байж болно. Энэ тохиолдолд чуулгын уулзвар нь сүлжээнд огтхон ч тус болохгүй. Энэ шалтгааны улмаас SCP цагаан цаасан дээрх олон үр дүн нь сүлжээний чуулгын огтлолцолд үлдсэн зүйл гэх мэт тодорхой таамаглалууд муу зангилааг арилгасны дараа ч гэсэн. Энгийн байхын тулд эдгээр таамаглалыг орхиё далд Нийтлэлийн үлдсэн хэсэгт).
Бие даасан зангилааны сүлжээнд чуулгын найдвартай хөндлөн гарах боломжтой гэж хүлээх нь үндэслэлгүй мэт санагдаж магадгүй юм. Гэхдээ ийм байдалд хүрсэн хоёр шалтгаан бий.
Эхний шалтгаан нь интернет өөрөө оршин тогтнох явдал юм. Интернэт бол огтлолцсон чуулга бүхий бие даасан зангилааны сүлжээний төгс жишээ юм. Интернэт дэх ихэнх зангилаанууд нь зөвхөн цөөн хэдэн локал зангилаатай холбогддог боловч эдгээр жижиг багцууд нь хангалттай давхцаж байгаа тул зангилаа бүрийг зарим маршрутын дагуу бусад зангилаа бүрээс авах боломжтой.
Хоёрдахь шалтгаан нь Оддын төлбөрийн сүлжээнд зориулагдсан (SCP-ийн хамгийн түгээмэл хэрэглээ). Stellar сүлжээн дэх хөрөнгө бүр үнэт цаас гаргагчтай бөгөөд Stellar-ийн удирдамжийн дагуу эргүүлэн авах хүсэлтийг боловсруулахын тулд гаргагч бүр сүлжээн дэх нэг буюу хэд хэдэн зангилааг тодорхойлохыг шаарддаг. Эдгээр зангилаануудыг сонирхож буй хөрөнгө тус бүрийн хувьд шууд болон шууд бус байдлаар оруулах нь таны ашиг сонирхолд нийцнэ. Өгөгдсөн хөрөнгийг сонирхож буй бүх зангилааны чуулга нь хамгийн багадаа эдгээр эргүүлэн авах цэгүүдэд давхцах болно. Олон хөрөнгийг сонирхож буй зангилаанууд нь тухайн үнэт цаас гаргагчийн эргүүлэн авах бүх цэгүүдийг өөрсдийн чуулгын хэсгүүдэд багтаах бөгөөд тэд бүх хөрөнгийг нэгтгэхийг эрэлхийлэх болно. Үүнээс гадна, сүлжээнд байгаа бусадтай ийм байдлаар холбогдоогүй аливаа хөрөнгө, мөн холбогдож болохгүй - энэ нь энэ сүлжээнд чуулгын давхцал байхгүй байхаар хийгдсэн (жишээлбэл, долларын бүсийн банкууд заримдаа евро бүсийн банкууд болон песо бүсийн банкуудтай арилжаа хийхийг хүсдэг тул тэд нэг сүлжээнд байдаг, гэхдээ аль нь ч байдаггүй. Тэдний зарим нь бейсболын карт зардаг хүүхдүүдийн тусдаа сүлжээнд санаа тавьдаг).
Мэдээжийн хэрэг, хүлээж байна чуулгын гарц биш баталгаа. Византийн бусад гэрээний системүүд чуулгын баталгаатай холбоотой байдаг. SCP-ийн чухал шинэлэг зүйл бол зөвшилцлийн алгоритмаас чуулга үүсгэх хариуцлагыг арилгаж, хэрэглээний түвшинд хүргэж байгаа явдал юм. Тиймээс, нэгдсэн санал хураалт нь аливаа асуудлаар санал өгөхөд хангалттай ерөнхий боловч түүний найдвартай байдал нь эдгээр утгын өргөн утгаас ихээхэн хамаардаг. Зарим таамаглалтай хэрэглээ нь бусадтай адил сайн холбогдсон сүлжээг бий болгоход тустай байж болохгүй.
Санал өгөх, хүлээн зөвшөөрөх, баталгаажуулах
Холбооны санал хураалтын шатанд зангилаа V утгын төлөө саналаа өгч эхэлнэ. Энэ нь сүлжээнд "Би N зангилаа, миний чуулгын хэсэг Q, би V-д санал өгч байна" гэсэн мессежийг сүлжээнд цацна гэсэн үг. Зангилаа ийм байдлаар санал өгөхөд энэ нь хэзээ ч V-ийн эсрэг санал өгөөгүй, хэзээ ч болохгүй гэж амлаж байна.
Үе тэнгийн нэвтрүүлэгт зангилаа бүр бусад нь хэрхэн санал өгөхийг хардаг. Зангилаа эдгээр мессежийг хангалттай цуглуулсны дараа чуулгын зүсмэлүүдийг хянаж, чуулга олохыг оролдож болно. Хэрэв тэр V-д санал өгөх үе тэнгийнхний чуулгыг харвал тэр үргэлжлүүлж болно үрчлэлт V гэж хэлээд сүлжээндээ "Би N зангилаа, миний чуулгын зүсмэлүүд Q, би V-г хүлээн зөвшөөрч байна." Хүлээн авах нь энгийн санал хураалтаас илүү хүчтэй баталгаа болдог. Зангилаа V-д санал өгөхөд бусад сонголтуудад санал өгөх боломжгүй. Гэхдээ хэрэв зангилаа V-г хүлээн авбал Сүлжээний ямар ч зангилаа өөр сонголтыг хэзээ ч хүлээн зөвшөөрөхгүй (SCP цагаан цаасны 8-р теорем үүнийг баталж байна).
Мэдээжийн хэрэг, V-тэй санал нийлэх зангилааны чуулга нэн даруй гарахгүй байх магадлал өндөр байна. Бусад зангилаанууд бусад утгын төлөө саналаа өгч болно. Гэхдээ зангилаа энгийн санал хураалтаас хүлээн зөвшөөрөх хүртэл шилжих өөр нэг арга бий. N нь W-ийн төлөө саналаа өгөөгүй байсан ч, тэр ч байтугай ирц бүрдээгүй байсан ч гэсэн өөр утгыг хүлээн зөвшөөрч магадгүй юм. Саналаа өөрчлөхөөр шийдэхийн тулд харна уу блоклох багц W-г хүлээн зөвшөөрсөн зангилаа блок өөр ямар ч утга. Хэрэв ийм олонлогийн бүх зангилаа W-г хүлээн авбал (8-р теоремоор) өөр утгатай чуулга үүсгэх боломжгүй тул N-д W-г хүлээн зөвшөөрөх нь бас аюулгүй.
Гурван чуулгын зүсмэлүүдтэй N зангилаа.
BDF нь N-д зориулсан блоклох багц юм: N-ийн зүсмэл бүрээс нэг зангилаа багтана.
BE нь мөн N-д зориулсан блоклох багц юм, учир нь E нь N-ийн хоёр зүсмэл дээр гарч ирдэг.
Гэхдээ блоклох багц нь чуулга биш юм. Хэрэв N-ийн зүсмэл бүрийн нэг зангилааг хакердахад л хангалттай байсан бол N зангилааг хүссэн утгыг нь хүлээн зөвшөөрөх нь хэтэрхий амархан байх болно. Тиймээс утгыг хүлээн авснаар санал хураалт дуусахгүй. Үүний оронд N нь утгыг баталгаажуулах ёстой, өөрөөр хэлбэл үүнийг хүлээн авах зангилааны чуулгыг харах ёстой. Хэрэв энэ нь тийм ч хол явах юм бол SCP-ийн танилцуулгад нотлогдож байгаачлан (Теорем 11-д) сүлжээний бусад хэсэг нь эцэст нь ижил утгыг баталгаажуулах тул N нь үр дүнд нь тодорхой утгаар нэгдсэн санал хураалтыг дуусгана.
Холбооны санал хураалт.
Санал хураах, хүлээн зөвшөөрөх, баталгаажуулах үйл явц нь нэгдсэн санал хураалтыг нэг удаа явуулдаг. Оддын зөвшилцлийн протокол нь бүрэн зөвшилцлийн системийг бий болгохын тулд эдгээр олон тойргийг нэгтгэдэг.
Оддын зөвшилцлийн протокол
Зөвшилцлийн системийн хамгийн чухал хоёр шинж чанар нь - аюулгүй байдал и амьд үлдэх чадвар. Зөвшилцлийн алгоритм нь өөр өөр оролцогчдод хэзээ ч өөр үр дүнг өгч чадахгүй бол "аюулгүй" болно (Бобын түүхийн хуулбар Каролтой хэзээ ч зөрчилдөхгүй). "Амьдрах чадвар" гэдэг нь алгоритм үргэлж үр дүнг гаргах болно, өөрөөр хэлбэл гацахгүй гэсэн үг юм.
Холбооны санал хураах журмыг тодорхойлсон аюулгүй Хэрэв зангилаа V-ийн утгыг баталгаажуулвал өөр ямар ч зангилаа нөгөө утгыг баталгаажуулахгүй гэсэн утгаараа. Гэхдээ "өөр утгыг батлахгүй" гэдэг нь ямар нэг зүйлийг заавал баталгаажуулна гэсэн үг биш юм. Оролцогчид маш олон янзын үнэлэмж дээр санал өгөх боломжтой тул юу ч хүлээн авах босго хэмжээнд хүрэхгүй. Энэ нь холбооны санал хураалтад байхгүй гэсэн үг юм амьд үлдэх чадвар.
Оддын зөвшилцлийн протокол нь аюулгүй байдал, оршин тогтнох чадварыг баталгаажуулах үүднээс нэгдсэн санал хураалтыг ашигладаг. (SCP-ийн аюулгүй байдал, оршин тогтнох баталгаа нь онолын хязгаартай байдаг. Энэхүү загвар нь маш хүчтэй аюулгүй байдлын баталгааг сонгож, амьд үлдэх чадварыг бага зэрэг бууруулж байгаа боловч хангалттай хугацаа өгвөл зөвшилцөлд хүрэх магадлал өндөр байна.) Товчхондоо, эдгээрийн аль нэг нь доор тайлбарласан SCP-ийн санал хураалтын бүх үе шатыг давах хүртэл олон тооны нэгдмэл санал хураалттай байх санаа юм.
SCP-ийн зөвшилцлийг эрэлхийлж буй үнэ цэнэ нь гүйлгээний түүх, өдрийн хоолны захиалга эсвэл өөр зүйл байж болох ч эдгээр нь хүлээн зөвшөөрөгдсөн эсвэл батлагдсан үнэ цэнэ биш гэдгийг анхаарах нь чухал юм. Үүний оронд холбооны санал хураалт нь дагуу явагддаг эдгээр үнэт зүйлсийн талаархи мэдэгдэл.
Холбооны сонгуулийн эхний шатны санал хураалт энэ өдөр болно нэр дэвшүүлэх үе шат (нэр дэвшүүлэх үе шат), "Би V-г дэвшүүлж байна" гэх мэт олон янзын V-ийн утгын хувьд байж болох юм. Нэр дэвшүүлэх зорилго нь хүлээн зөвшөөрөх, баталгаажуулах замаар дамждаг нэг буюу хэд хэдэн мэдэгдлийг олох явдал юм.
Баталгаажуулж болох нэр дэвшигчдийг олсны дараа SCP санал хураалтын үе шатанд шилждэг бөгөөд зорилго нь тодорхой нэр дэвшигчийг олох явдал юм. эмхэтгэл (өөрөөр хэлбэл, санал болгож буй үнэ цэнийн чингэлэг) болон зарлах боломжтой чуулга хийх үүний төлөө (амлах). Хэрэв чуулга саналаа өгсөн бол түүний утгыг зөвшилцсөн гэж үзнэ. Гэхдээ зангилаа саналын хуудсанд санал өгөхөөс өмнө эхлээд баталгаажуулах ёстой цуцлах бага тоолууртай бүх саналын хуудас. Саналын хуудсыг хүчингүй болгож болох нэгийг олохын тулд эдгээр алхмууд нь олон саналын хуудасны нэхэмжлэлийн талаар нэгдсэн санал хураалтыг олон удаа явуулдаг.
Дараах хэсгүүдэд нэр дэвшүүлэх болон санал хураалтыг илүү дэлгэрэнгүй тайлбарласан болно.
Нэр дэвших
Нэр дэвшүүлэх үе шатны эхэнд зангилаа бүр аяндаа V-ийн утгыг сонгож, "Би V-г дэвшүүлж байна" гэсэн мэдэгдлийн төлөө саналаа өгөх боломжтой. Энэ үе шатны зорилго нь холбооны санал хураалтаар тодорхой үнэ цэнийн нэр дэвшүүлэхийг баталгаажуулах явдал юм.
Магадгүй хангалттай олон тооны зангилаанууд хангалттай өөр саналууд дээр саналаа өгч, ямар ч нэр дэвшүүлэх нь хүлээн авах босго хэмжээнд хүрч чадахгүй. Тиймээс зангилаанууд өөрсдийн нэр дэвшүүлэх саналаа цацахаас гадна үе тэнгийнхнийхээ дэвшүүлсэн саналыг “тусгадаг”. Цуурай нь хэрэв зангилаа V нэр дэвшүүлэхэд санал өгсөн ч хөршөөсөө W-д нэр дэвшүүлэх талаар санал өгөх мессежийг харвал тэр одоо V болон W-д хоёуланд нь санал өгнө гэсэн үг юм. өөр өөр нэр дэвшигчид.SCP нь эдгээр саналуудыг зохицуулах механизмыг агуулдаг.Товчхондоо, зангилааны үүднээс үе тэнгийнхний "тэргүүлэх"-ийг тодорхойлох томьёо байдаг бөгөөд зөвхөн өндөр ач холбогдол бүхий зангилааны саналыг тусгадаг.Нэр дэвшүүлэх тусам урт байх болно. авах тусам босго бага байх тул зангилаа нь саналыг тусгах үе тэнгийнхний багцыг өргөжүүлнэ. Тэргүүлэх томьёо нь түүний оролтын нэг болох үүрний дугаарыг агуулдаг тул нэг слотын өндөр ач холбогдол бүхий үе тэнгийнх нь бага ач холбогдол бүхий үе тэнгийнхэн байж болно. өөр, мөн эсрэгээр).
Үзэл баримтлалын хувьд нэр дэвшүүлэх нь зэрэгцээ, V ба W хоёулаа холбооны тусдаа саналууд бөгөөд тус бүр нь хүлээн зөвшөөрөх эсвэл баталгаажуулах чадвартай. Практикт SCP протоколын мессежүүд нь эдгээр хувийн саналыг хамтад нь багцалдаг.
Хэдийгээр V-г дэвшүүлэхийн төлөө санал өгөх нь хэзээ ч V-г дэвшүүлэхийн эсрэг санал өгөхгүй гэсэн амлалт боловч энэ нь хэрэглээний түвшинд - энэ тохиолдолд SCP - "эсрэг" гэж юу гэсэн үг болохыг тодорхойлдог. SCP нь "Би Х-г дэвшүүлж байна" гэсэн саналтай зөрчилдсөн мэдэгдлийг олж харахгүй байна, өөрөөр хэлбэл "Би Х-г дэвшүүлэхийг эсэргүүцэж байна" гэсэн мессеж байхгүй тул зангилаа ямар ч утгыг нэр дэвшүүлэх санал өгөх боломжтой. Эдгээр номинацийн ихэнх нь хаашаа ч гарахгүй, гэхдээ эцэст нь зангилаа нэг буюу хэд хэдэн утгыг хүлээн авах эсвэл баталгаажуулах боломжтой болно. Нэр дэвшигч батлагдмагц тэр болно нэр дэвшигч.
Холбооны санал хураалтыг ашиглан SCP нэр дэвшүүлэх. Үе тэнгийнхэн дэвшүүлсэн, зангилаагаар "туссан" олон "В" утгууд байж болно.
Нэр дэвшсэнээр олон нэр дэвшигч батлагдаж болно. Тиймээс SCP нь нэр дэвшигчдийг нэг болгон нэгтгэх зарим аргыг хангахын тулд хэрэглээний давхарга шаарддаг нийлмэл (нийлмэл). Холбох арга нь юу ч байж болно. Хамгийн гол нь хэрэв энэ арга нь тодорхойлогддог бол зангилаа бүр ижил нэр дэвшигчдийг нэгтгэх болно. Үдийн цайны санал хураалтын системд "нэгдлээ" гэдэг нь хоёр нэр дэвшигчийн аль нэгийг нь татгалзсан гэсэн үг юм. (Гэхдээ тодорхойлогч аргаар: зангилаа бүр дахин тохируулахын тулд ижил утгыг сонгох ёстой. Жишээ нь, цагаан толгойн үсгийн дарааллаар өмнөх сонголт). Гүйлгээний түүхэнд санал хураалт явуулдаг Stellar төлбөрийн сүлжээнд санал болгож буй хоёр нэр дэвшигчийг нэгтгэх нь тэдгээрийн агуулагдаж буй гүйлгээ болон тэдгээрийн хамгийн сүүлийн үеийн хоёр цагийн тэмдгийг нэгтгэх явдал юм.
SCP-ийн танилцуулга нь (Теорем 12) өргөтгөлийн үе шат дуусахад сүлжээ эцэстээ нэг нийлмэл болж нийлдэг гэдгийг нотолж байна. Гэхдээ нэг асуудал бий: нэгдсэн санал хураалт нь асинхрон протокол юм (SCP гэх мэт). Өөрөөр хэлбэл, зангилаанууд нь цаг хугацаагаар зохицуулагддаггүй, зөвхөн тэдний илгээсэн мессежээр зохицуулагддаг. Зангилааны үүднээс авч үзвэл хэзээ гэдэг нь тодорхойгүй байна дууссан сунгах үе шат. Хэдийгээр бүх зангилаанууд эцэст нь нэг нийлмэл дээр ирэх боловч замдаа өөр өөр замыг туулж, замдаа өөр өөр нийлмэл нэр дэвшигчдийг бий болгож, аль нь эцсийнх болохыг хэзээ ч хэлж чадахгүй.
Гэхдээ хэвийн. Нэр дэвших нь зүгээр л бэлтгэл. Гол нь зөвшилцөлд хүрэхийн тулд нэр дэвшигчдийн тоог хязгаарлах нь үйл явцад тохиолддог сонгуульд нэр дэвшиж байна (санал хураалт).
Гүйж байна
Мэдээллийн хуудас бол хос юм , энд тоолуур нь 1-ээс эхэлсэн бүхэл тоо, утга нь нэр дэвшүүлэх шатнаас нэр дэвшигч юм. Энэ нь зангилааны өөрийн нэр дэвшигч эсвэл хөрш зэргэлдээх зангилааны нэр дэвшигч байж болно. Ойролцоогоор саналын хуудас гэдэг нь саналын хуудасны мэдэгдэлд олон тооны холбооны санал авах замаар зарим нэг нэр дэвшигчийн талаар зөвшилцөлд хүрэхийг сүлжээг удаа дараа оролдох явдал юм. Саналын хуудасны тоолуур хийсэн оролдлогыг бүртгэж, илүү өндөр тоо бүхий саналын хуудас нь бага тоотой саналын хуудсыг давуулах болно. Хэрэв мэдээллийн товхимол бол гацаж, шинэ санал хураалт эхэлнэ, одоо саналын хуудас дээр .
Энэ нь ялгах нь чухал юм утга (жишээлбэл, үдийн хоолны захиалга ямар байх ёстой вэ: пицца эсвэл салат), мэдээллийн товхимол (эсрэг үнийн хос) ба мэдэгдэл саналын хуудасны тухай. SCP-ийн тойрогт холбооны санал хураалтын хэд хэдэн үе шат, тухайлбал дараах мэдэгдлүүд багтана.
- "Би санал өгөх В-д бэлэн байна" болон
- "Би санал хураалт явуулах В санал хураалтыг зарлаж байна"
Тухайн зангилааны үүднээс авч үзвэл, "Би саналын хуудас өгч байна" гэсэн мэдэгдлийг баталгаажуулах (өөрөөр хэлбэл, хүлээн зөвшөөрсөн чуулгыг олох) саналын хуудас B-г олох үед зөвшилцөлд хүрнэ. Энэ мөчөөс эхлэн B-д заасан утгын дагуу ажиллах нь аюулгүй юм - жишээлбэл, үдийн хоолонд энэ захиалгыг байрлуулах. гэж нэрлэдэг гадагшлуулах утга. Саналын хуудсыг хүлээн зөвшөөрсний дараа зангилаа өөр ямар ч зангилаа ижил утгыг гадагш гаргасан эсвэл ирээдүйд үүнийг хийх болно гэдэгт итгэлтэй байж болно.
Хэдийгээр олон төрлийн санал хураалт нь олон төрлийн саналын хуудасны нэхэмжлэлийн дагуу явагддаг боловч мессеж бүр нь хэд хэдэн саналын хуудсыг багтаасан байдаг тул тэд тийм ч олон мессеж солилцдоггүй. Нэг мессеж нь нэг дор олон тооны саналын төлөвийг сурталчлах болно, жишээлбэл: "Би саналын хуудсыг хүлээн зөвшөөрч байна. өмнө "
"Бэлтгэлтэй" болон "Үүрэг гүйцэтгэх" гэсэн нэр томъёо нь юу гэсэн үг вэ?
Зангилаа нь бусад зангилаа өөр өөр утгатай саналын хуудас өгөхгүй гэдэгт итгэлтэй байгаа тохиолдолд санал хураалтад оролцоно. Үүнийг итгүүлэх нь өргөдлийг бэлтгэх зорилго юм. "Би В саналын хуудас өгөхөд бэлэн" гэсэн санал нь хэзээ ч В-ээс бага, өөрөөр хэлбэл бага тооллогоор санал өгөхгүй гэсэн амлалт юм (SCP нь саналын хуудасны утгыг тодорхой дарааллаар оруулахыг шаарддаг. Тиймээс мэдээллийн товхимол бага , хэрэв N1
“Би санал өгөх В-д бэлэн байна” гэдэг нь яагаад “Б-ээс жижиг саналын хуудас өгөхгүй гэж амлаж байна” гэсэн үг вэ? Учир нь SCP нь abort гэдэг нь commit-ийн эсрэгээр тодорхойлогддог. Саналын хуудас бэлтгэх санал хураалт нь бусад зарим саналын хуудсыг хүчингүй болгох санал хураалтыг хамардаг бөгөөд бидний өмнө дурдсанчлан нэг зүйлийн төлөө санал өгөх нь хэзээ ч эсрэг санал өгөхгүй гэсэн амлалт юм.
Зангилаа нь амлалтаа дамжуулахын өмнө эхлээд бэлтгэсэн гэдгээ баталгаажуулах мэдээллийн хуудсыг олох ёстой. Өөрөөр хэлбэл, ирцийг хүлээн зөвшөөрсөн нэгийг олох хүртлээ олон төрлийн саналын хуудсаар “Би санал өгөхөд бэлэн байна” гэсэн сэдвээр нэгдсэн санал хураалт явуулдаг.
Санал хураалтад бэлтгэхийн тулд саналын хуудас хаанаас ирдэг вэ? Эхлээд зангилаа <1,C>-д санал өгөх бэлтгэлийг цацдаг бөгөөд С нь нэр дэвшүүлэх шатанд гаргасан нийлмэл нэр дэвшигч юм. Гэсэн хэдий ч санал хураалтад бэлтгэж эхэлсэн ч нэр дэвшүүлэх нь нэмэлт нэр дэвшигчид шинэ саналын хуудас болж магадгүй юм. Үүний зэрэгцээ, үе тэнгийнхэн өөр өөр нэр дэвшигчтэй байж болох бөгөөд тэд "Би B2 саналын хуудас өгөхөд бэлэн байна" гэж хүлээн зөвшөөрсөн блоклох багц үүсгэж болох бөгөөд энэ нь зангилааг хүлээн зөвшөөрөхөд итгүүлэх болно. Эцэст нь, хэрэв одоогийн саналын хуудас гацсан бол илүү өндөр тоо бүхий шинэ саналын хуудсууд дээр нэгдсэн санал хураалтын шинэ үе шатуудыг бий болгодог хугацаа дуусах механизм байдаг.
Зангилаа нь бэлтгэсэн гэж батлах боломжтой саналын хуудас Б-г олмогцоо "Саналын хуудсыг B-г өг" гэсэн шинэ мессежийг цацдаг. Энэ санал нь зангилаа хэзээ ч B бууж өгөхгүй гэдгийг үе тэнгийнхэн хэлж байна. Үнэн хэрэгтээ, хэрэв B саналын хуудас , дараа нь “Саналын хуудас өгнө үү " гэдэг нь саналын хуудас бүрийн бэлэн байдлын төлөө санал өгөх ямар ч болзолгүй зөвшөөрлийг хэлнэ <∞, s> руу. Энэхүү нэмэлт үнэ цэнэ нь бусад үе тэнгийнхэндээ протоколын эхний шатанд байгаа бол гүйцэтгэгчийг гүйцэхэд тусалдаг.
Энэ үе шатанд эдгээр нь асинхрон протоколууд гэдгийг дахин онцлон тэмдэглэх нь зүйтэй. Нэг зангилаа нь амлалтад эерэг санал илгээдэг учраас түүний үе тэнгийнхэн ч гэсэн хариу өгдөг гэсэн үг биш юм. Тэдний зарим нь санал хураалтад бэлтгэж байгаа мэдэгдлүүдийн талаар саналаа өгсөөр байгаа бол зарим нь утгыг аль хэдийн гадагшлуулсан байж магадгүй юм. SCP нь үе тэнгийн мессежийн төрөл бүрийг үе шатаас нь үл хамааран зангилаа хэрхэн боловсруулах ёстойг тайлбарладаг.
Хэрэв мессеж "Би амлалтаа зарлалаа » хүлээн авах эсвэл баталгаажуулах боломжгүй, өөрөөр хэлбэл мессежийг хүлээн авах эсвэл баталгаажуулах магадлал эсвэл - эсвэл ямар ч тохиолдолд C гэсэн утгатай саналын хуудас, өөр аль нь ч биш, учир нь зангилаа хэзээ ч цуцлахгүй гэж амласан. . Зангилаа нь амлалтын төлөө санал өгөх үед энэ нь зөвшилцөл хэр хол явахаас хамааран C эсвэл юу ч биш байх болно. Гэсэн хэдий ч, энэ нь зангилаа C-г гадагшлуулахад хангалттай биш байна C. Зарим Византийн үе тэнгийнхэн (бидний аюулгүй байдлын таамаглалд тулгуурлан чуулгаас бага хувийг бүрдүүлдэг) зангилаа руу худал хэлж болно. Саналын хуудсыг (эсвэл саналын хуудасны хүрээг) хүлээн авч, дараа нь баталгаажуулах нь зангилаанд С-г эцэслэн гадуурхах итгэлийг өгдөг.
Холбооны санал хураалтаар SCP санал хураалт. Үзүүлээгүй: Цаг хэмжигч хэдийд ч унтарч, саналын хуудасны тооллогыг нэмэгдүүлэх боломжтой (мөн нэмэлт нэр дэвшсэн нэр дэвшигчдийн шинэ бүрэлдэхүүнийг гаргаж магадгүй).
Тэгээд бүгд байна! Сүлжээ зөвшилцөлд хүрсэн бол дахин дахин хийхэд бэлэн байна. Stellar төлбөрийн сүлжээнд энэ нь ойролцоогоор 5 секунд тутамд тохиолддог бөгөөд энэ нь SCP-ээр баталгаажсан аюулгүй байдал, амьд үлдэх чадварыг шаарддаг.
SCP олон удаагийн нэгдсэн санал хураалтад тулгуурлан үүнд хүрч чадна. Холбоотой санал хураалт нь чуулгын зүсмэлүүд буюу зангилаа бүр өөрийн (субъектив) чуулгын нэг хэсэг болгон итгэхээр шийдсэн үе тэнгийн гишүүдийн багц гэсэн ойлголтоор боломжтой болсон. Энэ тохиргоо нь нээлттэй гишүүнчлэлтэй, Византийн хууран мэхлэлттэй сүлжээнд ч гэсэн зөвшилцөлд хүрч чадна гэсэн үг юм.
Цаашид унших
- Анхны SCP цагаан цаасыг олж болно болон түүнийг хэрэгжүүлэх техникийн нөхцөлийн төсөл.
- SCP протоколын анхны зохиогч Дэвид Мазиер үүнийг хялбаршуулсан (гэхдээ техникийн) байдлаар тайлбарлав. .
- Энэ нийтлэлээс "уул уурхай" эсвэл "ажлын нотолгоо" гэсэн нэр томъёо олдоогүйд та гайхсан байх. SCP эдгээр аргуудыг ашигладаггүй, гэхдээ бусад зөвшилцлийн алгоритмууд ашигладаг. Зейн Уизерспун хүртээмжтэй бичжээ .
- SCP-ийн нэг бүтэн тойрогт зөвшилцөлд хүрдэг энгийн сүлжээ.
- SCP-ийн хэрэгжилтийг сонирхож буй уншигчдын хувьд: үзнэ үү , Оддын төлбөрийн сүлжээ ашигладаг, эсвэл , үүнийг би SCP-ийг илүү сайн ойлгохын тулд бичсэн.
Эх сурвалж: www.habr.com