Консенсус (информатика) - Consensus (computer science)

Ішіндегі негізгі проблема таратылған есептеу және көп агенттік жүйелер бірқатар ақаулы процестер болған кезде жүйенің жалпы сенімділігіне қол жеткізу болып табылады. Бұл көбіне жету үшін үйлестіру процестерін қажет етеді консенсус, немесе есептеу кезінде қажет болатын кейбір деректер мәні туралы келісіңіз. Келісімнің қосымшаларына мәліметтер базасына қандай транзакцияларды қандай тәртіппен жасауға келісу кіреді, мемлекеттік машинаның репликациясы, және атомдық хабарлар. Жиі консенсус талап ететін нақты әлемдегі қосымшаларға жатады бұлтты есептеу, сағаттық синхрондау, PageRank, пікір қалыптастыру, ақылды электр желілері, мемлекеттік бағалау, ұшу аппараттарын басқару (және жалпы бірнеше роботтар / агенттер), жүктемені теңдестіру, блокчейн, және басқалар.

Мәселелерді сипаттау

Консенсус мәселесі деректердің бір мәні үшін бірқатар процестердің (немесе агенттердің) келісуін талап етеді. Кейбір процестер (агенттер) сәтсіздікке ұшырауы немесе басқа жолмен сенімсіз болуы мүмкін, сондықтан консенсус хаттамалары болуы керек ақаулыққа төзімді немесе серпімді. Процестер қандай-да бір түрде өздерінің үміткер құндылықтарын көрсетіп, бір-бірімен байланысып, бірыңғай консенсус мәні бойынша келісуі керек.

Консенсус мәселесі көп агенттік жүйелерді басқарудың негізгі проблемасы болып табылады. Консенсусты қалыптастырудың бір тәсілі - барлық процестердің (агенттердің) көпшілік мәні туралы келісуі. Осы тұрғыдан алғанда, көпшілікке қол жетімді дауыстардың кемінде жартысынан көбі қажет (мұнда әр процеске дауыс беріледі). Алайда, бір немесе бірнеше ақаулы процедуралар нәтижеге әкелуі мүмкін, сондықтан консенсусқа қол жеткізілмейді немесе қате қол жеткізілмейді.

Консенсус мәселелерін шешетін хаттамалар шектеулі санды мәселелерді шешуге арналған процестер. Бұл хаттамалар пайдалы болу үшін бірқатар талаптарды қанағаттандыруы керек. Мысалы, тривиальды хаттамада барлық процестердің екілік мәні шығуы мүмкін. Бұл пайдалы емес, демек, нәтиже қандай да бір жолмен кіріске тәуелді болатындай етіп өзгертіледі. Яғни консенсус протоколының шығыс мәні қандай да бір процестің кіріс мәні болуы керек. Тағы бір талап, процесс шығыс мәнін тек бір рет шеше алады және бұл шешім қайтарылмайды. Процесс орындалуда дұрыс деп аталады, егер ол сәтсіздікке ұшырамаса. Істен шығуды тоқтататын консенсус хаттамасы келесі қасиеттерді қанағаттандыруы керек.[1]

Тоқтату
Сайып келгенде, кез-келген дұрыс процесс белгілі бір мәнді шешеді.
Адалдық
Егер барлық дұрыс процестер бірдей мәнді ұсынса , содан кейін кез-келген дұрыс процесс шешілуі керек .
Келісім
Әрбір дұрыс процесс бірдей мәнде келісуі керек.

Анықтамасындағы вариациялар тұтастық өтінішке сәйкес орынды болуы мүмкін. Мысалы, шешімнің мәні кейбір дұрыс үдеріс ұсынған мәнге тең болуы үшін әлсіздіктің әлсіз түрі болуы мүмкін - олардың барлығы бірдей емес.[1] The Адалдық күйі ретінде белгілі жарамдылық әдебиетте.[1]

N процесі арасында консенсусқа дұрыс кепілдік бере алатын, ең көбі t сәтсіз болатын хаттама деп аталады т-төзімді.

Консенсус хаттамаларының нәтижелілігін бағалау кезінде қызығушылық тудыратын екі фактор бар жүгіру уақыты және хабарламаның күрделілігі. Жұмыс уақыты берілген Үлкен O белгісі кейбір кіріс параметрлерінің функциясы ретінде хабарламалар алмасу раундарының санында (әдетте процестердің саны және / немесе кіріс доменінің мөлшері). Хабарламаның күрделілігі дегеніміз - хаттамамен жасалатын хабарлама трафигінің мөлшері. Басқа факторлар жадты пайдалану мен хабарламалардың көлемін қамтуы мүмкін.

Есептеу модельдері

Есептеудің әр түрлі модельдері «консенсус мәселесін» анықтауы мүмкін. Кейбір модельдер толығымен байланысты графиктермен, ал басқалары сақиналар мен ағаштармен айналысуы мүмкін. Кейбір модельдерде хабарламаның аутентификациясы рұқсат етіледі, ал басқаларында процестер толығымен жасырын болады. Процестер ортақ жадтағы объектілерге қатынасу арқылы байланысатын ортақ жад модельдері де зерттеудің маңызды бағыты болып табылады.

