Исследование алгоритмов принятия консенсуса в сети ненадежных вычислителей (1187400), страница 4
Текст из файла (страница 4)
Âûáîðùèê ïîëó÷àåò Accept çàïðîñ äëÿ ïðåäëîæåíèåì ñ íîìåðîìN, îí ïðèíèìàåò ïðåäëîæåíèå åñëè òîëüêî íå îòâå÷àë íà Prepareçàïðîñ ñ íîìåðîì, áîëüøèì N23Èíèöèàòîð ìîæåò ñäåëàòü íåñêîëüêî ïðåäëîæåíèé, òîëüêî åñëè äëÿêàæäîãî èç íèõ îí ñëåäóåò ýòîìó àëãîðèòìó. Èíèöèàòîð òàêæå ìîæåòîòêàçàòüñÿ îò ïðåäëîæåíèÿ â ëþáîé ìîìåíò âðåìåíè. Òàêæå, èíèöèàòîðóñëåäóåò îòêàçûâàòüñÿ îò ïðåäëîæåíèÿ, åñëè êàêîé-òî äðóãîé èíèöèàòîðñäåëàë ïðåäëîæåíèå ñ áîëüøèì íîìåðîì. Òàêèì îáðàçîì, åñëè âûáîðùèêèãíîðèðóåò Prepare èëè Accept çàïðîñ (òàê êàê îí óæå ïîëó÷èë Prepareèëè Accept çàïðîñ ñ áîëüøèì íîìåðîì), îí ìîæåò ïðîèíôîðìèðîâàòü îáýòîì èíèöèàòîðà, êîòîðûé â ýòîì ñëó÷àå äîëæåí îòêàçàòüñÿ îò ñâîåãîïðåäëîæåíèÿ.
Ýòî ïîâûøàåò ýôôåêòèâíîñòü àëãîðèòìà, íî íå âëèÿåò íàåãî êîððåêòíîñòü.3.3Ïîëó÷åíèå èíôîðìàöèè î ïðèíÿòîì ðåøåíèèÄëÿ òîãî, ÷òîáû ïîíÿòü, ÷òî ïî êàêîìó-òî ðåøåíèþ äîñòèãíóò êîíñåíñóñ, èñïîëíèòåëü äîëæåí óáåäèòüñÿ ÷òî îíî áûëî ïðèíÿòî áîëüøèíñòâîìâûáîðùèêîâ. Î÷åâèäíûé àëãîðèòì - êàæäûé âûáîðùèê, êîãäà áû îí íèïîëó÷èë ïðåäëîæåíèå, êîòîðîå îí ðåøèë ïðèíÿòü, ïåðåñûëàåò ïðèíÿòîå ðåøåíèå âñåì èñïîëíèòåëÿì. Ýòî ïîçâîëÿåò èñïîëíèòåëÿì óçíàòü îâûáðàííîì ïðåäëîæåíèè, êàê òîëüêî îíî áûëî ïðèíÿòî. Òàêæå ýòî òðåáóåò îò âûáîðùèêà êîììóíèöèðîâàòü ñ êàæäûì èñïîëíèòåëåì, òàêèìîáðàçîì êàæäîå âûáðàííîå ïðåäëîæåíèå áóäåò ãåíåðèðîâàòü êîëè÷åñòâîñîîáùåíèé, ïðîïîðöèîíàëüíîå ïðîèçâåäåíèþ êîëè÷åñòâà âûáîðùèêîâ íàêîëè÷åñòâî èñïîëíèòåëåé.Ïðåäïîëîæåíèå îá îòñóòñòâèè îøèáîê âèçàíòèéñêîãî òèïà â ñðåäåïåðåäà÷è ñîîáùåíèé ïîçâîëÿåò îäíîìó èñïîëíèòåëþ äîâåðÿòü èíôîðìàöèè, ïîëó÷åííîé îò äðóãîãî èñïîëíèòåëÿ. Èíûìè ñëîâàìè, èñïîëíèòåëü24ìîæåò óçíàòü îò äðóãîãî èñïîëíèòåëÿ, ÷òî îïðåäåë¼ííîå ïðåäëîæåíèåáûëî ïðèíÿòî.
Âûáîðùèêè ìîãóò èíôîðìèðîâàòü î ñâîèõ ðåøåíèÿõ èçáðàííîãî èñïîëíèòåëÿ, êîòîðûé, â ñâîþ î÷åðåäü, ïðîèíôîðìèðóåò âñåõîñòàëüíûõ â òîò ìîìåíò, êîãäà îïðåäåëèò, ÷òî êîíñåíñóñ áûë äîñòèãíóò.Ýòîò ïîäõîä òðåáóåò äîïîëíèòåëüíûõ îáìåíîâ ñîîáùåíèÿìè, è, ñëåäîâàòåëüíî, âíåñåò çàäåðæêè äëÿ âñåõ èñïîëíèòåëåé. Ýòî òàêæå ìåíåå íàä¼æíî, òàê êàê èçáðàííûé èñïîëíèòåëü ìîæåò àâàðèéíî îñòàíîâèòñÿ.Îäíàêî, ýòîò ïîäõîä ýêîíîìèò êîëè÷åñòâî ïåðåñûëàåìûõ ñîîáùåíèé îíî ïðîïîðöèîíàëüíî ñóììå êîëè÷åñòâà âûáîðùèêîâ è êîëè÷åñòâà èñïîëíèòåëåé. îáùåì ñëó÷àå, âûáîðùèêè ìîãóò èíôîðìèðîâàòü î ñâîèõ ðåøåíèÿõíåêîòîðîå ôèêñèðîâàííîå ìíîæåñòâî èçáðàííûõ èñïîëíèòåëåé, êàæäûéèç êîòîðûõ â äàëüíåéøåì ïðîèíôîðìèðîâàë áû îñòàëüíûõ èñïîëíèòåëåéî ïðèíÿòîì ðåøåíèè. Ðàñøèðåíèå ìíîæåñòâà èçáðàííûõ èñïîëíèòåëåéïîâûøàåò íàä¼æíîñòü ñèñòåìû, íî óâåëè÷èâàåò êîëè÷åñòâî ïåðåñûëàåìûõ ñîîáùåíèé. óñëîâèÿõ âîçìîæíûõ ïîòåðü ñîîáùåíèé íåêîòîðîå çíà÷åíèå ìîæåòáûòü âûáðàíî, íî ïðè ýòîì íè îäèí èñïîëíèòåëü îá ýòîì íèêîãäà íå óçíàåò, òàê êàê ñîîòâåòñòâóþùèå ñîîáùåíèÿ áûëè ïîòåðÿíû.
Èñïîëíèòåëü,òàêèì îáðàçîì, äîëæåí èìåòü âîçìîæíîñòü óçíàòü îò âûáîðùèêîâ êàêèåðåøåíèé îíè ïðèíÿëè, íî îòêàç âûáîðùèêà ìîæåò ñäåëàòü ýòî äåéñòâèåíåîñóùåñòâèìûì.Âñëåäñòâèå ýòîãî, â ñëó÷àå îòêàçà âûáîðùèêà, íåò ñïîñîáà óçíàòü, ÷òîðåøåíèå ïðèíÿòî áîëüøèíñòâîì. Åñëè èñïîëíèòåëþ íåîáõîäèìî óçíàòüî êîíêðåòíîì ïðåäëîæåíèè, áûëî ëè îíî ïðèíÿòî, èëè íåò, îí ìîæåòïîïðîñèòü èíèöèàòîðà ñäåëàòü ïðåäëîæåíèå î ïðèíÿòèè ýòîãî ðåøåíèÿ,èñïîëüçóÿ àëãîðèòìà, îïèñàííîãî âûøå.25S1 P 3.1A 3.1 X P 4.1A 4.1 XS2 P 3.1A 3.1 X P 4.1A 4.1 XS3 P 3.1 P 3.5 A 3.1 X P 4.1 A 3.5 Y P 5.5 A 4.1 XP 3.5A 3.5 Y P 5.5S4A 3.5 Y P 5.5S5P 3.5timeÐèñ.
3.3: Êîíêóðèðóþùèå èíèöèàòîðû ïîãóò ñîçäàòü ñèòóàöèþ âçàèìîáëîêèðîâêè.3.4Îáðàáîòêà ñèòóàöèè âçàèìîáëîêèðîâêèÑóùåñòâóåò ñöåíàðèé, â êîòîðîì åñòü äâà èíèöèàòîðà, êîòîðûå äåëàþò ïðåäëîæåíèÿ ñ óâåëè÷èâàþùèìèñÿ íîìåðàìè, è íè îäíî èç ýòèõïðåäëîæåíèé íå ìîæåò áûòü ïðèíÿòî. Èíèöèàòîð S1 çàâåðøàåò ôàçó 1ïðåäëîæåíèÿ N1.
Ïîñëå ýòîãî, äðóãîé èíèöèàòîð S5 çàâåðøàåò ôàçó 1ïðåäëîæåíèÿ N2 (N2 > N1). Èíèöèàòîð S1 ïåðåõîäèò â ôàçó 2 è ïîñûëàåò Accept çàïðîñû, íî îíè èãíîðèðóþòñÿ, òàê êàê âûáîðùèêè óæåïîîáåùàëè íå ïðèíèìàòü ïðåäëîæåíèÿ ñ íîìåðàìè ìåíüøèìè N2. Íåèìåÿ êîíñåíñóñà, èíèöèàòîð S1 çàíîâî íà÷èíàåò ôàçó 1 äëÿ ïðåäëîæåíèÿ ñ íîìåðîì N3 (N3 > N2), è óñïåâàåò çàâåðøèòü å¼, òàêèì îáðàçîìïðåïÿòñòâóÿ êîíñåíñóñó ïî ðåøåíèþ N2. Ïîäîáíàÿ ïîñëåäîâàòåëüíîñòüñîáûòèé ìîæåò ïðîäîëæàòüñÿ íåîãðàíè÷åííî äîëãî, ñîçäàâàÿ ñèòóàöèþâçàèìîáëîêèðîâîê.Îäèí èç ñïîñîáîâ èçáåæàòü ýòîé ñèòóàöèè ñîñòîèò â òîì, ÷òîáû äîáàâèòü ñëó÷àéíóþ çàäåðæêó ïåðåä ïîïûòêîé çàíîâî íà÷àòü ôàçó 1 äëÿïðåäëîæåíèÿ ââèäó îòñóñòâèÿ êîíñåíñóñà, ÷òîáû ïîçâîëèòü çàâåðøèòüñâîé ðàóíä ãîëîñîâàíèÿ äðóãèì èíèöèàòîðàì.Äðóãîé âàðèàíò èçáåæàòü ýòèõ ñèòóàöèé ñîñòîèò â òîì, ÷òîáû òîëüêî èçáðàííûé èíèöèàòîð äîëæåí èñïîëüçîâàòüñÿ äëÿ ñîçäàíèÿ ïðåäëîæåíèé.
Åñëè èçáðàííûé èíèöèàòîð ìîæåò óñïåøíî êîììóíèöèðîâàòü ñ26áîëüøèíñòâîì âûáîðùèêîâ, è îí èñïîëüçóåò ïðåäëîæåíèÿ ñ íîìåðàìèáîëüøèìè, ÷åì îí êîãäà-ëèáî óæå èñïîëüçîâàë, òîãäà îí ïðåóñïååò è âäîñòèæåíèè êîíñåíñóñà ïî íîâîìó ïðåäëîæåíèþ.  ñëó÷àå, åñëè èçáðàííûé èíèöèàòîð óçíàåò î çàïðîñå ñ áîëüøèì íîìåðîì, îí ìîæåò îòêàçàòüñÿ îò ïðåäëîæåíèÿ, è â êîíöå êîíöîâ âûáðàòü ïðåäëîæåíèå ñ áîëüøèìíîìåðîì.Åñëè äîñòàòî÷íàÿ ÷àñòü ïðîöåññîâ ñèñòåìû (èíèöèàòîðû, âûáîðùèêè, ñåòü) ôóíêöèîíàëüíû, æèâó÷åñòü ñèñòåìû ìîæåò áûòü äîñòèãíóòàïîñðåäñòâîì ïðîöåäóðû âûáîðîâ èçáðàííîãî èíèöèàòîðà.3.5Îñîáåííîñòè ðåàëèçàöèèPaxos ïðåäïîëàãàåò, ÷òî âçàèìîäåéñòâóþùèå ïðîöåññû îáúåäèíåíû âñåòü.
 àëãîðèòìå êîíñåíñóñà êàæäûé ïðîöåññ èãðàåò ðîëü èíèöèàòîðà, âûáîðùèêà èëè èñïîëíèòåëÿ. Àëãîðèòì âûáèðàåò ëèäåðà, êîòîðûéèãðàåò ðîëü èçáðàííîãî èíèöèàòîðà è èçáðàííîãî èñïîëíèòåëÿ.  àëãîðèòìàõ Paxos çàïðîñû è îòâåòû ïîñûëàþòñÿ â âèäå îáû÷íûõ ñîîáùåíèé,à îòâåòû íà çàïðîñû äîëæíû ñîäåðæàòü ñîîòâåòñòâóþùèé íîìåð ïðåäëîæåíèÿ, ÷òîáû èçáåæàòü ïóòàíèöû â ñëó÷àå îáðàáîòêè ñðàçó íåñêîëüêèõçàïðîñîâ.
