Introduction to Distributed Algorithms. Gerard Tel (2nd edition) (811419), страница 101
Текст из файла (страница 101)
Ртоо~. ТЫв 1в Ъу шйисИоп оп тЬе пишЪет оЕ пот1ев; тЬе выщ1е-пот1е сме 1в $тЬла1, во сопв1т1ет а 5гарЬ ю1тЬ $ч~о от тоге пос1ев. ТЬеге 1в ат 1еыт опе пос1е, вау о, ~т1тЬ с1ерее йче ог 1ем. ТЬе дгарЬ С вЂ” (о) 1в р1влаг влс1 Ьм опе пот1е 1евв, Ьепсе Ьу шт1исФнн~ 1т Ьаз ап асусЬс ог1ептат1оп ш жЫсЬ вбегу пот1е Ьав ап оит-т1едгее оЕ ат шовт Ые. 1п тЬе ог1ептат1оп оЕ С, аБ ет15ев оЕ С вЂ” (и) аге йгес$ес1 м ш тЫз опептат1оп, апт1 тЬе ет1дея 1псИепт то и яхе йхестет1 аъау Егош э. С1езх1у, тЬе гевиМп5 ог1ептайоп 1в асусЬс япс1 тю пот1е Ьм пюге ФЬап 6че оит5оищ ет1дев.
П ТЬеогеш 15.20 (Бис-со1ог СЬеогеш) Р1апат дтарйз рте зтх-со1отаб1е. РгооЕ. 1еФ С Ъе а р1влвх рарЬ; сопяЫег вл асусЬс опеаФат1оп оЕ С ш ~чЫсЬ тю пот1е Ьм шоте ФЬвл 6че оит5ош5 ет15ев. Весаияе тЬе ог1етйат1оп 1в асус11с, тЬе иос1ев сап Ъе пишЬетей от йтои5Ь о„зисЬ ФЬаФ 1Е ФЬеке 1в вл ефе йтестес1 6ош из то от, реп д > т. Со1ог $Ье пот1ев ш ФЬе огс1ег ъ1 йгои5Ь е„; тЬе рторегту оЕ йе пишЪегшд штрЬез 1Ьат ЬеЕоге поде ю оп1у 15 огао11сгайоп оис-дефЬЪогз оГ ю аге со1огес1. ТЬ1в, апс1 сЬе ргорегФу оГ сЬе опепсаСюд, дойч 1п1р1у сЬас ас шовс йче дефЬЪогя оЕ э аге со1огес1 ЪеГоге о, Ьепсе ю сап Ъе со1огес1 ЙЯегепс1у 6ош а11 (а1геас?у со1огес1) пе1зЬЪогя. П ТЬе ргооГ оГ 1Ье в1х-со1ог 1Ьеогеш ви~~еягя сЬе с?ев1зд оГ вл а1~ог1сЬш Гог сошрисш~ а яы-со1огшв; ФЬе йгя~ в~азе сошри1ея ал асус11с опепФаМод аз шс11сагес? ш ? ешша 15.19, апс1 сЬе весопс1 зСа~е со1огв 1Ье пойез ш ап огйег сопз1зсепФ едгЬ сЬе опетйас1оп.
То гергеветй ап асус11с опепсаМоп, ргосевз р 1я рчеп ап ш~езег чапаЫе х„, апс1 ч~е йейпе ес?ве ро со Ъе с(1гес~ес1 6ош р со о, с1епосес1 ро, И х <х Ч (х =х Лр<ц). С1еаг1у, еасЬ ес1ае 1в йгессес1 ш ехас~1у опе юау (1.е., ейЬег ро ог ор ЬоЫв), влс1 сЬе опепсас1од 1в асусйс. ? ес оиФ(р) с?едосе ФЬе пишЪег о1 оисдо1пд ес1Кея оГ р, 1.е., ои1(р) = 4~(д Е №гдЛ: ру).
ТЬе с1ея1гес1 ров~сопй6оп оГ сЬе йгвФ рЬме 1я В, с?ейпес1 Ъу В и (чр: оиг(р) < 5). Ргоагаш 51, гог евгаЫ1яЫщ В, содзЫя оК опе орегас1од Гог еасЬ ргосем, с11гесгш~ а11 ес1цев оГ р соиагс?я р Ю р Ьм п1оге сЬап йче ои~~ошз елея: О„: 1 оиг(р) > 5 ) х:= шах(х~: д б №~дЬ ~ + 1 ТЬеогегп 15.21 Ртодтат 31 ягаЬйиез Фо В, ада ч В ао1сЬ Вьеп йе чайи о~ х„тетатз сопвсапГ. Ртоо~. А сопйр~гаг1оп 1я сепшпа1 К апс1 оп1у 11' В ж багие; Ьепсе, К сЬе ргозгаш Ьа?ся В 1в еясаЫ1яЬес1, апс1 М В ж езФаЫ1яЬей сЬе чапаЫев х„гешаш сопвсадФ. То ргоче гЬе 1епп1пас1оп о? 5, тче изе а "геГегепсе" асус11с опепсМюп м ш ? епш1а 15.19; 1Ь(з ге?егедсе опепсаЫоп пеей пос Ъе, Ьочечег, сЬе опепсаМоп сошри1ес? Ъу 51.? ешша 15.?9 ипрЬез ФЬе ех?зФепсе о? ап епишегаМоп о1, ю~, ... оГ сЬе дос1ев висЬ сЬас ечегу пос?е Ьм ас шовс йче пейгЬЪогя МФЬ а Ь1вЬег шах. Ад ес1це ю;э; 1в са11ес1 чтптд К 1с 1я опепсес? м цЪ; Мц1е 1 > ~; 1ес ~( у) Ъе ~Ье Ьяс (н„п2, ...), тчЬеге тц 1в сЬе пишЪег о?' агап~ ес1Кев 1дс1с?едс со о,.
ЕасЬ аррЬсас1од оЕ асс1од П с?есгеазез ~ (ш сЬе 1ех1содарЬ?с огс?ег); сопвЫег йв аррИсас1оп ш пос1е о„ч~Ьове оис-пефЬЪог чпгЬ сЬе зша1?езз шс?ех 1в ц. Аз о, Ьзз ас 1емс ях оис-пе?фйогв Ъис Ьм аг, .8 Мейоййоду 1от БГаЬЙиаФшп чаг хр .
шгезег; с: (1, 2, 3, 4, 5, б); Я~хр<х~ Ч (хр=х~ Лр<ф); озг(р) ш Ф(д е №1дЛ„: рд); Р„: ( ои1(р) ) 5 ) хр ..= шах(хз: ц Е №1дЬ ) + 1 Ср: ((ЛЯ:Я Л ср=су) Л (чтв.г. рт:сф ф6) ) :=ь А1КогЫЬш 15.5 Бтх-соьокгяс льсокггнм кок рьлылк оклрнв. шов1 6че пещЬЪогз жЫЬ ЫкЬег 1Ыех, з < 7' во 1Ье ес15е це; жм мгспс Ъий семев 1о Ье во, Мни йесгеше~йшд л;, пЫ1е по п~ 1в аЯес~ес1 Гог й с г.
П Рго5гзш Яв, Гог ев~аЬЫзЫпд Ф, а)зо сопви~з оГ а з1пд1е орегаг1оп Гог еасЬ ргосевз, ш юЫсЬ р ас(ор~в а со1ог 6 йЯегеий йош йз виссемогв 1Е с еоиа)з опе оГ 1Ьозе со1огз аЫ ап шшзес1 со1ог ех1Ыв: Св ( (=1д: рд Л с„= с,) Л (Ут в.+. рт: с,.
ф Ь) „:=ь ТЬеогеш 15.22 Ртодтат Яр Гет.ттаГез, апй 4В м итие йе 5па1 сопЯи- тайоп заИзЯез 9. Ртоо~. То вЬо~т гегшшаг1оп, иве гЬай йЬе елея аге йгес1ес( м ш ап асусЬс опе~йай1оп, Ьепсе гЬеге ехЫв ап епишегаМоп оГ гЬе пойез и1, ч~, ... висЬ ФЬЮ еасЬ поде Ьм оп1у виссемогв ЯВЬ а зша11ег шс1ех.
тейпе д(у) = (т1, тз, ...), ~кЬеге ттц ж О Ы с; и ЙИГегетй 6ош гЬе со1огз оГ еасЬ оГ ч,'в виссеввогв апх1 1 о1Ьегичзе. ТЬе арр11сайоп оГ акоп С„Ъу поде и, сЬап5ез тп, 6ош 1 1о О, апй шау оп1у сЬапде тп; Ггош О го 1 Гог 7' > (, Ьепсе ФЬе ча)ие о1 д Йесгемея ш 1Ье 1ех1сорарЫс огйег. Рша)1у, мзише 9 Ьо1й апй сопзи1ег а сопйцигайоп ш юЫсЬ по С, акоп и аррЬсаЫе. Ргосевв р Ьм аг шовФ йче виссеввогв, Ьепсе 1Ьеге 1з а со1ог 6 Е 11, 2, 3, 4, 5, 61 поФ изей Ъу апу оГ йв виссемогв.
Ав ФЬе визга оГ С 1з 1а)зе, Ы Го11отчв ~Ьа~ с„сМегз Ггош ~Ье со1ог оГ ечегу зиссемог. Рша11у, аког ечегу еда ат, ейЬег т 1з а зиссевзог о1 д ог д 1з а виссеввог оГ т, юЫсЬ понг ппрЬез ФЬЮ с, ф сз. П ТЬе со11агега1 сошровМоп оГ Я1 аЫ Яр 1з рчеп м А1ког1~Ьш 15.5. 480 ТЬеогеш 15.23 АЕвотчйт 15.о иЕаЬйиеи Ео ~. РгооЕ'. ТЬе сойаФега1 сошров16оп сзл Ъе Еогшей Ъесанве гЬе чапаЫез жг|Ь сеп Ъу Яр (йЬе с ) йо поЕ оссиг ш Я~.
1С тчм г|ешопз~гагес| аЪоче 1ЬаФ Я, иФаЪйгез Фо О апс| с|оев до1 сЬатще 1Ье х„айег ев1аЪ||яЫгщ й (ТЬеогеш 15.21) злд 1ЬаЕ Я~ иФаЪйзез Фо Ф |Е 8 Ьо1с|з (ТЬеогеш 15.22). 1п огйег ~о сопс1пйе ФЬЮ 9~4Я Яи и1аЪйвез Ео Ф Ъу ТЬеогеш 15.17 й гетпыпи 1о иЬож 1ЬаФ 1Ье сошрозМоп |в Еан. Ву ТЬеогеш 15.22, 1Ьеге аге оп|у йп|1е1у шапу з1ерв оЕ Я~ ЪеЬчееп вбегу Мо иФерв оЕ Я„щЫсЬ вЬо~чз Еа|гдеяз ~~.г.Ф. Я~.
Ву ТЬеогеш 15.21 Я~ 1еппша~ез, 'в~ЫсЬ вЬотчв Еа|гпезз тг.г.~. Яр. П 15.3.2 Согприйт~д МиитпЕ РаИи ТЫз зпЪиесйоп ргеие~йв а з1аЪйяшв а|вопМш~ Еог а с1аяз оЕ ргоЫеши 1ЬаЕ сап Ъе Еогпш|а~ей м йлдпщ а пшщда| раФЬ ш а вшФаЪ|у сЬозеп сов~ 6шс6оп оп райз. Ехашр1ев шс1пйе до1 оп1у йЬе (иггащЬЕЕогюап|) сошрп$а~юп оЕ гои~ищ 1аЪ|еи, Ъцг, а|во йерй-йгв~ иеагсЬ ~геев аЫ, шаге ишрпишв1у, е1есИоп (иее Ехегс|ве 15.11).
%е вЪа|1 йгв1 ргезай гЬе шш|ша|-раФЬ ргоЫеш ш ап а|8еЪга|с зе~Мгщ зли| ргевепФ ЕЬе Ордам а|цогйЬш (А|цогйЬш 15.6), юЫсЬ и1аЪйяеи го ппп|ша1 ра1Ъв; арр11саФ|опв аге рчеп аФ ГЬе епс| оЕ ФЫз зиЪвес$1оп. РгорегИев оЕ 1Ье соз1 6шсйоп алй шпиша| райю. Азяме а 6шсМоп Ю Егош райв 1о а $сйа|1у огдегес| йоша|п У |з в|чеп; 1ог а ра1Ь л', ФЬе ча|ые Ю(7г) же Ъе геЕеггес| ~о м ФЬе соий оЕ 7г. ТЬе созФ оЕ ФЬе етр$у рай (р) оЕ1егщ~Ь 0 Егош р Фо р, |з г|епогей с злй аввдшей $о Ъе |акягп 1о р. %е сопви|ег сов1 6шсг|опв Еог жЫсЬ 1Ье соМ оЕ а раФЬ сзл Ъе сошриЕей шсгешепга11у, юЫсЬ шеапя гЬа1 ФЬе сой оЕ поп-ешрФу райя свп Ъе сошрШей П(р0 "., рь ри+ ) = Б..„,Р(р0 " Эк)).
Неге Д~~ |з а 6шсйоп ~„,: У вЂ” У, са|1е1 гЬе Ыде,Еипсйоп, р~еп Еог еасЬ ей~е рд. ТЬе соиг, оЕ а ра~Ь ~г = (ри, р~,...,р~ ~, ра) сап дойч Ъе сошриФе6 1псгешедФа||у м ~р,р,,(... (~„р,(с~,)...). Эедо1пщ м Е (х) 1Ье ча|ие ~~, „, (... (~~,„,(х)...), м~е сзл юг|Се Ю(~г) м ~ (с ). ТЪе совФ 6шсЫоп (вЫ ес1ве 6шсйопв) аге ргевишес| 1о за~|зЕу ~Ье ЕоБоМпв ахюшв. (1) МопоФоп|сйу. Рог е~гегу еда рд аЫ х е У, 1Е ~г |в а Бшр1е ра~Ь со д по1 соМзлпЕгщр, ~Ьеп Ю(~г) с х ~,Е" (В(~г)) < ~ (х). (2) Сус1е-1псгеме. ЕЕ т |я а сус1е, Е" (х) > х Еог а11 х Е У. 5.3 Мейоййоуу ~от йабйтапоп (3) ЬепфЬ-1асгеазе.
ТЬеге ех1вФз а пишЪег В висЬ ФЬЮ аког еасЬ ра1Ь О о1 1епфЬ В ог шоге, еасЬ х Е У, влй еасЬ в1шр1е ратЬ тт оГ 1ещй Л вЂ” 1 ог 1ем, Д„(ю) ) Р(тт). ТЬе тгтита1-рай ргоб1ет ж $о сошриФе, 1ог еасЬ р, 1Ье гшшша1 сов1 оГ влу рагЬ ехийщ ш р, алй Ыв ргейесеявог д ш а рМЬ о1 ппшша1 сояг (тгй й тЬе пшшпа1 ратЬ 1з ешр1у). ТЬе созС ог а пшйша1 ратЬ ж г1епо1ей к(р) апс1 1Ье ргес1есезвог 1в йепоФей ф(р).
ТЬе ехЫепсе вхп1 ап ппроггахй ргореггу ог пшиша1 райз аге ехргеззей ш 1Ье ГоИотчшц ~Ьеогеш. ТЬеогегп 15.24 (1) Рог влету р Йете ехтзй а лтпр1е рай тт(р) елйт~д Ы р, зисЬ йа1 аИ райз вийону Ы р Ьаие а соа1 о~ аб 1еай Р(тт(р)). (2) Тйеге его а зрапптз ~отев1 1'саИеН а тптьтпа1-рай ~огез1) зисй Йаг ~от еиету р Йе (ипщиа) рай ~тоти а тооГ $о р ла8 Йе сов$ Р(тт(р)). Ргоо~, Рог (1): м 1Ьеге аге оп1у йш1е1у шалу з1шр1е раИа еш11п~ Ы р, ч е сал сЬоове тт(р) м а ш~шша1 зппр1е ра1Ь епйшд ш р. Ву ФЬе сЬо1се оГ тг(р), аБ з1шр1е раМм еыйщ ш р 1Ьеп Ьаме а созб оГ а$ 1ем1 Р(тг(р)).
ТЬе созФ о1 а райЬ сопАа1ш~щ а сус1е 1з (Ъу сус1е-шсгеззе апг1 шопо1опбс1гу) Ыф~ег 1Ьвл 1Ье соМ о1 гЬе зппр1е раФЬ оЫашей Ъу гешалпз сус1ев, Ьепсе а1во Ъоиги$ей Ъу Р(тг(р)). ТЫя вЬояз ФЬЮ л (р) ~ч1тлеззев ФЬе йгй раг~ о1 1Ье тЬеогеш. Рог (2): м пышша1 ратЬз пеев поФ Ъе ип1с1ие, гЬе весоЫ рагг оГ гЬе ~Ьеогеш геошгез зоше саге; тЬе рарЬ оЫа1пеи Ъу гаЫпц аБ ег1~ея оссиггшд ш пншша1 ра1Ьз пеед поФ Ъе а вогез~. 1,йе гЬе ор1ппа1 яш1с Фгеев сопзЫегед ш ТЬеогеш 4.2, ФЬе пышша1-раФЬ Гогевт, 1я поФ ишоие, Ъи1 1т, 1в роззбЫе Фо сопзФгис1 зисЬ а $огезг, зз 1о11оттв.
СЬоове Ьг ергу ног1е р а Га1Ьег ф(р) м Гойлъ. 0 тЬе ешрФу рМЬ (р) ж оргппа1, ф(р) = тп1, оФЬегттие ф(р) 1з а пе1зЬЪог д висЬ ФЬЮ а ппшша1 раФЬ 'бо р юЫЬ репиШша1е поде д ехЫз. СопзЫег 1Ье едигея р, ф(р) Гог жЫсЬ ф(р) ~ тп1. Ву шопо1оп1с1ту, Гог ечегу р тйЬ ф(р) ф тп1, к(р) > ~рв~ 1(к(ф(р)). СопвециепМу, Ы' С 1з а сус1е (Ггош р 1о р) ш ~Ье могшей згарЬ, гЬеп к(р) > Ус(к(р)), юЫсЬ сопггасБс~з ФЬе сус1е-шсгеме ргорег~у, Ьепсе ФЬе сЬозеп ефез бейле а ГогмФ. 1гы1исЫоп Ггош ФЬе гооЬ вЬочз ~Ье йеаге1 ргорегФу оЕ ФЫз Гоген. П ОЪвегче 1Ьаз ~Ье 1епфЬ-шсгеазе ргорег~у 1з поФ пеейей ш ФЬе ргооГ; 1з 1з оп1у песеввагу то зЬаи 1ЬаФ егтопеоиз Ыогшайоп ш 1Ье шЖа1 сопйдига- 4аа 15 йаЪйлайота чав К~: В; 1р: Ие1уБ 0 (~иЦ 1 Ср: Кр:= 1 (Ъ, ш1 Им(Кч): д Н ~7е уЪ.)) ' И'К =ср СЬеп Ьр:= Ы е1ве Ьр ж а в.С.
Кр = ~,„(Кч) А1$0г1СЬш 15.6 ТНЕ 11РЭАТЕ А1ООВ1ТНМ РОВ, МРИМАГ РАТНЗ. С1оп и ечепСиаБу гешочей ш а вСаЬйз1пе а1цог1СЬш Сог сошриС1пд пип1шв1 раСЬз. ТЬе гесуигей ровСсоЫ1С1оп оГ ап а1дог1СЬш 1ог СЬе шыыгпа1-раСЬ ргоЫеш сап почч Ье зСаСей: Ф вв (Чр: Кр = к(р) А Ьр = 4(р)). А с1мв1са1 (поп-вСаЫ11зшв) а1зог1СЬш 1ог езСаЫиЬшц Ф сопзжСв о1 а вшд1е орегаС1оп оп еасЬ елее, са11ес1 р~иЬжд СЬе еда: Р„: (У„(К)сК,) К.:= 1-(Кч) ~р:= Ч ТЬе чапаЫе К, 1з ш1С1в11зей Со с„. ТЬе мвегС1оп К > к(р) сап Ье вЬотчп Со Ье 1пчаг1апС. То зЬою 11чепевз 1че шцзС аззише СЬаС ризЫпе и Га1г т.г.С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