Тікелей немесе тасымалданатын аутентификациясы бар байланыс арналары

Қарым-қатынас протоколының көптеген модельдерінде қатысушылар байланысады аутентификацияланған арналар. Бұл дегеніміз, хабарламалар жасырын емес, алушылар қабылдаған әрбір хабарламаның қайнар көзін біледі, ал кейбір модельдер мықты деп санайды, тасымалданатын аутентификация нысаны, мұнда әрқайсысы хабар алушы әр хабарламаның тікелей көзін ғана емес, хабарламаны бастапқыда құрған қатысушыны білуі үшін жіберуші қол қояды, бұл аутентификацияның анағұрлым күшті түріне цифрлық қолтаңба қол жеткізеді, ал егер аутентификацияның мықты түрі болса, хаттамалар көптеген ақауларға жол бере алады.[2]

Екі түрлі аутентификация моделі жиі аталады ауызша қарым-қатынас және жазбаша байланыс модельдер. Ауызша сөйлесу моделінде жедел ақпарат көзі белгілі, ал күшті, жазбаша байланыс модельдерінде қабылдағыштың әрбір қадамы хабарламаның жедел көзін ғана емес, хабарламаның байланыс тарихын да біледі.[3]

Консенсус кірістері мен нәтижелері

Ең дәстүрлі бір мәнді сияқты консенсус хаттамалары Паксо, ынтымақтастық түйіндері пайдалы кодтау үшін айнымалы өлшемі болуы мүмкін бүтін сан сияқты бір мәнге келіседі метадеректер деректер базасына жасалған транзакция сияқты.

Деп аталатын бір мәнді консенсус мәселесінің ерекше жағдайы екілік консенсус, кірісті, демек шығыс доменін бір екілік цифрмен шектейді {0,1}. Екілік консенсус хаттамалары өздері үшін онша пайдалы емес болғанымен, көбінесе жалпы консенсус хаттамаларында, әсіресе асинхронды консенсус үшін құрылыс материалы ретінде пайдалы.

Жылы көп мәнді сияқты консенсус хаттамалары Мульти-паксо және Сал, мақсаты біртұтас мәнді ғана емес, уақыт өте келе дамып келе жатқан тарихты қалыптастыра отырып, бірқатар құндылықтар туралы келісімге келу. Көп мәнді консенсусқа бір мәнді консенсус хаттамасының бірнеше қайталануын қатарынан іске қосу арқылы аңғалдықпен қол жеткізуге болатын болса да, көптеген оңтайландыру және қайта конфигурацияны қолдау сияқты басқа да ойлар көп мәнді консенсус протоколдарын іс жүзінде тиімді ете алады.

Апат және Византия сәтсіздіктері

Процестің екі түрлі ақаулары болуы мүмкін, а апаттың бұзылуы немесе а Византия сәтсіздігі. A апаттың бұзылуы процесс кенеттен тоқтап, қайта жалғаспаған кезде пайда болады. Византия сәтсіздігіs - бұл ешқандай шарт қойылмаған сәтсіздіктер. Мысалы, олар қарсыластың зиянды әрекеттері нәтижесінде пайда болуы мүмкін. Византия сәтсіздігін бастан кешірген процесс қарама-қайшы немесе қарама-қайшы деректерді басқа процестерге жіберуі мүмкін немесе ұйықтап, кейін ұзақ кідірістен кейін жұмысын жалғастыра алады. Сәтсіздіктердің екі түрінің ішінде Византия сәтсіздіктері анағұрлым бұзады.

Осылайша, византиялық сәтсіздіктерге жол беретін консенсус хаттамасы болуы мүмкін барлық қателіктерге төзімді болуы керек.

Византия сәтсіздіктеріне төзімді консенсус күштірек нұсқасы Адалдықты шектеуді күшейту арқылы беріледі:

Адалдық
Егер дұрыс процесс шешсе , содан кейін қандай да бір дұрыс үдеріспен ұсынылған болуы керек.

Асинхронды және синхронды жүйелер

Консенсус мәселесі асинхронды немесе синхронды жүйелер жағдайында қарастырылуы мүмкін. Нақты әлемдік коммуникация көбінесе асинхронды болса да, синхронды жүйелерді модельдеу оңайырақ,[4] өйткені асинхронды жүйелер синхрондыға қарағанда табиғи түрде көп мәселелерді қамтиды.

Синхронды жүйелерде барлық байланыс жалғасады деп есептеледі раундтар. Бір айналымда процесс басқа хабарламалардан барлық хабарларды ала отырып, өзіне қажет барлық хабарларды жібере алады. Осылайша, бір айналымнан келген хабарлама бір турдың ішінде жіберілген хабарламаларға әсер ете алмайды.

