Исследование алгоритмов принятия консенсуса в сети ненадежных вычислителей (1187400), страница 3
Текст из файла (страница 3)
Âûáîðùèê, â ñâîþ î÷åðåäü, íåìîæåò ïðèíÿòü áîëüøå äâóõ ïðåäëîæåíèé, òàê êàê èíà÷å ìîæåò âîçíèêíóòü ñèòóàöèÿ íàëè÷èÿ áîëüøèíñòâà ãîëîñîâ ïî áîëåå ÷åì îäíîìó14ïðåäëîæåíèþ.Ïðè ïîëó÷åíèè ïåðâîãî ïðåäëîæåíèÿ ó âûáîðùèêà íåò íèêàêîãî ñïîñîáà óçíàòü, áóäåò ëè îí ïîëó÷àòü ïðåäëîæåíèÿ â äàëüíåéøåì. Îñîáåííîýòà ïðîáëåìà àêòóàëüíà â ñðåäå, ãäå ñîîáùåíèå ìîæåò áûòü ïîòåðÿíî.Òàêæå, ðåøåíèå äîëæíî áûòü ïðèíÿòî, äàæå åñëè åñòü òîëüêî îäèí èíèöèàòîð. Îòñþäà ñëåäóåò:P1: Âûáîðùèê ïðèíèìàåò ïåðâîå ïðåäëîæåíèå, êîòîðîå îí ïîëó÷àåò.Ñ ýòèì òðåáîâàíèåì, îäíàêî, åñòü îäíà ïðîáëåìà. Íåñêîëüêî çíà÷åíèéìîãóò áûòü ïðåäëîæåíû ðàçíûìè èíèöèàòîðàìè â ïðèìåðíî îäíî è òî æåâðåìÿ, èç-çà ýòîãî ìîæåò ïîëó÷àòñÿ ñèòóàöèÿ, êîãäà êàæäûé âûáîðùèêïðèíÿë ðåøåíèå, íî êàæäûé ñâî¼, ïîýòîìó íè îäíî èç ïðåäëîæåíèé íåíàáðàëî áîëüøèíñòâà ãîëîñîâ.
Äàæå åñëè åñòü òîëüêî äâà çíà÷åíèÿ, ìîæåò ñëó÷èòüñÿ òàê, ÷òî ïðèìåðíî ïîëîâèíà âûáîðùèêîâ ïðèìåò ïåðâîåçíà÷åíèå, à îñòàâøèåñÿ âûáåðóò âòîðîå çíà÷åíèå.  ýòîì ñëó÷àå, âûõîäèç ñòðîÿ äàæå îäíîãî àêöåïòîðà ìîæå ïðèâåñòè ê òîìó, ÷òî ïîíÿòü, êàêîåðåøåíèå áûëî ïðèíÿòî ñòàíåò íåâîçìîæíûì, òàê êàê îñòàâøèåñÿ âûáîðùèêè ïîäåëÿòñÿ â ñâîèõ ìíåíèÿõ ïîðîâíó (ñì. ðèñóíîê 3.1a).Óñëîâèå P1 âìåñòå ñ òðåáîâàíèåì, ÷òî ïðåäëîæåíèå ñ÷èòàåòñÿ ïðèíÿòûì òîãäà è òîëüêî òîãäà, êîãäà îíî ïðèíÿòî áîëüøèíñòâîì àêöåïòîðîâ, ïðèâîäèò ê òîìó, ÷òî âûáîðùèêàì ïîçâîëÿåòñÿ ïðèíèìàòü áîëåå÷åì îäíî ïðåäëîæåíèå. Ðàçëè÷íûå ïðåäëîæåíèÿ ìîãóò áûòü èäåíòèôèöèðîâàíû âûáîðùèêîì ñ ïîìîùüþ ïðèñâîåíèÿ èì ÷èñëîâîãî èäåíòèôèêàòîðà, òàêèì îáðàçîì ïðåäëîæåíèå äîëæíî áûòü ïðåäñòàâëåíî ïàðîé÷èñåë(çíà÷åíèå, íîìåð ïðåäëîæåíèÿ) ,à ðàçëè÷íûå ïðåäëîæåíèÿäîëæíû ïîëó÷àòü ðàçëè÷íûå íîìåðà.Êàê ïðèñâàèâàòü ïðåäëîæåíèÿì ðàçëè÷íûå íîìåðà çàâèñèò îò ðåàëèçàöèè.
Îäèí èç âàðèàíòîâ: ó êàæäîãî ïðîöåññà åñòü óíèêàëüíûé èäåí-15òèôèêàòîð, è êàæäûé ïðîöåññ õðàíèò ó ñåáÿ â ïåðåìåííîé max_roundìàêñèìàëüíûé íîìåð ðàóäà ïðîòîêîëà, êîòîðûé åìó èçâåñòåí. Äëÿ òîãî, ÷òîáû ñîçäàòü ïðåäëîæåíèå ñ íîâûì íîìåðîì, ïðîöåññó íóæíî óâåëè÷èòü max_round íà 1 è çàäàòü íîìåð ïðèëîæåíèÿ êàê êîíêàòåíàöèþïåðåìåííîé max_round è óíèêàëüíîãî èäåíòèôèêàòîðà ïðîöåññà. Ïåðåìåííàÿ max_round äîëæíà õðàíèòü ñâîå çíà÷åíèå ïåðñèñòåíòíî, ÷òîáûíå ïîòåðÿòü ñâîå çíà÷åíèå â ñëó÷àå îòêàçà ïðîöåññà.Òàêèì îáðàçîì, ðàñøèðèâ ïîíÿòèå ïðåäëîæåíèÿ, ïðåäëîæåíèå ñ÷èòàåòñÿ ïðèíÿòûì òîãäà, êîãäà çà ïðåäëîæåííîå çíà÷åíèå ïðîãîëîñîâàëîáîëüøèíñòâî âûáîðùèêîâ.
Ïðè ýòîì, òàê êàê ðàçëè÷íûì ïðåäëîæåíèÿìïðèñâàèâàþòñÿ ðàçëè÷íûå íîìåðà, îäíî è òî æå çíà÷åíèå ìîæåò áûòüèñïîëüçîâàíî â ðàçëè÷íûõ ïðåäëîæåíèÿõ.Òàêèì îáðàçîì, íåñêîëüêî ïðåäëîæåíèé ìîãóò áûòü ïðèíÿòû, íî òîãäà è òîëüêî òîãäà, êîãäà îíè ðàçëè÷àþòñÿ òîëüêî íîìåðîì, íî ïðåäëàãàþò îäíî è òî æå çíà÷åíèå (ñì. ðèñóíîê 3.1b). ×òîáû ýòî, â êîíöå êîíöîâ,ïðîèçîøëî, ïî èíäóêöèè ïî íîìåðó ïðåäëîæåíèÿ, äîñòàòî÷íî ãàðàíòèðîâàòü:P2: Åñëè ïðåäëîæåíèå (v, N) (ïðèíÿòü çíà÷åíèå v ñ íîìåðîì ïðåäëîæåíèÿN) ïðèíÿòî, òîãäà ëþáîå äðóãîå ïðèíÿòîå òåì æå âûáîðùè-êîì ïðåäëîæåíèå ñ íîìåðîì, áîëüøèìçíà÷åíèåv16N,äîëæíî òàêæå ïðåäëàãàòüaccept?(A)S1accept(A)accept(A)S2accept?(B)S3accept(B)accept(B)S4accept?(C)S5accept(C)time(a) Ðàçíûå âûáîðùèêè âûáðàëè ðàçíûå çíà÷åíèÿ, íè îäíî èç çíà÷åíèé íå ìîæåò áûòüïðèíÿòî.S1accept?(A)accept(A)accept(A)S2accept(A)S3accept(B)accept(B)S4accept(B)S5accept?(B)time(b) Ïðîòèâîðå÷èâîñòü âûáîðà â ñëó÷àå, åñëè âûáîðùèê èìååò âîçìîæíîñòü ãîëîñîâàòü çà íåñêîëüêî çíà÷åíèé - íåñêîëüêî ðåøåíèé îêàçûâàþòñÿ ïðèíÿòûìè.S1accept?(A)accept(A)accept(A)S2S3accept(B)S4accept(B)S5accept(B)accept(A)accept?(B)time(c) Ïðåäëîæåíèÿ äîëæíû áûòü óïîðÿäî÷åíû, ÷òîáû óñòàðåâøèå ïðåäëîæåíèÿ ìîæíîáûëî îòâåðãíóòü (ïðåäëîæåíèå îòS1äîëæíî áûòü îòâåðãíóòîS3)Ðèñ.
3.1: Ïðèìåðû, ïîêàçûâàþùèå íåîáõîäèìîñòü îïðåäåëåííûõ îãðàíè÷åíèé íàëîãèêó âûáîðùèêà17Òàê êàê èäåíòèôèêàòîðû ïðåäëîæåíèé âîçðàñòàþò è ðàçëè÷íû, óñëîâèå P2 ãàðàíòèðóåò ÷òî òîëüêî îäíî çíà÷åíèå âûáðàíî. Ñ äðóãîé ñòîðîíû, äëÿ òîãî, ÷òîáû áûòü ïðèíÿòûì, ïðåäëîæåíèå äîëæíî áûòü ïðèíÿòî õîòÿ áû îäíèì âûáîðùèêîì. Ñëåäîâàòåëüíî, óñëîâèå P2 ìîæåò áûòüóäîâëåòâîðåíî åñëè:P2': Åñëè ïðåäëîæåíèå (v, N) ïðèíÿòî, òîãäà ëþáîå äðóãîå ïðèíÿòîå ëþáûì âûáîðùèêîì ïðåäëîæåíèå ñ íîìåðîì, áîëüøèìòàêæå ïðåäëàãàòü çíà÷åíèåN,äîëæíîvP2' íå ïðîòèâîðå÷èò P1, ñëåäîâàòåëüíî, êàêèå-òî ïðåäëîæåíèÿ áóäóò ïðèíÿòû. Òàê êàê êîììóíèêàöèÿ ìåæäó ïðîöåññàìè àñèíõðîííàÿ,ïðåäëîæåíèå ìîæåò áûòü ïðèíÿòî äàæå åñëè êàêîé-òî èç âûáîðùèêîâåãî âîîáùå íå ïîëó÷èë. Ïóñòü ýòîò âûáîðùèê íàçûâàåòñÿ CÏðåäñòàâèì ñåáå, ÷òî íîâûé èíèöèàòîð ïðîáóæäàåòñÿ è äåëàåò ïðåäëîæåíèå ñ íîìåðîì M, M > N, ñ äðóãèì ïðåäëàãàåìûì çíà÷åíèåì.
P1îáÿçûâàåò C ïðèíÿòü ýòî ïðåäëîæåíèå, òàêèì îáðàçîì íàðóøàÿ P2'.Ñëåäîâàòåëüíî, äëÿ òîãî ÷òîáû P1 è P2' áûëè áû âåðíû, íåîáõîäèìî:P2 : Åñëè ïðåäëîæåííîå çíà÷åíèå v áûëî ïðèíÿòî, òî ëþáîå ïðåäëîæåíèå ñ íîìåðîìM, M > Näîëæíî èìåòü çíà÷åíèåvÈç P2 ñëåäóåò P2' è P2 ò.ê. ëþáîå ïðèíÿòîå ïðåäëîæåíèå äîëæíîáûòü ïðåäëîæåíî êàêèì-òî èíèöèàòîðîì.Èíèöèàòîð äîëæåí èìåòü ìåõàíèçì, ïîçâîëÿþùèé åìó óçíàòü, êàêîåïðåäëîæåíèå áûëî ïðèíÿòî, ïåðåä òåì êàê ñäåëàòü ñâî¼ ïðåäëîæåíèå.Äëÿ ýòîãî ñëåäóåò äîêàçàòü, ÷òî P2 âûïîëíåíî; íåîáõîäèìî ïðîäåìîíñòðèðîâàòü ÷òî, ïðè óñëîâèè êîãäà íåêîòîðîå ïðåäëîæåíèåïðåäëîæåíèå ñ íîìåðîìN > Mèìååò çíà÷åíèå18v.(v, M) , ëþáîåÏðèìåíÿåòñÿ èíäóêöèÿ ïî íîìåðó ïðåäëîæåíèÿãîN > M,âñå ïðåäëîæåíèÿ â äèàïàçîíå(ñì.
ðèñóíîê 3.1c). Äëÿ òîãî, ÷òîáûMN.M...N-1Ïóñòü äëÿ ëþáî-èìåþò çíà÷åíèåváûëî ïðèíÿòî, íåîáõîäèìî ÷òîáûáîëüøèíñòâî âûáîðùèêîâ (ïóñòü ýòî ìíîæåñòâî íàçûâàåòñÿ ìíîæåñòâîìÑ)ïðèíÿëî åãî.Òîãäà, ïî èíäóêöèè, êàæäûé âûáîðùèê âíèÿM...N-1 ,Ñòàêæå ïðèíÿë ïðåäëîæå-è êàæäîå ïðåäëîæåíèå â ýòîì äèàïàçîíå èìåëî çíà÷åíèåv.Òàê êàê ëþáîå ìíîæåñòâî, ñîñòîÿùåå èç áîëüøèíñòâà âûáîðùèêîâ,äîëæíî âêëþ÷àòü õîòÿ áû îäíîãî èç ó÷àñòíèêîâ ìíîæåñòâà÷òîáû ïðåäëîæåíèå ñ íîìåðîìNèìåëî çíà÷åíèåvÑ,äëÿ òîãî,íåîáõîäèìî, ÷òîáûâûïîëíÿëñÿ ñëåäóþùèé èíâàðèàíò:P3: Äëÿ ëþáûõ v è N ïðåäëîæåíèå (v, N) äåëàåòñÿ òîëüêî òîãäà,êîãäà ñóùåñòâóåò ìíîæåñòâîS,ñîñòîÿùåå èç áîëüøèíñòâà âûáîðùè-êîâ, òàêîå ÷òî âûïîëíÿåòñÿ îäíî èç óñëîâèé:•Íè îäèí âûáîðùèê èç ìíîæåñòâàìåðîì, ìåíüøèì•Çíà÷åíèåvSíå ïðèíÿë ïðåäëîæåíèå ñ íî-N- ýòî ôèêñèðîâàííîå ïðåäëàãàåìîå çíà÷åíèå ïðåäëîæå-íèé ñ íîìåðîì ìåíüøåN,ïðèíÿòîãî âûáîðùèêàìè èçSÝòî çíà÷èò, ÷òî óñëîâèå P2 ìîæåò áûòü óäîâëåòâîðåíî åñëè èíâàðèàíòû èç P3 ñîáëþäåíû.
Äëÿ òîãî, ÷òîáû âûïîëíèòü òðåáîâàíèÿ P3,èíèöèàòîðó, ïåðåä òåì êàê ñäåëàòü ïðåäëîæåíèå ñ íîìåðîìNíåîáõî-äèìî óçíàòü î ïîñëåäíåì ïðåäëîæåíèè ñ íîìåðîì, ìåíüøèìN,êîòîðîåáûëî ïðèíÿòî áîëüøèíñòâîì âûáîðùèêîâ.Óçíàòü ïðåäëîæåíèÿ, êîòîðûå óæå áûëè ïðèíÿòû äîñòàòî÷íî ïðîñòî,à ïðåäñêàçàòü, êàêèå ïðåäëîæåíèÿ áóäóò ïðèíÿòû â áóäóùåì - ñëîæíî.19Âìåñòî òîãî, ÷òîáû ïûòàòüñÿ ïðåäñêàçûâàòü áóäóùåå, èíèöèàòîð êîíòðîëèðóåò õîä èñïîëíåíèÿ, òðåáóÿ îò âûáîðùèêîâ îáåùàíèÿ, ÷òî â áóäóùåìèìè íå áóäóò ïðèíÿòû íåïðàâèëüíûõ ðåøåíèÿ.
Äðóãèìè ñëîâàìè, èíèöèàòîð òðåáóåò îò âûáîðùèêîâ íå ïðèíèìàòü ïðåäëîæåíèé ñ íîìåðîì,ìåíüøèìN.Òàêîé ïîäõîä âåä¼ò ê ñëåäóþùåìó àëãîðèòìó âûäâèæåíèÿïðåäëîæåíèé:Èíèöèàòîð âûáèðàåò íîìåð ïðåäëîæåíèÿçûâàåòñÿ Prepare -çàïðîñîì ñ íîìåðîìN )Nè ïîñûëàåò çàïðîñ (íà-êàæäîìó âûáîðùèêó, òðåáóÿâåðíóòü:< N•Îáåùàíèå íèêîãäà íå ïðèíèìàòü ïðåäëîæåíèÿ ñ íîìåðîì•Èíôîðìàöèþ î ïîñëåäíåì èçâåñòíîì âûáîðùèêó ïðåäëîæåíèè, ñìàêñèìàëüíûì íîìåðîì, ìåíüøèìNÅñëè èíèöèàòîð ïîëó÷àåò îòâåò íà çàïðîñ îò áîëüøèíñòâà âûáîðùèêîâ, îí ìîæåò ïîñëàòü ïðåäëîæåíèå(v, N) (ïðè÷åì âûáèðàåòñÿ çíà÷åíèåñ ìàêñèìàëüíûì íîìåðîì ïðåäëîæåíèÿN ),ãäåv- çíà÷åíèå âûáðàííîåñðåäè:•íà÷àëüíîãî çíà÷åíèÿ èíèöèàòîðà•âñåõ çíà÷åíèé ïðåäëîæåíèé êîòîðûå èíèöèàòîð ïîëó÷èë îò âûáîðùèêîâ â ïðåäûäóùåì ïóíêòåÇàòåì èíèöèàòîð íåïîñðåäñòâåííî äåëàåò ñâî¼ ïðåäëîæåíèÿ, ïîñûëàÿ, ìíîæåñòâó âûáîðùèêîâ ñôîðìèðîâàííîå ïî îïèñàííûì âûøå ïðèíöèïàì ïðåäëîæåíèå.
Ýòî äîëæíî áûòü òî æå ìíîæåñòâî âûáîðùèêîâ,÷òî è îòâåòèëî íà ïåðâîíà÷àëüíîå ïðåäëîæåíèå. Ýòîò òèï çàïðîñà íàçûâàåòñÿ Accept-çàïðîñîì.20Âûáîðùèê ìîæåò ïîëó÷èòü äâà âèäà çàïðîñîâ: Prepare è Accept. Òàêêàê ëþáîå ñîîáùåíèå âñ¼ ðàâíî ìîæåò ïîòåðÿòüñÿ, âûáîðùèê ìîæåò èãíîðèðîâàòü ëþáîé çàïðîñ, áåç óãðîçû íàðóøåíèÿ êîíñåíñóñà. Âûáîðùèêâñåãäà ìîæåò îòâåòèòü íà Prepare çàïðîñ, â îòëè÷èè îò Accept -çàïðîñà.Âûáîðùèê ìîæåò îòâåòèòü íà Accept òîëüêî òîãäà, êîãäà íóæíî ïðèíÿòüïðåäëîæåíèå, òî åñòü òîëüêî òîãäà, êîãäà âûáîðùèê íà äàííûé ìîìåíòíå îáåùàë êîìó ëèáî â îòâåòå íà êàêîé-ëèáî ïðåäûäóùèé Prepare çàïðîñýòîãî íå äåëàòü.Èíûìè ñëîâàìè:P1': Âûáîðùèê ìîæåò ïðèíÿòü ïðåäëîæåíèå ñ íîìåðîì textbfNòîãäà è òîëüêî òîãäà, êîãäà îí íå îòâå÷àë ïîëîæèòåëüíî íà çàïðîñPrepare ñ íîìåðîì, áîëüøèìNÊîíå÷íàÿ âåðñèÿ àëãîðèòìà ìîæåò áûòü ïîëó÷åíà â ðåçóëüòàòå ïðèìåíåíèÿ íåáîëüøîé îïòèìèçàöèè.Ïðåäïîëîæèì, âûáîðùèê ïîëó÷àåò Prepare çàïðîñ ñ íîìåðîì N, íîîí óæå îòâåòèë íà N çàïðîñ ñ íîìåðîì, áîëüøèì N, òàêèì îáðàçîì ãàðàíòèðóÿ íå ïðèíèìàòü ïðåäëîæåíèå ñ íîìåðîì N.
 ýòîì ñëó÷àå âûáîðùèêó íåò ïðè÷èíû îòâå÷àòü íà Prepare çàïðîñ, òàê êàê â ëþáîì ñëó÷àåîí íå ïðèìåò ïðåäëîæåíèå ñ íîìåðîì N, êîòîðîå õî÷åò ñäåëàòü èíèöèàòîð, íåçàâèñèìî îò çíà÷åíèÿ ïðåäëîæåíèÿ. Òàêèì îáðàçîì, àêöåïòîðìîæåò ñâîáîäíî ïðîèãíîðèðîâàòü òàêîé Prepare çàïðîñ. Îí òàêæå ìîæåòïðîèãíîðèðîâàòü Prepare çàïðîñ äëÿ ïðåäëîæåíèÿ, êîòîðîå óæå áûëîïðèíÿòî. ðåçóëüòàòå ýòîé îïòèìèçàöèè, âûáîðùèê îáÿçàí ïîìíèòü òîëüêîïîñëåäíåå ïðåäëîæåíèå êîòîðîå îí êîãäà-ëèáî ïðèíÿë (õðàíèòüñÿ íîìåðïîñëåäíåãî èçâåñòíîãî âûáîðùèêó ïðèíÿòîãî ïðåäëîæåíèÿ).Òàê êàê óñëîâèå P3 äîëæíî âûïîëíÿòüñÿ äàæå â ñëó÷àå àâàðèé è ïå-21XS1S2values S3S4YP 3.1P 3.1P 3.1S5A 3.1 XA 3.1 XA 3.1 XPrepare(3.1)Accept(X, 4.5)P 4.5 A 4.5 XP 4.5 A 4.5 XP 4.5 A 4.5 Xtime(a) Çíà÷åíèå óæå ïðèíÿòî, íîâûé èíèöèàòîð óçíàåò î í¼ì è ñìåíÿåò ñâîå ïðåäëàøàåìîå çíà÷åíèå.XS1S2values S3S4YP 3.1P 3.1P 3.1A 3.1 XS5A 3.1 XA 3.1 XP 4.5 A 4.5 XP 4.5 A 4.5 XP 4.5 A 4.5 Xtime(b) Çíà÷åíèå åùå íå ïðèíÿòî, íî èíèöèàòîð óçíàåò î íåì â âûçîâåPrepare.Íîâûéèíèöèàòîð ïîëüçóåòñÿ çíà÷åíèåì, ïðåäëîæåííûì ðàíåå.
Îáà èíèöèàòîðà óñïåøíîçàâåðøàþò ãîëîñîâàíèå.XS1S2values S3S4YS5P 3.1P 3.1P 3.1A 3.1 XA 3.1 XP 4.5 A 3.1 XP 4.5 A 4.5 YP 4.5 A 4.5 YA 4.5 Ytime(c) Ïðåäûäóùåå çíà÷åíèå íå èçáðàíî è íå èçâåñòíî íîâîìó èíèöèàòîðó. Íîâûé èíèöèàòîð èñïîëüçóåò ñîáñòâåííîå çíà÷åíèå, ãîëîñîâàíèå ïî ïðåäûäóùåìó ïðåäëîæåíèþçàáëîêèðîâàíî.Ðèñ. 3.2: Ïðèìåðû ñöåíàðèåâ ðàáîòû Paxosðåçàïóñêîâ âûáîðùèêà, ýòà èíôîðìàöèÿ äîëæíà õðàíèòñÿ ïåðñèñòåíòíî.Ñ äðóãîé ñòîðîíû, èíèöèàòîð âñåãäà ìîæåò îòêàçàòüñÿ îò ñâîåãî ïðåäëîæåíèÿ è çàáûòü î íåì, íèêîäà áîëüøå íå äåëàÿ ïðåäëîæåíèé ñ òåì æåíîìåðîì (ò.å. ïðåäâàðèòåëüíî íå ñäåëàâ Prepare çàïðîñ).223.2Îïèñàíèå ôàç àëãîðèòìà PaxosÓ÷èòûâàÿ äåéñòâèÿ âûáîðùèêîâ è èíèöèàòîðîâ, àëãîðèòì äåéñòâóåòâ äâóõ ñëåäóþùèõ ôàçàõ.Ôàçà 11.
ÈíèöèàòîðâûáèðàåòïðåäëîæåíèåñíîìåðîìN è âûïîëíÿåòPrepare çàïðîñ äëÿ âñåõ âûáîðùèêîâ.2. Åñëè âûáîðùèê ïîëó÷àåò Prepare çàïðîñ ñ íîìåðîì N, áîëüøèì÷åì íîìåð ëþáîãî äðóãîãî Prepare çàïðîñà, íà êîòîðûé ýòîò âûáîðùèê êîãäà-ëèáî îòâå÷àë, îí îòâå÷àåò íà çàïðîñ, îáåùàÿ íèêîãäà íåïðèíèìàòü ïðåäëîæåíèå ñ íîìåðîì, ìåíüøèì N è ñ èíôîðìàöèåéî ïðåäëîæåíèè ñ íàèáîëüøèì M < N, êîòîðîå âûáîðùèê ïðèíÿëïîñëåäíèì.Ôàçà 21. Åñëè âûáîðùèê ïîëó÷àåò îòâåò íà Prepare çàïðîñ ñ íîìåðîì Nîò áîëüøèíñòâà âûáîðùèêîâ, îí ïîñûëàåò Accept çàïðîñ êàæäîìóèç âûáîðùèêîâ, ñîäåðæàùèé ïðåäëîæåíèå (v, N), ãäå çíà÷åíèå vâûáðàííî â ðåçóëüòàòå ïîèñêà ñðåäè âñåõ îòâåòîâ íà Prepare çàïðîñ ïî ìàêñèìàëüíîìó íîìåðó ïðåäëîæåíèÿ, èëè ñî çíà÷åíèåì,ïîñëàííûì èíèöèàòîðîì, åñëè Prepare çàïðîñ íå âåðíóë íè îäíîãîïðåäëîæåíèÿ.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
