Աստղային կոնսենսուսի արձանագրությունն առաջին անգամ նկարագրվել է Դեյվիդ Մազիերը 2015թ. Սա «դաշնային բյուզանդական համաձայնությունների համակարգ» է, որը թույլ է տալիս ապակենտրոնացված, առանց առաջնորդի հաշվողական ցանցերին արդյունավետորեն համաձայնության գալ որոշման վերաբերյալ: Stellar վճարային ցանցը օգտագործում է Stellar Consensus Protocol-ը (SCP)՝ հետևողական գործարքների պատմություն պահպանելու համար, որը տեսանելի է բոլոր մասնակիցներին:
Կոնսենսուսային արձանագրությունները համարվում են դժվար հասկանալի: SCP-ն ավելի պարզ է, քան նրանցից շատերը, բայց դեռևս կիսում է այս հեղինակությունը, մասամբ այն սխալ մտքի պատճառով, որ «ֆեդերատիվ քվեարկությունը», որը գիտական հոդվածի առաջին կեսի թեման է, SCP է: Բայց դա ճիշտ չէ։ Սա պարզապես կարևոր շինանյութ է, որն օգտագործում է հոդվածի երկրորդ կեսը ստեղծելու համար փաստացի Աստղային կոնսենսուսի արձանագրություն.
Այս հոդվածում մենք հակիրճ կբացատրենք, թե ինչ է «պայմանագրերի համակարգը», ինչը կարող է այն դարձնել «բյուզանդական» և ինչու է բյուզանդական համակարգը դարձնել «դաշնային»: Այնուհետև մենք կբացատրենք SCP հոդվածում նկարագրված դաշնային քվեարկության ընթացակարգը, և վերջապես մենք կբացատրենք հենց SCP արձանագրությունը:
Համաձայնագրի համակարգեր
Համաձայնությունների համակարգը թույլ է տալիս մասնակիցների խմբին կոնսենսուսի հասնել մի թեմայի շուրջ, օրինակ՝ ինչ պատվիրել ճաշի համար:
Interstellar-ում մենք ներդրել ենք ճաշի պայմանագրերի մեր սեփական համակարգը. մենք պատվիրում ենք այն, ինչ ասում է մեր գործառնությունների մենեջեր Ջոնը: Սա պարզ և արդյունավետ պայմանագրերի համակարգ է: Մենք բոլորս վստահում ենք Ջոնին և հավատում, որ նա ամեն օր հետաքրքիր և սննդարար բան կգտնի։
Բայց ի՞նչ, եթե Ջոնը չարաշահի մեր վստահությունը։ Նա կարող է ինքնուրույն որոշել, որ մենք բոլորս պետք է վեգան դառնանք: Մեկ-երկու շաբաթից մենք հավանաբար կտապալենք նրան և իշխանությունը կհանձնենք Էլիզաբեթին։ Բայց հանկարծ նա սիրում է անչոուսով ավոկադո և կարծում է, որ բոլորը պետք է այդպիսին լինեն: Իշխանությունը փչացնում է. Այսպիսով, ավելի լավ է գտնել ավելի ժողովրդավարական մեթոդ. ինչ-որ կերպ համոզվելու, որ տարբեր նախապատվություններ են հաշվի առնվում՝ միաժամանակ ապահովելով ժամանակին և միանշանակ արդյունք, որպեսզի ոչ ոք չպատվիրի ճաշ, կամ հինգ հոգի տարբեր պատվերներ դնեն կամ քննարկեն: ձգվում է մինչև երեկո:
Թվում է, թե լուծումը պարզ է՝ անցկացրե՛ք քվեարկություն։ Բայց սա ապակողմնորոշիչ տպավորություն է։ Ո՞վ է հավաքելու քվեաթերթիկները և զեկուցելու արդյունքները։ Իսկ ինչո՞ւ ուրիշները պետք է հավատան նրա ասածներին։ Երևի կարող ենք սկզբում քվեարկեք մի առաջնորդի օգտին, ում վստահում ենք, որ կղեկավարի քվեարկությունը, բայց ով կղեկավարի այն առաջինը քվեարկությամբ? Իսկ եթե չկարողանանք պայմանավորվել առաջնորդի հարցում: Կամ եթե պայմանավորվենք, բայց այս ղեկավարը խրվի ժողովի մեջ կամ գնա հիվանդ արձակուրդի։
Նմանատիպ խնդիրներ առաջանում են բաշխված համակարգչային ցանցերում: Բոլոր մասնակիցները կամ հանգույցները պետք է համաձայնվեն որոշ որոշման շուրջ, օրինակ՝ ում հերթն է թարմացնել ընդհանուր ֆայլը կամ հեռացնել առաջադրանքը մշակման հերթից: Կրիպտոարժույթների ցանցում հանգույցները պետք է բազմիցս ընտրեն, թե ինչպիսին է ամբողջական պատմությունը մի քանի հնարավոր տարբերակներից, որոնք երբեմն հակասում են: Ցանցի այս պայմանագիրը հավաստիացում է տրամադրում ստացողին, որ մետաղադրամը (ա) վավեր է (կեղծված չէ) և (բ) դեռ այլ տեղ չի ծախսվել: Սա նաև ապահովում է, որ նա ապագայում կկարողանա ծախսել մետաղադրամները, քանի որ նոր ստացողը կունենա նույն երաշխիքները նույն պատճառներով:
Բաշխված հաշվողական ցանցում կոնսենսուսի ցանկացած համակարգ պետք է լինի անսարքության հանդուրժող. այն պետք է հետևողական արդյունքներ տա՝ չնայած այնպիսի սխալների, ինչպիսիք են դանդաղ հղումները, չպատասխանող հանգույցները և հաղորդագրությունների սխալ պատվիրումը: բյուզանդական Համաձայնագրի համակարգը հավելյալ դիմացկուն է «բյուզանդական» սխալներին. հանգույցներ, որոնք կեղծ տեղեկատվություն են տալիս, լինի դա սխալի հետևանքով կամ համակարգը խաթարելու կամ որոշակի առավելություններ ձեռք բերելու միտումնավոր փորձով: «Բյուզանդական» սխալների հանդուրժողականությունը՝ խմբի որոշմանը վստահելու ունակություն, նույնիսկ այն դեպքում, երբ խմբի որոշ անդամներ կարող են ստել կամ այլ կերպ չհետևել որոշումների կայացման կանոններին. ովքեր փորձել են համակարգել հարձակումը։ Էնթոնի Սթիվենսում:
Դիտարկենք կրիպտո մետաղադրամի սեփականատեր Ալիսը, ով պետք է ընտրի Բոբից համեղ պաղպաղակ գնելու և Քերոլի պարտքը մարելու միջև: Միգուցե Ալիսն ուզում է երկուսին էլ միանգամից վճարել՝ խաբեությամբ նույն մետաղադրամը ծախսելով։ Դա անելու համար նա պետք է համոզի Բոբի համակարգչին, որ մետաղադրամը երբեք չի վճարվել Քերոլին, և համոզի Քերոլի համակարգչին, որ մետաղադրամը երբեք չի վճարվել Բոբին: Բյուզանդական համաձայնագրերի համակարգը դա գործնականում անհնար է դարձնում՝ օգտագործելով մեծամասնության կանոնը, որը կոչվում է քվորում. Նման ցանցի հանգույցը հրաժարվում է անցնել պատմության որոշակի տարբերակ, քանի դեռ չի տեսնում, որ բավարար թվով գործընկերներ՝ քվորում, համաձայնում են նման անցմանը: Հենց դա տեղի ունենա, նրանք կձևավորեն բավականաչափ քվեարկության բլոկ, որպեսզի ստիպեն ցանցի մնացած հանգույցներին համաձայնվել իրենց որոշման հետ: Ալիսը կարող է ստիպել որոշ հանգույցների ստել իր անունից, բայց եթե ցանցը բավականաչափ մեծ է, նրա փորձը կհեղեղվի ազնիվ հանգույցների ձայներով:
Քանի՞ հանգույց է պահանջվում քվորումի համար: Նվազագույնը` մեծամասնություն, ավելի ճիշտ` որակյալ մեծամասնություն` սխալների ու խարդախության դեմ պայքարելու համար: Բայց մեծամասնությունը հաշվելու համար անհրաժեշտ է իմանալ մասնակիցների ընդհանուր թիվը: Interstellar գրասենյակում կամ շրջանային ընտրություններում այս թվերը հեշտ է պարզել: Բայց եթե ձեր խումբը թույլ սահմանված ցանց է, որտեղ հանգույցները կարող են մտնել և դուրս գալ ըստ ցանկության՝ առանց կենտրոնի հաստատման, ապա ձեզ անհրաժեշտ է. դաշնային բյուզանդական համաձայնությունների համակարգ, որն ի վիճակի է քվորումներ որոշել ոչ թե հանգույցների կանխորոշված ցանկից, այլ դինամիկ կերպով՝ ժամանակի տվյալ պահին հանգույցների անընդհատ փոփոխվող և անխուսափելիորեն թերի պատկերից:
Հսկայական ցանցում մեկ հանգույցի տեսանկյունից կարող է անհնար թվալ քվորում ստեղծելը, բայց դա հնարավոր է: Նման քվորումը կարող է նույնիսկ երաշխավորել ապակենտրոնացված քվեարկության արդյունքները։ SCP սպիտակ թուղթը ցույց է տալիս, թե ինչպես դա անել, օգտագործելով ընթացակարգը, որը կոչվում է դաշնային քվեարկությամբ.
Անհամբերների համար
Հոդվածի մնացած մասը ավելի մանրամասն նկարագրում է դաշնային քվեարկությունը և Stellar կոնսենսուսի արձանագրությունը: Եթե ձեզ չեն հետաքրքրում մանրամասները, ահա գործընթացի ընդհանուր ակնարկը:
- Հանգույցներն անցկացնում են դաշնային քվեարկության փուլեր «նոմինանտների» վերաբերյալ: Դաշնային քվեարկության փուլը նշանակում է.
- Հանգույցը ձայն է տալիս որոշ հայտարարության, օրինակ՝ «Ես առաջարկում եմ V-ի արժեքը»;
- Հանգույցը լսում է հասակակիցների ձայնը, մինչև գտնի մեկը, որը կարող է «ստանալ»;
- Հանգույցը փնտրում է «քվորում» այս պնդման համար: Քվորումը «հաստատում է» թեկնածուին:
- Երբ հանգույցը կարող է հաստատել մեկ կամ մի քանի թեկնածուների, այն փորձում է «պատրաստել» «քվեաթերթիկը» դաշնային քվեարկության մի քանի փուլերի միջոցով:
- Հենց որ հանգույցը կարողանա ստուգել, որ քվեաթերթիկը պատրաստ է, այն փորձում է իրականացնել դաշնային քվեարկության ավելի շատ փուլերի միջոցով:
- Երբ հանգույցը կարող է հաստատել քվեաթերթիկի կատարումը, այն կարող է «արտաքինացնել» այդ քվեաթերթիկի արժեքը՝ օգտագործելով այն որպես կոնսենսուսի արդյունք:
Այս քայլերը ներառում են դաշնային քվեարկության բազմաթիվ փուլեր, որոնք միասին կազմում են մեկ SCP փուլ: Եկեք ավելի սերտ նայենք, թե ինչ է տեղի ունենում յուրաքանչյուր քայլում:
Դաշնային քվեարկություն
Ֆեդերատիվ քվեարկությունը մի ընթացակարգ է՝ որոշելու, թե արդյոք ցանցը կարող է համաձայնության գալ առաջարկի շուրջ: Քվեարկության փուլում յուրաքանչյուր հանգույց պետք է ընտրի պոտենցիալ բազմաթիվ հնարավոր արժեքներից մեկը: Այն չի կարող դա անել, քանի դեռ վստահ չէ, որ ցանցի մյուս հանգույցները չեն ընտրի այլ արդյունք: Դրանում համոզվելու համար հանգույցները փոխանակում են հաղորդագրությունների տարափ ետ ու առաջ, որպեսզի բոլորը հաստատել էՈր քվորում հանգույցներ ընդունում է նույնը որոշում. Այս բաժնի մնացած մասը բացատրում է այս նախադասության տերմինները և ինչպես է կատարվում ամբողջ ընթացակարգը:
Քվորումներ և քվորումի հատվածներ
Սկսենք քվորում սահմանելուց։ Ինչպես վերը քննարկեցինք, դինամիկ անդամակցությամբ ապակենտրոնացված ցանցում հնարավոր չէ նախապես իմանալ հանգույցների քանակը և, հետևաբար, քանիսն են անհրաժեշտ մեծամասնությանը: Ֆեդերատիվ քվեարկությունը լուծում է այս խնդիրը՝ ներմուծելով նոր գաղափար քվորումի կրճատում (քվորումի հատված). Գործընկերների մի փոքր շարք, որին հանգույցը վստահում է քվեարկության կարգավիճակի մասին տեղեկատվությունը ցանցի մնացած մասերին հաղորդելու համար: Յուրաքանչյուր հանգույց սահմանում է իր քվորումի հատվածը (որի դե ֆակտո անդամ է դառնում):
Քվորումի ձևավորումը սկսվում է քվորումի կրճատմամբ: Յուրաքանչյուր հանգույցի համար ավելացվում են նրա կտրված հանգույցները: Այնուհետև ավելացվում են հատվածի տերմինները այս հանգույցները եւ այլն։ Շարունակելով, կան ավելի ու ավելի շատ հանգույցներ, որոնք դուք չեք կարող ավելացնել, քանի որ դրանք արդեն ներառված են հատվածում: Երբ այլևս չկան նոր հանգույցներ ավելացնելու, գործընթացը դադարում է. մենք քվորում ենք կազմել սկզբնական հանգույցի քվորումի հատվածի «անցումային փակման» միջոցով:
Տրված հանգույցից քվորում գտնելու համար...
... ավելացնել իր հատվածի անդամները...
...այնուհետև մենք ավելացնում ենք այս հանգույցների կտոր անդամները:
Շարունակում ենք այնքան ժամանակ, մինչև ավելացվող հանգույցներ չմնան։
Ավելացնելու համար հանգույցներ չեն մնացել: Սա քվորում է։
Փաստորեն, յուրաքանչյուր հանգույց կարող է հայտնվել մեկից ավելի հատվածով: Քվորում ձևավորելու համար ընտրեք հատվածներից միայն մեկը և ավելացրեք անդամներ. ապա յուրաքանչյուր անդամի համար ընտրեք ցանկացած հատված և ավելացրեք անդամներ այն կտրել և այլն: Սա նշանակում է, որ յուրաքանչյուր հանգույց շատ հնարավոր քվորումների անդամ է:
Ընտրեք միայն մեկ քվորումի հատված յուրաքանչյուր քայլում:
Մեկ հնարավոր քվորում. Կամ այլընտրանք...
...ընտրեք այլ հատվածներ...
… (երբ դա հնարավոր է)…
... ստեղծում է մեկ այլ քվորում:
Ինչպե՞ս է հանգույցը իմանում, թե որ հատվածներում են գտնվում մյուս հանգույցները: Նույն կերպ, ինչպես այլ հանգույցների մասին այլ տեղեկություններ. այն փոխանցումներից, որոնք յուրաքանչյուր հանգույց հեռարձակում է ցանց, երբ նրա քվեարկության վիճակը փոխվում է: Յուրաքանչյուր հեռարձակում պարունակում է տեղեկատվություն ուղարկող հանգույցի հատվածների մասին: SCP-ի սպիտակ թուղթը չի նշում հաղորդակցման մեխանիզմ: Իրականացումները սովորաբար օգտագործվում են հաղորդագրությունների երաշխավորված հեռարձակման համար ամբողջ ցանցում:
Հիշեցնենք, որ համաձայնագրերի ոչ դաշնային բյուզանդական համակարգում քվորումը սահմանվում է որպես բոլոր հանգույցների մեծամասնություն: Բյուզանդական պայմանագրային համակարգը նախագծված է այն հարցի տեսանկյունից՝ քանի՞ անազնիվ հանգույց կարող է հանդուրժել համակարգը։ N հանգույցների համակարգում, որը նախատեսված է f ձախողումներից գոյատևելու համար, հանգույցը պետք է կարողանա առաջընթաց գրանցել՝ ստանալով հետադարձ կապ N−f հասակակիցներից, քանի որ դրանցից f-ը կարող է ձախողված լինել: Բայց ստանալով պատասխան N−f հասակակիցներից՝ մենք կարող ենք ենթադրել, որ բոլոր f էջերը (որոնցից հանգույցը պատասխան չի ստացել) իրականում ազնիվ են։ Այսպիսով, N−f հասակակիցներից f-ը (որից ստացվել է պատասխանը) վնասակար են: Որպեսզի հանգույցները գան միևնույն համաձայնության, մնացած հանգույցների մեծ մասը պետք է լինի ազնիվ, այսինքն՝ մեզ պետք է, որ N−f-ը լինի 2f-ից մեծ կամ N > 3f: Այսպիսով, սովորաբար f ձախողումներից գոյատևելու համար նախատեսված համակարգը կունենա ընդհանուր N=3f+1 հանգույց և 2f+1 քվորումի չափ: Հենց որ առաջարկը հաղթահարի քվորումի շեմը, ցանցի մնացած անդամները համոզված են, որ ցանկացած մրցակցող առաջարկ չի հաջողվի: Այսպես է ցանցը զուգակցվում արդյունքին։
Բայց դաշնային բյուզանդական պայմանագրային համակարգում ոչ միայն չի կարող լինել մեծամասնություն (որովհետև ոչ ոք չգիտի ցանցի ընդհանուր չափը), այլև մեծամասնություն հասկացությունն ամբողջովին անօգուտ է: Եթե համակարգին անդամակցությունը բաց է, ապա ինչ-որ մեկը կարող է մեծամասնություն ձեռք բերել պարզապես այսպես կոչված Sybil գրոհի միջոցով՝ բազմիցս միանալով ցանցին մի քանի հանգույցներով: Այսպիսով, ինչու կարելի է անվանել անցումային շերտի փակում քվորում, և ինչպե՞ս է այն կարողանում ճնշել մրցակցող առաջարկները։
Տեխնիկապես, ոչ մի կերպ: Պատկերացրեք վեց հանգույցներից բաղկացած ցանց, որտեղ երկու եռյակներ մեկուսացված են միմյանց քվորումի շերտերում: Առաջին ենթախումբը կարող է որոշում կայացնել, որի մասին երկրորդը երբեք չի լսի, և հակառակը։ Այս ցանցի համար որևէ ձև չկա կոնսենսուսի հասնելու (բացառությամբ պատահականության):
Հետևաբար, SCP-ն պահանջում է, որ դաշնային քվեարկության համար (և փաստաթղթի կարևոր թեորեմների կիրառման համար), ցանցը պետք է ունենա մի հատկություն, որը կոչվում է. քվորումների հատում. Այս հատկությամբ ցանցում ցանկացած երկու քվորում, որը կարելի է կառուցել, միշտ համընկնում են առնվազն մեկ հանգույցում: Ցանցի գերակշռող տրամադրությունը որոշելու համար սա նույնքան լավ է, որքան մեծամասնություն ունենալը: Ինտուիտիվորեն սա նշանակում է, որ եթե որևէ քվորում համաձայնում է X հայտարարությանը, ոչ մի այլ քվորում երբեք չի կարող համաձայնել որևէ այլ բանի, քանի որ այն անպայման կներառի առաջին քվորումից որոշ հանգույց, որն արդեն քվեարկել է X-ի օգտին:
Եթե ցանցում քվորումների հատում լինի...
...հետո ցանկացած երկու քվորում կարող եք կառուցել...
...միշտ հատվելու է:
(Իհարկե, համընկնող հանգույցները կարող են լինել բյուզանդական կամ այլ կերպ վատ: Այս դեպքում, քվորումի խաչմերուկը չի օգնում ցանցին համաձայնության գալ: Այդ իսկ պատճառով, SCP սպիտակ թղթի արդյունքներից շատերը հիմնված են. հստակ ենթադրություններ, ինչպիսիք են այն, ինչ մնացել է ցանցի քվորումի հատման ժամանակ նույնիսկ վատ հանգույցները հեռացնելուց հետո. Պարզության համար թողնենք այս ենթադրությունները անուղղակի հոդվածի մնացած մասում):
Կարող է անհիմն թվալ ակնկալել, որ քվորումի հուսալի հատումը հնարավոր է անկախ հանգույցների ցանցում: Բայց կա երկու պատճառ, թե ինչու է դա այդպես.
Առաջին պատճառը հենց ինտերնետի առկայությունն է։ Համացանցը խաչվող քվորումներով անկախ հանգույցների ցանցի կատարյալ օրինակ է: Ինտերնետում գտնվող հանգույցների մեծ մասը միանում է միայն մի քանի այլ տեղական հանգույցների, բայց այս փոքր հավաքածուները այնքան են համընկնում, որ յուրաքանչյուր հանգույցից կարելի է հասնել որևէ երթուղու երկայնքով:
Երկրորդ պատճառը հատուկ է Stellar վճարային ցանցին (SCP-ի ամենատարածված օգտագործումը): Stellar ցանցի յուրաքանչյուր ակտիվ ունի թողարկող, և Stellar-ի ուղեցույցները պահանջում են, որ յուրաքանչյուր թողարկող նշանակի մեկ կամ մի քանի հանգույց ցանցում՝ մարման հարցումները մշակելու համար: Ձեր շահերից է բխում ուղղակիորեն կամ անուղղակիորեն ներառել այս հանգույցները քվորումի հատվածներում՝ ձեզ հետաքրքրող յուրաքանչյուր ակտիվի համար: Տվյալ ակտիվով հետաքրքրված բոլոր հանգույցների քվորումներն այնուհետև կհամընկնեն առնվազն այդ մարման հանգույցներում: Բազմաթիվ ակտիվներով հետաքրքրված հանգույցները կներառեն համապատասխան թողարկողների մարման բոլոր հանգույցները իրենց քվորումի հատվածներում, և նրանք կփորձեն միավորել բոլոր ակտիվները միասին: Բացի այդ, ցանկացած ակտիվներ, որոնք այս կերպ կապված չեն ցանցի մյուսների հետ, և չպետք է միացված լինի - սա նախատեսված է այնպես, որ այս ցանցի համար քվորումի համընկնումը չլինի (օրինակ, դոլարային գոտու բանկերը երբեմն ցանկանում են առևտուր անել եվրոյի գոտու բանկերի հետ, իսկ պեսո գոտու բանկերը, ուստի նրանք գտնվում են նույն ցանցում, բայց ոչ մեկը: նրանցից հոգ է տանում բեյսբոլի քարտեր վաճառող երեխաների առանձին ցանցի մասին):
Իհարկե, ожидание քվորումի հատում չկա երաշխիք. Բյուզանդական այլ պայմանագրերի համակարգեր իրենց բարդության մեծ մասը պարտական են քվորումի երաշխավորմանը: SCP-ի կարևոր նորամուծությունն այն է, որ այն հանում է քվորումներ ստեղծելու պատասխանատվությունը կոնսենսուսի ալգորիթմից և այն հասցնում կիրառական մակարդակի: Այսպիսով, թեև դաշնային քվեարկությունը բավականաչափ ընդհանուր է ցանկացած հարցի շուրջ քվեարկելու համար, դրա հուսալիությունը իրականում խիստ կախված է այս իմաստների ավելի լայն իմաստից: Որոշ հիպոթետիկ օգտագործումներ կարող են այնքան էլ նպաստավոր չլինել լավ կապված ցանցեր ստեղծելու համար, որքան մյուսները:
Քվեարկություն, ընդունում և հաստատում
Դաշնային քվեարկության փուլում հանգույցը ընտրովի սկսում է քվեարկել որոշ V արժեքի համար: Սա նշանակում է հաղորդագրություն հեռարձակել ցանցին. «Ես N հանգույցն եմ, իմ քվորումի հատվածները Q են, և ես քվեարկում եմ V-ի օգտին»: Երբ հանգույցը քվեարկում է այսպես, այն խոստանում է, որ երբեք դեմ չի քվեարկել V-ին և չի էլ անի:
Peer-to-peer հեռարձակումների ժամանակ յուրաքանչյուր հանգույց տեսնում է, թե ինչպես են մյուսները քվեարկում: Հենց որ հանգույցը հավաքի այս հաղորդագրություններից բավականաչափ, այն կարող է հետևել քվորումի հատվածներին և փորձել գտնել քվորումներ: Եթե նա տեսնի հասակակիցների քվորում, ովքեր նույնպես քվեարկում են V-ի օգտին, կարող է անցնել ընդունումը V և հեռարձակեք այս նոր հաղորդագրությունը ցանցին. «Ես N հանգույցն եմ, իմ քվորումի հատվածները Q են, և ես ընդունում եմ V-ն»: Ընդունումն ավելի ուժեղ երաշխիք է տալիս, քան պարզ քվեարկությունը: Երբ հանգույցը քվեարկում է V-ի օգտին, այն երբեք չի կարող քվեարկել այլ տարբերակների օգտին: Բայց եթե հանգույցն ընդունում է V-ն, ցանցի ոչ մի հանգույց երբեք չի ընդունի մյուս տարբերակը (SCP սպիտակ թղթի թեորեմ 8-ն ապացուցում է դա):
Իհարկե, մեծ է հավանականությունը, որ անմիջապես V-ի հետ համաձայնվող հանգույցների քվորում չի լինի: Մյուս հանգույցները կարող են քվեարկել այլ արժեքների օգտին: Բայց կա մեկ այլ միջոց, որով հանգույցը հասարակ քվեարկությունից անցում կատարի ընդունման: N-ը կարող է ընդունել W-ի համար այլ արժեք, նույնիսկ եթե նա դրա օգտին չի քվեարկել, և նույնիսկ եթե նա դրա համար քվորում չի տեսնում: Որպեսզի որոշեք փոխել ձեր ձայնը, պարզապես տեսեք արգելափակման հավաքածու հանգույցներ, որոնք ընդունել են W: Արգելափակող խումբը մեկ հանգույց է քվորումի յուրաքանչյուր հատվածից N: Ինչպես ենթադրում է անունը, այն կարող է արգելափակել ցանկացած այլ իմաստ: Եթե նման բազմության բոլոր հանգույցներն ընդունում են W-ն, ապա (8-րդ թեորեմով) երբեք հնարավոր չի լինի ձևավորել քվորում, որն այլ արժեք է վերցնում, և, հետևաբար, N-ի համար նույնպես անվտանգ է ընդունել W:
N հանգույց երեք քվորումի շերտով:
BDF-ը N-ի արգելափակող հավաքածու է. այն ներառում է մեկ հանգույց N-ի յուրաքանչյուր հատվածից:
BE-ն նաև N-ի արգելափակող հավաքածու է, քանի որ E-ն հայտնվում է N-ի երկու հատվածում:
Բայց արգելափակող խումբը քվորում չէ։ Չափազանց հեշտ կլիներ խաբել N հանգույցը՝ ընդունելու ցանկալի արժեքը, եթե բավական էր կոտրել միայն մեկ հանգույց N-ի յուրաքանչյուր հատվածում: Հետևաբար, արժեքը ընդունելը քվեարկության վերջը չէ: Փոխարենը, N-ը պետք է հաստատի արժեքը, այսինքն՝ տեսնի այն ընդունող հանգույցների քվորումը։ Եթե այն հասնի այդքան հեռու, ապա, ինչպես ապացուցում է SCP սպիտակ թուղթը (թեորեմ 11-ում), ցանցի մնացած մասը նույնպես ի վերջո կհաստատի նույն արժեքը, ուստի N-ը կավարտի դաշնային քվեարկությունը որոշակի արժեքով որպես արդյունք:
Դաշնային քվեարկություն.
Քվեարկության, ընդունման և հաստատման գործընթացը կազմում է դաշնային քվեարկության մեկ ամբողջական փուլ: Stellar կոնսենսուսային արձանագրությունը միավորում է այս փուլերից շատերը՝ ստեղծելու ամբողջական կոնսենսուսային համակարգ:
Աստղային կոնսենսուսի արձանագրություն
Կոնսենսուսային համակարգի երկու ամենակարևոր հատկություններն են անվտանգություն и գոյատևման հնարավորությունը. Կոնսենսուսի ալգորիթմը «անվտանգ է», եթե այն երբեք չի կարող տարբեր արդյունքներ տալ տարբեր մասնակիցներին (Պատմության Բոբի պատճենը երբեք չի հակասի Քերոլին): «Կենսունակություն» նշանակում է, որ ալգորիթմը միշտ արդյունք կտա, այսինքն՝ չի խրվի։
Նկարագրված է դաշնային քվեարկության ընթացակարգը ապահով այն իմաստով, որ եթե հանգույցը հաստատում է V-ի արժեքը, ոչ մի այլ հանգույց չի հաստատի մյուս արժեքը։ Բայց «այլ իմաստը չի հաստատի» չի նշանակում, որ անպայման ինչ-որ բան կհաստատի։ Մասնակիցները կարող են քվեարկել այնքան տարբեր արժեքների վրա, որ ոչինչ չի հասնի ընդունման շեմին: Սա նշանակում է, որ դաշնային քվեարկության մեջ չկա գոյատևման հնարավորությունը.
Stellar կոնսենսուսի արձանագրությունը օգտագործում է դաշնային քվեարկությունը այնպես, որ ապահովում է ինչպես անվտանգությունը, այնպես էլ գոյատևումը: (SCP-ի անվտանգության և գոյատևման երաշխիքներն ունեն տեսական սահման: Դիզայնն ընտրում է անվտանգության շատ ուժեղ երաշխիք՝ զոհաբերելով գոյատևման փոքր չափի մեղմացում, սակայն բավարար ժամանակի առկայության դեպքում մեծ հավանականություն կա, որ ձեռք կբերվի կոնսենսուս:) Մի խոսքով, գաղափարն այն է, որ ունենանք բազմաթիվ դաշնային ձայներ բազմաթիվ արժեքների վերաբերյալ, քանի դեռ դրանցից մեկը չի անցնում ստորև նկարագրված SCP քվեարկության բոլոր փուլերը:
Արժեքները, որոնց վերաբերյալ SCP-ն կոնսենսուս է փնտրում, կարող են լինել գործարքի պատմությունը կամ ճաշի պատվերը կամ այլ բան, բայց կարևոր է նշել, որ դրանք այն արժեքները չեն, որոնք ընդունված կամ հաստատված են: Փոխարենը, դաշնային քվեարկությունը տեղի է ունենում ըստ հայտարարություններ այս արժեքների մասին.
Դաշնային քվեարկության առաջին փուլերը տեղի կունենան առաջադրման փուլ (առաջադրման փուլ), մի շարք հայտարարությունների վրա, ինչպիսին է «Ես առաջադրում եմ V-ին», միգուցե V-ի շատ տարբեր արժեքների համար: Առաջադրման նպատակն է գտնել մեկ կամ մի քանի հայտարարություններ, որոնք անցնում են ընդունման և հաստատման միջոցով:
Ստուգելի թեկնածուներ գտնելուց հետո ՀՔԾ-ն անցնում է քվեարկության փուլին, որտեղ նպատակն է գտնել որոշակի. տեղեկագիր (այսինքն՝ առաջարկվող արժեքի կոնտեյներ) և քվորում, որը կարող է հայտարարել պարտավորվել դրա համար (կատարել): Եթե քվորումը կատարում է քվեաթերթիկ, ապա դրա արժեքն ընդունվում է որպես կոնսենսուս: Բայց նախքան հանգույցը կարող է քվեարկել քվեաթերթիկի հանձնման վերաբերյալ, այն նախ պետք է հաստատի չեղարկումը բոլոր քվեաթերթիկները ավելի ցածր հակարժեքով: Այս քայլերը՝ չեղյալ համարել քվեաթերթիկները՝ գտնելու համար, որը կարող է կատարվել, ներառում է մի քանի քվեաթերթիկների վերաբերյալ պահանջների վերաբերյալ դաշնային քվեարկության մի քանի փուլեր:
Հետևյալ բաժինները ավելի մանրամասն նկարագրում են առաջադրումը և քվեարկությունը:
Առաջադրում
Առաջադրման փուլի սկզբում յուրաքանչյուր հանգույց կարող է ինքնաբերաբար ընտրել V-ի արժեքը և քվեարկել «Ես առաջադրում եմ V-ին» արտահայտությանը: Նպատակն այս փուլում դաշնային քվեարկության միջոցով ինչ-որ արժեքի առաջադրումը հաստատելն է։
Թերևս բավականաչափ հանգույցներ քվեարկում են բավական տարբեր առաջարկների վրա, որ ոչ մի առաջադրում չի կարող հասնել ընդունման շեմին: Հետևաբար, բացի իրենց առաջադրման ձայները հեռարձակելուց, հանգույցները «արտացոլում են» իրենց հասակակիցների առաջադրումները: Արձագանքը նշանակում է, որ եթե հանգույցը քվեարկի V առաջադրման օգտին, բայց տեսնի հաղորդագրություն հարևանի կողմից, որը քվեարկում է W առաջադրման օգտին, նա այժմ կքվեարկի և՛ V-ի, և՛ W-ի օգտին։ տարբեր թեկնածուներ: SCP-ն ներառում է այդ քվեարկությունները կարգավորելու մեխանիզմ: Կարճ ասած, կա մի բանաձև, որը որոշելու է գործընկերոջ «առաջնահերթությունը» հանգույցի տեսանկյունից, և արտացոլվում են միայն բարձր առաջնահերթության հանգույցների ձայները: Որքան երկար է առաջադրումը: այնքան ցածր է շեմը, այնպես որ հանգույցը ընդլայնում է հասակակիցների շարքը, որոնց ձայները կարտացոլի: Առաջնահերթության բանաձևը ներառում է անցքի համարը որպես մուտքագրումներից մեկը, այնպես որ մեկ սլոտի համար բարձր առաջնահերթ գործընկերը կարող է լինել ցածր առաջնահերթություն: մեկ այլ, և հակառակը):
Հայեցակարգային առումով առաջադրումը զուգահեռ է, և՛ V, և՛ W-ն առանձին դաշնային ձայներ են, որոնցից յուրաքանչյուրն առանձին-առանձին կարող է հասնել ընդունման կամ հաստատման: Գործնականում SCP արձանագրային հաղորդագրությունները փաթեթավորում են այս առանձին ձայները միասին:
Թեև V-ի առաջադրմանը կողմ քվեարկելը խոստում է երբեք դեմ չքվեարկել V-ի առաջադրմանը, սակայն հայտի մակարդակում, այս դեպքում՝ SCP-ն, որոշվում է, թե ինչ է նշանակում «դեմ»: SCP-ն չի տեսնում հայտարարություն, որը հակասում է «Ես առաջադրում եմ X» քվեարկությանը, այսինքն՝ չկա «Դեմ եմ X առաջադրելուն» հաղորդագրությունը, ուստի հանգույցը կարող է քվեարկել ցանկացած արժեք առաջադրելու համար։ Այս անվանակարգերից շատերը ոչ մի տեղ չեն գնա, բայց ի վերջո հանգույցը կկարողանա ընդունել կամ հաստատել մեկ կամ մի քանի արժեքներ: Հենց որ թեկնածուն հաստատվի, նա դառնում է թեկնածու.
SCP-ի առաջադրում դաշնային քվեարկության միջոցով: Կարող են լինել բազմաթիվ «B» արժեքներ, որոնք առաջ են քաշվում գործընկերների կողմից և «արտացոլված» հանգույցի կողմից:
Առաջադրումները կարող են հանգեցնել բազմաթիվ հաստատված թեկնածուների: Հետևաբար, SCP-ն պահանջում է, որ կիրառական շերտը տրամադրի թեկնածուներին մեկի մեջ միավորելու մեթոդ կոմպոզիտային (կոմպոզիտային): Միացման մեթոդը կարող է լինել ցանկացած բան: Գլխավորն այն է, որ եթե այս մեթոդը դետերմինիստական է, ապա յուրաքանչյուր հանգույց կմիավորի նույն թեկնածուներին: Լանչ քվեարկության համակարգում «միավորումը» կարող է պարզապես նշանակել երկու թեկնածուներից մեկին մերժել: (Բայց դետերմինիստական ձևով. յուրաքանչյուր հանգույց պետք է ընտրի նույն արժեքը՝ վերակայելու համար: Օրինակ՝ ավելի վաղ ընտրությունը այբբենական կարգով): Stellar վճարային ցանցում, որտեղ քվեարկվում է գործարքների պատմությունը, երկու առաջարկված թեկնածուների միաձուլումը ներառում է դրանց պարունակած գործարքների և դրանց երկու ժամանակի վերջին դրոշմանիշների միավորումը:
SCP սպիտակ թուղթն ապացուցում է (թեորեմ 12), որ ընդլայնման փուլի ավարտին ցանցն ի վերջո համախմբվում է մեկ կոմպոզիտային: Բայց կա մի խնդիր. դաշնային քվեարկությունը ասինխրոն արձանագրություն է (ինչպես SCP): Այլ կերպ ասած, հանգույցները չեն համակարգվում ժամանակով, այլ միայն իրենց ուղարկած հաղորդագրություններով: Հանգույցի տեսանկյունից անհասկանալի է, թե երբ ավարտվեց երկարաձգման փուլ. Եվ չնայած բոլոր հանգույցները, ի վերջո, կհասնեն միևնույն կոմպոզիտային, նրանք կարող են անցնել տարբեր երթուղիներ ճանապարհին, ճանապարհին ստեղծելով տարբեր կոմպոզիտային թեկնածուներ և երբեք չեն կարող ասել, թե որն է վերջնականը:
Բայց դա նորմալ է. Առաջադրումը պարզապես նախապատրաստություն է։ Գլխավորը թեկնածուների թիվը սահմանափակելն է՝ կոնսենսուսի հասնելու համար, ինչը տեղի է ունենում գործընթացում առաջադրվել է պաշտոնի համար (քվեարկություն):
Վազում
Bulletin-ը զույգ է , որտեղ հաշվիչը ամբողջ թիվ է, որը սկսվում է 1-ից, իսկ արժեքը՝ թեկնածու առաջադրման փուլից: Սա կարող է լինել հանգույցի սեփական թեկնածուն կամ հարևան հանգույցի թեկնածուն, որն ընդունված է այդ հանգույցի կողմից: Կոպիտ ասած, քվեաթերթիկը ներառում է ցանցին ստիպելու կրկնվող փորձեր՝ որոշակի քվեաթերթիկում ինչ-որ թեկնածուի վերաբերյալ կոնսենսուսի հասնել՝ քվեաթերթիկների հայտարարությունների վերաբերյալ պոտենցիալ շատ դաշնային ձայներ անցկացնելով: Քվեաթերթիկների հաշվիչները հետևում են կատարված փորձերին, և ավելի մեծ թվով քվեաթերթիկները գերակայում են ավելի ցածր թվով քվեաթերթիկների նկատմամբ: Եթե տեղեկագիրը խրվում է, նոր քվեարկություն է սկսվում, հիմա քվեաթերթիկում .
Կարևոր է տարբերակել արժեքներ (օրինակ, ինչպիսի՞ն պետք է լինի լանչի պատվերը՝ պիցցա կամ աղցաններ), տեղեկագրեր (հակարժեքային զույգ) և հայտարարություններ քվեաթերթիկների մասին։ SCP փուլը ներառում է դաշնային քվեարկության մի քանի փուլ, մասնավորապես հետևյալ հայտարարությունների վերաբերյալ.
- «Ես պատրաստ եմ կատարել Բ քվեաթերթիկը» և
- «Հայտարարում եմ Բ քվեաթերթիկի ընդունումը».
Տվյալ հանգույցի տեսանկյունից կոնսենսուսը ձեռք է բերվում, երբ նա գտնում է B քվեաթերթիկ, որի համար կարող է հաստատել (այսինքն՝ գտնել քվորում ընդունելու համար) «Ես կատարում եմ «B» քվեաթերթիկը: Այս պահից սկսած, անվտանգ է գործել B-ում նշված արժեքով, օրինակ՝ այս պատվերը կատարելով ճաշի համար: Այն կոչվում է արտաքինացում իմաստներ. Հենց որ քվեաթերթիկի ընդունումը հաստատվի, հանգույցը կարող է վստահ լինել, որ ցանկացած այլ հանգույց նույն արժեքն է արտաքինացրել կամ դա կանի ապագայում:
Թեև շատ դաշնային քվեարկություններ կոնցեպտուալ կերպով անցկացվում են բազմաթիվ տարբեր քվեաթերթիկների պահանջների վերաբերյալ, նրանք այդքան շատ հաղորդագրություններ չեն փոխանակում, քանի որ յուրաքանչյուր հաղորդագրություն ներառում է մի շարք քվեաթերթիկներ: Այսպիսով, մեկ հաղորդագրություն խթանում է միանգամից բազմաթիվ դաշնային ձայների վիճակը, օրինակ. նախքան «
Ի՞նչ են նշանակում «պատրաստված» և «կատարել» տերմինները:
Հանգույցը քվեարկում է քվեաթերթիկ կատարելու օգտին, երբ վստահ է, որ մյուս հանգույցները տարբեր արժեքներով քվեաթերթիկներ չեն ընդունի: Համոզելով սա է դիմումի պատրաստման նպատակը։ Քվեարկությունը, որն ասում է «Ես պատրաստ եմ կատարել B քվեաթերթիկը», խոստանում է երբեք չանցկացնել B-ից փոքր քվեաթերթիկ, այսինքն՝ ավելի փոքր թվով (SCP-ն պահանջում է, որ քվեաթերթիկների արժեքները լինեն որոշակի հերթականությամբ: Այսպիսով, տեղեկագիր պակաս , եթե N1
Ինչու՞ է «ես պատրաստ եմ կատարել B քվեաթերթիկը» նշանակում է «Ես խոստանում եմ երբեք չտալ B-ից փոքր քվեաթերթիկներ»: Քանի որ SCP-ն աբորտը սահմանում է որպես commit-ի հակառակ: Քվեաթերթիկ պատրաստելու քվեարկությունը ներառում է նաև որոշ այլ քվեաթերթիկներ որակազրկելու քվեարկություն, և, ինչպես մենք ավելի վաղ քննարկեցինք, մեկ բանի օգտին քվեարկելը խոստում է երբեք դեմ չքվեարկել:
Նախքան commit հեռարձակելը, հանգույցը նախ պետք է գտնի տեղեկագիր, որը կարող է հաստատել, քանի որ պատրաստված է: Այլ կերպ ասած, այն իրականացնում է դաշնային քվեարկություն «Ես պատրաստ եմ կատարել B քվեաթերթիկը» թեմայով, հնարավոր է շատ տարբեր քվեաթերթիկների վրա, մինչև գտնի այն մեկը, ով կընդունի քվորումը:
Որտեղի՞ց են գալիս քվեաթերթիկները քվեարկությունը նախապատրաստելու համար: Նախ, հանգույցը հեռարձակում է <1,C>-ի օգտին քվեարկելու նախապատրաստական աշխատանքները, որտեղ C-ն առաջադրման փուլում արտադրված կոմպոզիտային թեկնածուն է: Այնուամենայնիվ, նույնիսկ քվեարկության նախապատրաստական աշխատանքների մեկնարկից հետո, առաջադրումները կարող են հանգեցնել նրան, որ լրացուցիչ թեկնածուներ դառնան նոր քվեաթերթիկներ: Մինչդեռ, հասակակիցները կարող են ունենալ տարբեր թեկնածուներ, և նրանք կարող են ձևավորել արգելափակող խումբ, որն ընդունում է «Ես պատրաստ եմ կատարել B2 քվեաթերթիկը», որը կհամոզի հանգույցին նույնպես ընդունել այն: Վերջապես, կա ժամանակի դադարման մեխանիզմ, որը առաջացնում է դաշնային քվեարկության նոր փուլեր նոր քվեաթերթիկների ավելի բարձր հաշվարկներով, եթե ներկայիս քվեաթերթիկները խրված են:
Հենց որ հանգույցը գտնում է B քվեաթերթիկ, որը կարող է հաստատել, քանի որ պատրաստված է, այն հեռարձակում է նոր հաղորդագրություն «Կատարել B քվեաթերթիկը»: Այս քվեարկությունը հասակակիցներին ասում է, որ հանգույցը երբեք չի հրաժարվի B-ից: Փաստորեն, եթե B-ն քվեաթերթիկ է , ապա «Կատարել քվեաթերթիկ «նշանակում է յուրաքանչյուր քվեաթերթիկի պատրաստության համար քվեարկելու անվերապահ համաձայնություն դեպի <∞, s>: Այս լրացուցիչ արժեքը օգնում է մյուս հասակակիցներին հասնել commit peer-ին, եթե նրանք դեռևս գտնվում են արձանագրության ավելի վաղ փուլերում:
Այս փուլում հարկ է ևս մեկ անգամ ընդգծել, որ դրանք ասինքրոն արձանագրություններ են։ Պարզապես այն պատճառով, որ մի հանգույց ուղարկում է կողմ ձայներ կատարման համար, չի նշանակում, որ իր հասակակիցները նույնպես դա անում են: Նրանցից ոմանք դեռ կարող են քվեարկել քվեարկությանը նախապատրաստվող հայտարարությունների վերաբերյալ, մյուսները կարող են արդեն արտաքին իմաստով: SCP-ն բացատրում է, թե ինչպես պետք է հանգույցը մշակի գործընկերային հաղորդագրությունների յուրաքանչյուր տեսակ՝ անկախ դրա փուլից:
Եթե հաղորդագրությունը «Ես հայտարարել եմ commit » չի կարող ստացվել կամ հաստատվել, այսինքն՝ հաղորդագրության ընդունման կամ հաստատման հավանականությունը կամ - կամ, ամեն դեպքում, C արժեքով ցանկացած քվեաթերթիկ, և ոչ որևէ այլ, քանի որ հանգույցն արդեն խոստացել է երբեք չեղարկել . Այն պահին, երբ հանգույցը հեռարձակում է կատարման համար ձայները, այն կլինի C կամ ոչինչ՝ կախված նրանից, թե որքան հեռու է կոնսենսուսը: Այնուամենայնիվ, սա դեռ բավարար չէ հանգույցի համար C-ին արտաքին տեսքի բերելու համար: Որոշ բյուզանդական հասակակիցներ (որոնք կազմում են քվորումից պակաս՝ հիմնված մեր անվտանգության ենթադրությունների վրա) կարող են ստել հանգույցին: Որոշ քվեաթերթիկներ (կամ քվեաթերթիկների շարք) ընդունելը և այնուհետև հաստատելն այն է, ինչը հանգույցին վստահություն է տալիս վերջնականապես արտաքին դարձնելու C-ն:
SCP քվեարկությունը դաշնային քվեարկության միջոցով. Ցուցադրված չէ. ժմչփը ցանկացած պահի կարող է անջատվել՝ մեծացնելով քվեաթերթիկների հաշվարկը (և, հնարավոր է, ստեղծելով լրացուցիչ առաջադրված թեկնածուների նոր կազմ):
Եվ դա բոլորը! Երբ ցանցը հասնի կոնսենսուսի, այն պատրաստ է դա անել նորից ու նորից: Stellar վճարային ցանցում դա տեղի է ունենում մոտավորապես 5 վայրկյանը մեկ անգամ. սխրանք, որը պահանջում է SCP-ի կողմից երաշխավորված և՛ անվտանգություն, և՛ գոյատևում:
SCP-ն կարող է հասնել դրան՝ հենվելով դաշնային քվեարկության բազմաթիվ փուլերի վրա: Ֆեդերատիվ քվեարկությունը հնարավոր է դարձել քվորումի հատվածների հայեցակարգի շնորհիվ. հասակակիցների հավաքածուներ, որոնց յուրաքանչյուր հանգույց որոշել է վստահել որպես իր (սուբյեկտիվ) քվորումի մաս: Այս կոնֆիգուրացիան նշանակում է, որ կոնսենսուսի կարելի է հասնել նույնիսկ բաց անդամակցությամբ և բյուզանդական խաբեություններով ցանցում:
Լրացուցիչ ընթերցում
- Բնօրինակ SCP սպիտակ թուղթը կարելի է գտնել Իսկ դրա իրականացման տեխնիկական պայմանների նախագիծը:
- SCP արձանագրության սկզբնական հեղինակ Դեյվիդ Մազիերը բացատրում է այն պարզեցված (բայց դեռ տեխնիկական) ձևով: .
- Դուք կարող եք զարմացած լինել այս հոդվածում չգտնելով «հանքարդյունաբերություն» կամ «աշխատանքի ապացույց» տերմինները: SCP-ն չի օգտագործում այս մեթոդները, սակայն որոշ այլ համաձայնության ալգորիթմներ օգտագործում են: Զեյն Ուիզերսփունը գրել է մատչելի .
- պարզ ցանց, որը կոնսենսուսի է հասնում SCP-ի մեկ ամբողջական փուլում:
- SCP-ի իրականացումներով հետաքրքրված ընթերցողների համար տես , որն օգտագործվում է Stellar վճարային ցանցի կողմից, կամ , որը ես գրել եմ SCP-ն ավելի լավ հասկանալու համար:
Source: www.habr.com