FLP мүмкін еместігі асинхронды детерминистік консенсусқа әкеледі

Толығымен асинхронды хабарлама таратылатын жүйеде, онда кем дегенде бір процесс а болуы мүмкін апаттың бұзылуы, бұл әйгіліде дәлелденген FLP мүмкін емес нәтижесі бұл а детерминирленген алгоритм консенсусқа қол жеткізу мүмкін емес.[5] Бұл мүмкін емес нәтиже жоспарлаудың сценарийлерінен туындайды, олар іс жүзінде екіталай болып шығады, мысалы, ақылды сияқты қарсылас жағдайлардан басқа қызметтен бас тарту шабуылдаушысы желіде. Көптеген қалыпты жағдайларда процестерді жоспарлау табиғи кездейсоқтыққа ие.[4]

Асинхронды модельде кейбір сәтсіздіктер синхронды консенсус хаттамасымен өңделеді. Мысалы, байланыс байланысының жоғалуы Византия сәтсіздігіне ұшыраған процесс ретінде модельденуі мүмкін.

Рандомизацияланған консенсус алгоритмдері FLP мүмкін емес нәтижесін айналып өтуі мүмкін, бұл үлкен ықтималдылықпен қауіпсіздікке де, тіршілікке де қол жеткізеді, тіпті жоспарлаудың ең нашар сценарийлері кезінде, мысалы, желідегі қызметтен бас тартудың ақылды шабуылшысы.[6]

Рұқсат етілген және рұқсат етілмеген консенсус

Консенсус алгоритмдері дәстүрлі түрде түйіндерге қатысатын түйіндер жиынтығы бекітілген және бастапқыда берілген деп есептейді: яғни кейбір алдыңғы (қолмен немесе автоматты) конфигурация процесі бар рұқсат етілген топ мүшелері ретінде бір-бірін аутентификациялай алатын белгілі бір белгілі қатысушылар тобы. Мұндай анықталған, аутентификацияланған мүшелері бар жабық топ болмаған жағдайда, а Сибил шабуылы ашық консенсус тобы тіпті Византия консенсус алгоритмін жеңе алады, жай вирустық қатысушыларды ақауларға төзімділік шегін еңсеру үшін жеткілікті құра алады.

A рұқсатсыз консенсус протоколы, керісінше, желідегі кез-келген адамға динамикалық қосылуға және алдын-ала рұқсатынсыз қатысуға мүмкіндік береді, бірақ оның орнына басқа түрдегі жасанды шығындар немесе кіруге кедергі азайту үшін Сибил шабуылы қауіп-қатер. Bitcoin криптографиялық негізделген бірінші рұқсатсыз консенсус хаттамасын енгізді жұмыс дәлелі, онда қатысушылар криптографиялық шешуге таласады хэш басқатырғыштар және ықтималдықпен олардың инвестицияланған есептеу күшіне пропорционалды түрде блоктар жасау және байланысты сыйақы алу құқығын алады. Ішінара осы тәсілдің жоғары энергетикалық құны түрткі болды, келесі рұқсат етілмеген консенсус хаттамалары Сибил шабуылынан қорғаудың басқа баламалы ережелерін ұсынды немесе қабылдады, мысалы. үлестің дәлелі, кеңістіктің дәлелі, және беделінің дәлелі.

Келісім мәселелерінің баламалылығы

Келісімнің үш проблемасы келесідей.

Сенімді хабар таратуды тоқтату

Жинағы бастап нөмірленген процестер дейін бір-біріне хабарлама жіберу арқылы сөйлесу. Процесс мәнді жіберуі керек барлық процестерге:

  1. егер процесс дұрыс, содан кейін әрбір дұрыс процесс қабылданады
  2. кез-келген екі дұрыс процесс үшін әр процесс бірдей мән алады.

Ол «Генерал проблемасы» деп те аталады.

Консенсус

Консенсус хаттамасына қойылатын ресми талаптар мыналарды қамтуы мүмкін:

  • Келісім: Барлық дұрыс процестер бірдей мәнде келісуі керек.
  • Жарамдылығы әлсіз: Әрбір дұрыс процесс үшін оның шығысы дұрыс процестің кірісі болуы керек.
  • Қатты жарамдылық: Егер барлық дұрыс процестер бірдей кіріс мәнін алса, онда олардың барлығы осы мәнді шығаруы керек.
  • Тоқтату: Барлық процестер ақырында шығыс мәні туралы шешім қабылдауы керек

Әлсіз интерактивті дәйектілік

Үшін n ішінара синхронды жүйедегі процестер (жүйе синхронияның жақсы және жаман кезеңдерін ауыстырып отырады), әр процесс жеке мәнді таңдайды. Процестер бір-бірімен дөңгелектер арқылы байланысып, қоғамдық құнды анықтайды және аксонсенс векторын жасайды:[7]

  1. егер дұрыс процесс жіберілсе , содан кейін барлық дұрыс процестер қабылданады немесе ештеңе (тұтастық қасиеті)
  2. Тура жолмен жіберілген барлық хабарламалар барлық айналымдармен (рационалдылық қасиеті) бір айналымда қабылданады.