Òàêæå, íåêîòîðûå ïåðåìåííûå íóæíî õðàíèòü ïåðñèñòåíòíî,òàê êàê â ïðîòèâíîì ñëó÷àå ïðè àâàðèéíîì îòêàçå ìîãóò âîçíèêíóòü ñèòóàöèè, íàðóøàþùèå èíâàðèàíòû, íà îñíîâàíèè êîòîðûõ ðàáîòàåò Paxos.Íàïðèìåð, ïåðåä îòïðàâêîé îòâåòà íà çàïðîñ âûáîðùèê îáÿçàí çàïèñàòüâûáðàííîå èì çíà÷åíèå â ïåðñèñòåíòíîå õðàíèëèùå.273.6Ïåðåõîä îò Single-Paxos ê Multi-PaxosÏðåäìåòîì ðàññìîòðåíèÿ âûøå áûë àëãîðèòì ïðèíÿòèÿ êîíñåíñóñàòîëüêî ïî îäíîìó âîïðîñó, òàê íàçûâàåìûé Single-Paxos. Òåïåðü, èñïîëüçóÿ ýòîò àëãîðèòì â êà÷åñòâå áàçîâîãî, áóäåò îïèñàí àëãîðèòì äëÿ âåäåíèÿ ðåïëèöèðîâàííîãî æóðíàëà â êîíòåñòå çàäà÷è ðàñïðåäåëåííîãî êîíå÷íîãî àâòîìàòà.
Ýòî àëãîðèòì íàçûâàåòñÿ Multi-Paxos.Åñëè Single-Paxos ðåøàåò çàäà÷è òîãî, ÷òî êàêèå-òî ó÷àñòíèêè äîëæíû äîãîâîðèòñÿ î íåêîì îáùåì çíà÷åíèè, òî â Multi-Paxos âîçíèêàåòòàê æå åùå îäèí ó÷àñòíèê - êëèåíò, îò êîòîðîãî ïðèõîäÿò îïðåäåëåííûåçíà÷åíèÿ â êà÷åñòâå âàðèàíòîâ äëÿ ãîëîñîâàíèÿ. Òàêæå, êëèåíò äîëæåíèìåòü âîçìîæíîñòü óçíàòü, áûëî ëè åãî ðåøåíèå ïðèíÿòî êëàñòåðîì, èëèíåò. Êëèåíò òàê æå ìîæåò îòêàçàòü, ÷òî ìîæåò ïðèâåñòè ê ïðîáëåìå, ÷òîîí ìîæåò îêàçàòüñÿ â íåâåäåíüå îòíîñèòåëüíî òîãî, áûëî ëè åãî ðåøåíèåïðèíÿòî, èëè íåò.Áîëåå òîãî, êëèåíòîâ ìîæåò áûòü íåñêîëüêî, ýòî âûíóæäàåò èñïîëüçîâàòü ðåïëèöèðîâàííûé æóðíàë äëÿ óñòðàíåíèÿ âîçìîæíûõ ïðîòèâîðå÷èé - åñëè áû äëÿ ðàçíûõ êëèåíòîâ ïðîèçâîäèëèñü ïðîñòî ïàðàëëåëüíûå,íåçàâèñèìûå ãîëîñîâàíèÿ, ýòî ìîãëî áû ïðèâåñòè ê òîìó, ÷òî ïîðÿäîê ïîëó÷èâøèõñÿ ðåçóëüòàòîâ ãîëîñîâàíèé áûë áû íåñîãëàñîâàííûì äëÿ âñåãîêëàñòåðà. Èíà÷å ãîâîðÿ, äëÿ ÷àñòè ñåðâåðîâ ñíà÷àëî áûëî ïðîèçâåäåíîïðèíÿòèå A, çàòåì ïðèíÿòèå B, à äëÿ îñòàëüíîé ÷àñòè - íàîáîðîò.28known chosenjmp 1123sub 2S1movadd 9S2movadd 9S3movadd 94567retcmdretsub 2ret(a) Ðåïëåöèðîâàííûé æóðíàë äî ïðîöåäóðû âûáîðà èíäåêñà.1234S1movadd 9sub 2cmdS2movadd 9sub 2cmdS3movadd 9sub 2cmd5jmp 1jmp 1jmp 167retretret(b) Ðåïëåöèðîâàííûé æóðíàë ïîñëå ïðîöåäóðû âûáîðà èíäåêñà.Ðèñ.
3.4: Àëãîðèòì âûáîðà èíäåêñà äëÿ çàïèñè ïðåäëîæåíèÿ â ðåïëåöèðîâàííûéæóðíàë.Ñöåíàðèé ðàáîòû ðåïëèöèðîâàííîãî êîíå÷íîãî àâòîìàòà âûãëÿäèòñëåäóþùèì îáðàçîì:1. Êëèåíò ïîñûëàåò êîìàíäó äëÿ âûïîëíåíèÿ íà ñåðâåð;2. Èñïîëüçóÿ Paxos, ñåðâåð ðåïëèöèðóåò çàïðîñ êëèåíòà íà âñå ìà-øèíû, âñå êîìàíäû êîïèðóþòñÿ â ôèêñèðîâàííûõ äëÿ âñåõ ñåðâåðîâ ïîðÿäêå;3. Ñåðâåð äîæèäàåòñÿ ïðèíÿòèÿ ðåøåíèÿ ïî ïðåäûäóùèì çàïèñÿì âæóðíàëå, çàòåì ïðèìåíÿåò èõ, òàêèì îáðàçîì âûïîëíÿÿ ïðåäûäóùèå êîìàíäû êëèåíòîâ;4. Ñåðâåð ïðèìåíÿåò âûáðàííóþ êîìàíäó è âîçâðàùàåò ðåçóëüòàòêëèåíòó;29Äëÿ òîãî, ÷òîáû õðàíèòü êîìàíäû â ôèêñèðîâàííîì ãëîáàëüíîì ïîðÿäêå, êàæäîå ïðåäëîæåíèå äîëæíî èìåòü íîâóþ ïåðåìåííóþ - èíäåêñ âðåïëèöèðîâàííîì æóðíàëå. Îäíîé èç çàäà÷ àëãîðèòìà ÿâëÿåòñÿ îáåñïå÷åíèå óíèêàëüíîñòè ýòîãî çíà÷åíèÿ.Äëÿ ýòîãî, ïðåäïîëîæèì, ó íàñ åñòü èíèöèàòîð A.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