Осы есептердің вариациялары эквивалентті болатынын көрсетуге болады, өйткені модельдің бір түріндегі есептің шешімі басқа типтегі есептің шешімі болуы мүмкін. Мысалы, синхронды аутентификацияланған хабарламаны жіберу үлгісіндегі әлсіз византиялық жалпы мәселені шешу әлсіз интерактивті консистенцияны шешуге әкеледі.[8] Интерактивті консистенция алгоритмі әр процесс өзінің консенсус векторындағы көпшілік мәнін өзінің консенсус мәні ретінде таңдау арқылы консенсус мәселесін шеше алады.[9]

Келісімнің кейбір проблемалары үшін шешімділік нәтижелері

Шешетін t-серпімді анонимді синхронды хаттама бар Византия генералдары проблемасы,[10][11] егер және әлсіз Византия генералдары ісі[8] қайда - бұл сәтсіздіктер саны және процестердің саны.

Жүйелері үшін оның ішінде процессорлар Византия болса, консенсус мәселесін шешетін алгоритм жоқ екендігі дәлелденді ішінде ауызша хабарламалар моделі.[12] Дәлел алдымен үш түйінді корпустың мүмкін еместігін көрсету арқылы жасалады және осы нәтижені процессорлардың бөлімдері туралы таласу үшін қолдану. Ішінде жазбаша хабарламалар моделі шыдай алатын протоколдар бар .[2]

Толығымен асинхронды жүйеде бір ғана немесе бірнеше апаттардың сәтсіздіктеріне төзімділікке ие болатын келісімді шешім жоқ, бұл тек маңызды емес қасиеттерді қажет етеді.[5] Бұл нәтиже кейде авторлардың атымен FLP мүмкін еместігі деп аталады Майкл Дж. Фишер, Нэнси Линч, және Майк Патерсон кім марапатталды Дайкстра сыйлығы осы елеулі жұмыс үшін. FLP нәтижесі механикалық түрде тексеріліп, тіпті астында болуы мүмкін әділеттілік туралы болжамдар.[13] Алайда, FLP консенсусқа ешқашан қол жеткізуге болмайтындығын айтпайды: тек модельдің жорамалдары бойынша ешбір алгоритм әрдайым белгілі бір уақытта консенсусқа келе алмайды. Іс жүзінде оның пайда болуы екіталай.

Кейбір консенсус хаттамалары

The Паксо консенсус алгоритмі бойынша Лесли Лампорт, және оның нұсқалары Сал, кең таралған жерлерде кеңінен қолданылады таратылды және бұлтты есептеу жүйелер. Бұл алгоритмдер синхронды болып табылады, алға басуға сайланған көшбасшыға тәуелді және тек апаттарға төзеді, византиялықтардың сәтсіздіктеріне жол бермейді.

Византия сәтсіздіктеріне жол беретін уақыттық екілік консенсус хаттамасының мысалы - Phase King алгоритмі.[14] Гарай мен Берман. Алгоритм синхронды хабарлама жіберетін модельде консенсус шешеді n процестер және дейін f ақаулар, қарастырылған n > 4f.Фазалық патша алгоритмінде бар f + 1 фаза, фазаға 2 айналымнан тұрады.Әр процесс өзінің артықшылықты шығынын қадағалайды (бастапқыда процестің өзіндік мәніне тең). Әр фазаның бірінші айналымында әрбір процесс барлық басқа процестерге өзінің артықшылықты мәнін ұсынады. Содан кейін ол барлық процестерден мәндерді қабылдайды және қай мән көпшілік мән екенін және оның есебін анықтайды. Фазаның екінші айналымында идентификаторы ағымдағы фаза санына сәйкес келетін процесс фазаның патшасы болып белгіленеді. Патша бірінші раундта байқалған көпшілік мәнді таратады және галстукты бұзады. Содан кейін әрбір процесс өзінің артықшылықты мәнін келесідей жаңартады. Егер көпшілік мәнінің саны бірінші айналымда байқалатын процесс үлкен болса n/2 + f, процесс өзінің басымдықты сол көпшілік мәніне өзгертеді; әйтпесе фаза патшасының мәнін қолданады. Соңында f + 1 фаза процестердің артықшылықты мәндерін шығарады.

Google компаниясы таратылған құлыптау қызметі кітапхана деп аталады Томби.[15] Чубби сәтсіздіктер кезінде жоғары қол жетімділікке жету үшін қайталанатын мәліметтер базасында сақталатын кішігірім файлдардағы құлып туралы ақпаратты сақтайды. Деректер базасы ақауларға төзімді журнал деңгейінің негізінде жүзеге асырылады Paxos консенсус алгоритмі. Бұл схемада Chubby клиенттері Paxos-пен байланысады шебер қайталанатын журналға қол жеткізу / жаңарту үшін; яғни файлдарды оқу / жазу.[16]

Интернеттегі көптеген құрдастар Нақты уақыттағы стратегия ойындар модификацияланған қолданады Lockstep протоколы ойындағы ойын жағдайын басқару мақсатында консенсус хаттамасы ретінде. Әрбір ойын әрекеті ойынның барлық басқа ойыншыларына жалпы ойын күйінің хэшімен бірге таратылатын ойын күйіндегі дельтаға әкеледі. Әрбір ойыншы өзгерісті дельтаны өздерінің ойын күйіне қолдану және ойын күйінің хэштерін салыстыру арқылы растайды. Егер хэштер келіспесе, онда дауыс беріледі, ал ойын жағдайы аз болған ойыншылар ажыратылады және ойыннан шығарылады (десинк деп аталады).

Тағы бір танымал тәсіл информатикадан теорияны басқару үшін кеңінен қолданылған MSR типті алгоритмдер деп аталады.[17][18][19]

ДереккөзСинхронизмАутентификацияТабалдырықДөңгелекЕскертулер
Пиз-Шостак-Лампорт [10]СинхрондыАуызшажалпы байланыс
Пиз-Шостак-Лампорт [10]СинхрондыЖазбашажалпы байланыс
Бен-Ор [20]АсинхрондыАуызша (күтілетін)күткен раундтар қашан
Долев және басқалар. [21]СинхрондыАуызшажалпы байланыс
Долев-Стронг [2]СинхрондыЖазбашажалпы байланыс
Долев-Стронг [2]СинхрондыЖазбашажалпы байланыс
Фельдман-Микали [22]СинхрондыАуызша (күтілетін)
Катц-Коо [23]СинхрондыЖазбаша (күтілетін)PKI талап етеді
PBFT [24]Асинхронды (қауіпсіздік) - синхронды (тіршілік)Ауызша
HoneyBadger [25]АсинхрондыАуызша (күтілетін)tx байланысына - ашық кілтпен шифрлауды қажет етеді
Ибраһим және басқалар [26]СинхрондыЖазбаша
Византия келісімі маңызды емес [27] [28]СинхрондыҚолтаңбалар (күтілетін)ЭЦҚ қажет

Рұқсатсыз консенсус хаттамалары

Bitcoin қолданады жұмыс дәлелі ашық жерде рұқсатсыз келісімге қол жеткізу пиринг жүйесі желі. Bitcoin-ді кеңейту үшін блокчейн немесе таратылған кітап, кеншілер шешім табу ықтималдығы секундына хэшке жұмсалған есептеу күшіне пропорционалды болатын криптографиялық басқатырғышты шешуге тырысады. Мұндай жұмбақты бірінші рет шешетін торапта олардың транзакциялардың келесі блогының ұсынылған нұсқасы кітапқа қосылып, соңында барлық басқа түйіндер қабылдады. Желідегі кез-келген түйін жұмыс дәлелі мәселесін шешуге тырысатындықтан, а Сибил шабуылы егер шабуылдаушыда желінің есептеу ресурстарының 50% -дан астамы болмаса, негізінен мүмкін емес.

Басқа криптовалюталар (яғни DASH, NEO, STRATIS, ...) қолданады үлестің дәлелі, онда түйіндер блоктарды қосуға және сәйкесінше сыйақы алуға пропорционалды түрде жарысқа түседі баған, немесе бар криптовалюта бөлінген және құлыпталған немесе ставка біраз уақыт аралығында. «Жұмыс дәлелі» жүйесімен салыстырғанда «үлесті дәлелдеудің» бір артықшылығы, ең болмағанда қазіргі заманғы технологиямен талап етілетін жоғары энергия шығыны. Мысал ретінде Bitcoin тау-кен өндірісі (2018) Чехияның немесе Иорданияның бүкіл халықтарына ұқсас мөлшерде жаңартылмайтын энергия көздерін тұтынады деп есептеледі.[29]

Ripple сияқты кейбір криптовалюталар кітапты растау үшін түйіндерді тексеру жүйесін пайдаланады, бұл Ripple қолданатын Ripple Protocol Consensus Algorithm (RPCA) деп аталатын бұл жүйе айналымдарда жұмыс істейді: 1-қадам: әрбір сервер жарамды үміткерлердің транзакциялар тізімін жасайды; 2-қадам: әр сервер өзінің бірегей түйіндер тізімінен (UNL) шыққан барлық үміткерлерді біріктіреді және олардың дұрыстығына дауыс береді; 3-қадам: ең төменгі шекті деңгейден өткен транзакциялар келесі турға өтеді; 4-қадам: round nal турға 80% келісім қажет[30]

Рұқсат етілмеген консенсус хаттамаларында қолданылатын басқа қатысу ережелері кіруге арналған кедергілер және қарсыласу sybil шабуылдары қосу беделінің дәлелі, кеңістіктің дәлелі, күйіктің дәлелі немесе өткен уақыттың дәлелі. Бұл баламалар қайтадан негізінен жұмысты дәлелдеуге жұмсалатын есептеу энергиясының көп мөлшеріне негізделген.[31] Сыйымдылығын дәлелдеуді Burstcoin сияқты криптокоиндер қолданады.

Жоғарыда аталған қатысуға рұқсат етілмеген ережелерден айырмашылығы, олардың барлығы қатысушыларды қандай-да бір іс-әрекетке немесе ресурстарға салынған инвестиция көлеміне пропорционалды түрде марапаттайды; жеке тұлғаның дәлелі Протоколдар әрбір нақты қатысушыға экономикалық инвестицияға қарамастан рұқсат етілген консенсус бойынша дауыс беру күшінің дәл бір бірлігін беруге бағытталған.[32][33] Жеке тұлғаны дәлелдеу үшін консенсус күшін бір адамға бөлуге қол жеткізуге ұсынылатын тәсілдерге физикалық бүркеншік партиялар жатады;[34] әлеуметтік желілер,[35] лақап аты бар үкімет берген сәйкестік,[36] және биометрия.[37]

Ортақ жадының консенсус хаттамалары

Ортақ жад жүйесіндегі консенсус мәселесін шешу үшін қатар объектілерді енгізу қажет. Параллельді объект немесе ортақ объект - бұл бір уақытта жүретін процестердің келісімге келуіне көмектесетін мәліметтер құрылымы.

Мұндай параллельді нысанды жобалаудың екі негізгі әдісі бар. Дәстүрлі түрде дизайнерлер пайдаланады маңызды бөлім бұл мәселені шешу үшін, бір уақытта бір уақытта қатар жүретін объектіге тек бір процеске баруға рұқсат етіледі, ал басқалары бұл процесс сыни бөлімнен шыққанша күтуі керек дегенді білдіреді. Бұл әдіс қарапайым және оны қолдану оңай. Алайда, сыни бөлімдері бар жүйелер, егер кейбір процестер сыни бөлік ішінде өлсе немесе ұзақ уақыт ұйықтаса, бұзылу қаупі бар.

Параллельді объектінің тағы бір іске асырылуы күтусіз іске асыру деп аталады, ол шектеулі қадамдарда консенсусқа кепілдік бере алады. Берілген объект түрі консенсус мәселелерін шешуге жеткілікті ме? Морис Херлихи «мүмкін емес және әмбебаптық иерархиясын» берді.[38]

Консенсус нөміріНысандар
Тіркелімдерді оқу / жазу
сынау және орнату, ауыстыру, алу және қосу, кезек, стек
......
n-регистрді тағайындау
......
Жадтан жадыға ауыстыру және ауыстыру, кеңейтілген кезек, салыстыру және ауыстыру, алу және минус, жабысқақ байт

Иерархиядағы консенсус саны - бұл берілген объектіде консенсусқа жете алатын жүйедегі процестердің максималды саны. Консенсус саны жоғары объектілерді консенсус саны төмен объектілер жүзеге асыра алмайды.

Иерархияға сәйкес оқу / жазу регистрлері 2 процессті жүйеде де консенсус шеше алмайды. Стек, кезек және тағы басқалар сияқты мәліметтер құрылымы тек екі процесс арасындағы консенсус шеше алады. Неліктен бұл объектілер көп процестер арасындағы консенсус шеше алмайды? Мұны дәлелдеудің тиімді тәсілі - биваленттіліктің артықшылығын пайдалану. Шығарылым екілік деп есептейік, егер екі шығудың екеуі де мүмкін болса, күй екі валентті болады, ал егер күйден шығатын нәтиже тек 0/1 болса, күй 0 валентті / 1 валентті деп аталады. Негізгі идея - 0 валентті және 1 валентті күйді алу үшін кейбір амалдарды орындау арқылы қарама-қайшылық жасау.

Алайда, кейбір параллель объектілер әмбебап болып табылады, яғни олар кез-келген процестердің арасында консенсус шеше алады және кез-келген басқа объектілерді имитациялай алады. Басқа объектілерді әмбебап нысандармен модельдеу тәсілі осы қатар объектімен амалдар тізбегін құру болып табылады.[38]

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ а б c Кулурис, Джордж; Жан Доллимор; Тим Киндберг (2001), Таратылған жүйелер: тұжырымдамалар және дизайн (3-шығарылым), Аддисон-Уэсли, б. 452, ISBN  978-0201-61918-8
  2. ^ а б c г. Долев Д .; Strong, HR (1983). «Византия келісімінің расталған алгоритмдері». Есептеу бойынша SIAM журналы. 12 (4): 656–666. дои:10.1137/0212045.
  3. ^ Гонг, Ли; Линкольн, Патрик; Рашби, Джон (1995). «Аутентификациясы бар византиялық келісім». Сыни қосымшаларға арналған сенімді есептеу. 10.
  4. ^ а б Агилера, М.К (2010). «Консенсус зерттеуіне сүріну: түсінбеушіліктер мен мәселелер». Репликация. Информатика пәнінен дәрістер. 5959. 59-72 бет. дои:10.1007/978-3-642-11294-2_4. ISBN  978-3-642-11293-5.
  5. ^ а б Фишер, Дж. Дж.; Линч, Н.; Патерсон, М.С. (1985). «Бір ақаулы процесстің таратылған консенсусының мүмкін еместігі» (PDF). ACM журналы. 32 (2): 374–382. дои:10.1145/3149.214121. S2CID  207660233.
  6. ^ Aspnes, James (мамыр 1993). «Уақыт пен кеңістікті тиімді кездейсоқ консенсус». Алгоритмдер журналы. 14 (3).
  7. ^ Милошевич, Зарко; Мартин Хатл; Андре Шипер (2009). Византиялық консенсус алгоритмдерін әлсіз интерактивті дәйектілікпен біріктіру. Таратылған жүйелердің принциптері, информатикадағы дәрістер. Информатика пәнінен дәрістер. 5293. бет.300–314. CiteSeerX  10.1.1.180.4229. дои:10.1007/978-3-642-10877-8_24. ISBN  978-3-642-10876-1.
  8. ^ а б Лампорт, Л. (1983). «Византия генералдарының әлсіз проблемасы». ACM журналы. 30 (3): 668. дои:10.1145/2402.322398. S2CID  1574706.
  9. ^ Фишер, Майкл Дж. «Сенімсіз таратылған жүйелердегі консенсус мәселесі (қысқаша сауалнама») (PDF). Алынған 21 сәуір 2014.
  10. ^ а б c Лампорт, Л.; Шостак, Р .; Пиз, М. (1982). «Византия генералдары проблемасы» (PDF). Бағдарламалау тілдері мен жүйелері бойынша ACM транзакциялары. 4 (3): 382–401. CiteSeerX  10.1.1.64.2312. дои:10.1145/357172.357176.
  11. ^ Лампорт, Лесли; Маршалл Пийз; Роберт Шостак (1980 ж. Сәуір). «Ақаулар болған кезде келісімге келу» (PDF). ACM журналы. 27 (2): 228–234. CiteSeerX  10.1.1.68.4044. дои:10.1145/322186.322188. S2CID  6429068. Алынған 2007-07-25.
  12. ^ Аттия, Хагит (2004). Таратылған есептеу 2-ші басылым. Вили. 101–103 бет. ISBN  978-0-471-45324-6.
  13. ^ Биспинг, Бенджамин; т.б. (2016), Бланшетт, Жасмин Кристиан; Мерц, Стефан (ред.), FLP үшін конструктивті дәлелдеуді механикалық тексеру, Информатикадағы дәрістер, 9807, Springer International Publishing, дои:10.1007/978-3-319-43144-4_7, ISBN  978-3-319-43144-4
  14. ^ Берман, Пиотр; Хуан А. Гарай (1993). «Дауыс беру дауыстары: n + 4-төзімді, t + 1 раундтар бойынша таратылған консенсус». Есептеу жүйелерінің теориясы. 2. 26: 3–19. дои:10.1007 / BF01187072. S2CID  6102847.
  15. ^ Берроуз, М. (2006). Кең таралған жүйелерге арналған Chubby lock қызметі (PDF). 7-ші еңбек Операциялық жүйелерді жобалау және енгізу бойынша симпозиум. USENIX қауымдастығы Беркли, Калифорния, АҚШ. 335–350 бб.
  16. ^ C., Тушар; Гриземер, Р; Redstone J. (2007). Paxos Live Live - инженерлік перспектива (PDF). Жиырма алтыншы жылдық ACM материалдары Таратылған есептеу принциптері туралы симпозиум. Портленд, Орегон, АҚШ: ACM Press Нью-Йорк, Нью-Йорк, АҚШ. 398–407 беттер. дои:10.1145/1281100.1281103. Архивтелген түпнұсқа (PDF) 2014-12-12. Алынған 2008-02-06.
  17. ^ LeBlanc, Heath J. (сәуір, 2013). «Қуатты желілердегі асимптотикалық консенсус». IEEE журналы байланыс саласындағы таңдаулы аймақтар туралы. 31 (4): 766–781. CiteSeerX  10.1.1.310.5354. дои:10.1109 / JSAC.2013.130413. S2CID  11287513.
  18. ^ Dibaji, S. M. (мамыр 2015). «Жергілікті шектелген ақаулар болған кезде екінші ретті көп агенттік жүйелердің консенсусы». Жүйелер және басқару хаттары. 79: 23–29. дои:10.1016 / j.sysconle.2015.02.005.
  19. ^ Dibaji, S. M. (шілде 2017). «Екінші ретті агент желілерінің тұрақты консенсусы: кідірістермен асинхронды жаңарту ережелері». Automatica. 81: 123–132. arXiv:1701.03430. Бибкод:2017arXiv170103430M. дои:10.1016 / j.automatica.2017.03.008. S2CID  7467466.
  20. ^ Бен-Ор, Майкл (1983). «Еркін таңдаудың тағы бір артықшылығы (кеңейтілген реферат): келісімнің толық асинхронды хаттамалары»: 27-30. дои:10.1145/800221.806707. S2CID  38215511. Журналға сілтеме жасау қажет | журнал = (Көмектесіңдер)
  21. ^ Долев, Дэнни; Фишер, Майкл Дж.; Фаулер, Роб; Линч, Нэнси; Strong, H. Raymond (1982). «Византия келісімінің аутентификациясы жоқ тиімді алгоритмі». Ақпарат және бақылау. 52 (3): 257–274. дои:10.1016 / S0019-9958 (82) 90776-8.
  22. ^ Фельдман, Песех; Микали, Сильвио (1997). Синхронды Византия келісіміне арналған ықтимал ықтимал хаттама. Есептеу бойынша SIAM журналы (Техникалық есеп). дои:10.1137 / S0097539790187084.
  23. ^ Катц, Джонатан; Коо, Чиу-Юэн (2006). Византия келісіміне күтілетін тұрақты дөңгелек хаттамалар туралы. CRYPTO. дои:10.1007/11818175_27.
  24. ^ Кастро, Мигель; Лисков, Барбара (1999). Практикалық византиялық ақауларға төзімділік (PDF). OSDI.
  25. ^ Миллер, Эндрю; Ся, Ю; Кроман, Кайл; Ши, Элейн; Ән, Таң (2016). BFT протоколдарының бал борсықтары. ОКҚ. дои:10.1145/2976749.2978399.
  26. ^ Ыбырайым, Итай; Девадас, Шринивас; Долев, Дэнни; Наяк, Картик; Рен, Линг (2017). Византияның тиімді синхронды консенсусы (Техникалық есеп).
  27. ^ Micali, Sylvio (2018). «Византия келісімі маңызды емес» (PDF).
  28. ^ Чен, Джин; Мики, Сильвио. «АЛГОРАНД». arXiv:1607.01341v9.
  29. ^ Ирфан, Умайыр (18.06.2019). «Биткоин - бұл энергетикалық шошқа. Барлық электр энергиясы қайдан келеді?». Vox.
  30. ^ Schwartz D, YoungsN, Britto A. 2014 Ripple протоколының консенсус алгоритмі
  31. ^ Жұмысты дәлелдеудің қандай баламалы стратегиялары бар?
  32. ^ Мария Борге, Элефтериос Кокорис-Когиас, Филипп Йованович, Линус Гассер, Николас Гейли, Брайан Форд (29 сәуір 2017). Жеке тұлғаны дәлелдеу: рұқсатсыз криптовалюталарды қайта демократияландыру. IEEE қауіпсіздігі және блокчейндегі құпиялылық (IEEE S&B).CS1 maint: авторлар параметрін қолданады (сілтеме)
  33. ^ Дивя Сиддарт, Сергей Ивлиев, Сантьяго Сири, Паула Берман (13 қазан 2020). «Күзетшілерді кім бақылайды? Жеке тұлға хаттамаларын дәлелдеуде Сибилге төзімділіктің субъективті тәсілдеріне шолу». arXiv:2008.05300.CS1 maint: авторлар параметрін қолданады (сілтеме)
  34. ^ Форд, Брайан; Штраус, Джейкоб (1 сәуір 2008). Интернеттегі есеп беретін лақап есімдерге арналған қор. Әлеуметтік желілік жүйелер бойынша бірінші семинар - SocialNets '08. 31-6 бет. дои:10.1145/1435497.1435503. ISBN  978-1-60558-124-8.
  35. ^ Гал Шахаф, Эхуд Шапиро, Нимрод Талмон (қазан 2020). Sybil-төзімді қоғамдастықтың өсуіне арналған шынайы жеке идентификаторлар және өзара кепілдіктер. Әлеуметтік информатика бойынша халықаралық конференция.CS1 maint: авторлар параметрін қолданады (сілтеме)
  36. ^ Дипак Марам, Харджаслин Мальвай, Фан Чжан, Нерла Жан-Луи, Александр Фролов, Тайлер Келл, Тайрон Лоббан, Кристин Мой, Ари Хуэлс, Эндрю Миллер (28 қыркүйек 2020). «CanDID: орталықтандырылмаған сәйкестікті бұрынғы үйлесімділікпен, Sybil-қарсылықпен және есептілікпен жасай алады» (PDF).CS1 maint: авторлар параметрін қолданады (сілтеме)
  37. ^ Мохаммад-Джавад Хаджалихани, Мохаммад-Махди Джаханара (20.06.2018). «UniqueID: адамның орталықтандырылмаған дәлелі» (PDF). arXiv:1806.07583.CS1 maint: авторлар параметрін қолданады (сілтеме)
  38. ^ а б Херлихи, Морис. «Күтусіз синхрондау» (PDF). Алынған 19 желтоқсан 2011.

Әрі қарай оқу