Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 94
Текст из файла (страница 94)
В построенной конфигурации два процесса обладаютмаркером, хотя подобной ситуации не может возникнуть ни в одном вычислениинашего алгоритма.Естественно, мы бы предпочли, чтобы алгоритм построения моментальногосостояния реконструировал конфигурацию, которая и «в самом деле» может возникнуть при вычислении. К сожалению, множество реализуемых конфигурацийне является инвариантом отношения эквивалентности, как это показано в § 2.3.2,355uuHH eHHHHHjHuHHjHueeРис.
10.2. Несогласованное моментальное состояниеТребование осуществимости моментального состояния налагает условия наотношения только между локальными моментальными состояниями соседних процессов, в то время как значимость является глобальным свойством моментального состояния всей системы. Однако далее мы покажем (теорема 10.5), чтоосуществимость моментального состояния равносильна его значимости, а также что такие моментальные состояния соответствуют согласованным сечениям.Сечение называется согласованным, если оно замкнуто влево относительно отношения причинно-следственной зависимости 2) .Определение 10.4.
Согласованным сечечнием на множестве событий Evназывается такое подмножество L ⊆ Ev, для которого выполняется соотношениеe ∈ L ∧ e0 e =⇒ e0 ∈ L.Теорема 10.5. Пусть S∗ — моментальное состояние системы и L —сечение, порожденное S∗ . Тогда равносильны следующие три утверждения:1) S∗ осуществимо;2) L согласовано;3) S∗ значимо.Д о к а з а т е л ь с т в о. Мы покажем, что из 1) следует 2), из 2) следует 3),и из 3) следует 1).2) Глобальной— Прим. перев.356Гл. 10.
Моментальные состояния системы10.2. Два алгоритма построения моментального состояния3571) ⇒ 2). Допустим, что состояние S∗ осуществимо. Чтобы убедиться в том,что L согласовано, рассмотрим e ∈ L и e0 e. По определению отношения достаточно показать, что включение e0 ∈L выполняется в следующих двух случаях.— Выполняется соотношение e0 p e (где p — это процесс, в котором происходят e0 и e). В таком случае включение e0 ∈ L выполняется благодаря тому,что L — сечение.— Событие e0 — это событие отправления сообщения, а событие e — соответствующее ему событие приема сообщения. Рассмотрим процесс p, в которомпроисходит событие e0 , процесс q, в котором происходит e, и сообщение m, которым обмениваются процессы. ТогдаПо теореме 2.21 существует выполнение вычисления F, состоящее из всехсобытий множества Ev, осуществляемых в том порядке, который представленпоследовательностью f.
Выполнение F содержит конфигурацию ∗ , которая возникает сразу же после осуществления всех предмоментальных событий.3) ⇒ 1). Если моментальное состояние S∗ является значимым, то конфигурация ∗ возникает при выполнении вычисления C. В каждом выполнении всякоесообщение не может быть доставлено по назначению, прежде чем оно будет отправлено. Отсюда следует, что для каждой пары процессов p и q имеет местосоотношение rcvd∗pq ⊆ sent∗pq . Поэтому состояние S∗ осуществимо.e ∈ L =⇒ m ∈ rcvd∗pq , поскольку e — предмоментальное событие=⇒ m ∈ sent∗pq , поскольку S∗ осуществимо=⇒ e0 ∈ L.10.2.
Два алгоритма построения моментального состояния2) ⇒ 3). Идея состоит в том, чтобы построить такое выполнение вычисления,в котором все предмоментальные события произошли ранее любого постмоментального события.Введем следующую нумерацию f = (f0 , f1 , . . .) событий множества Ev. Вначале перечислим все предмоментальные события из Ev в произвольном порядке,согласованном с отношением , а далее перечислим все постмоментальные события в произвольном порядке, согласованном с отношением (см. рис.
10.3).uHHHHu jHuuu u u u uue uJueuQJ eAQJQAUAueJsQuJJJu u u u uПространственновременнаядиаграмма CПоследовательность fРис. 10.3. Выполнение FЧтобы воспользоваться теоремой 2.21, нужно показать, что вся последовательность f согласована с отношением . Допустим, что f i fj ; если оба событияfi и fj являются предмоментальными, то имеет место неравенство i 6 j, посколькув f предмоментальные события перечислены в таком порядке, который согласован с отношением . По тем же причинам это неравенство выполняется и в томслучае, когда оба события fi и fj являются постмоментальными. Если же fi является предмоментальным событием, а событие fj является постмоментальным, тонеравенство i 6 j соблюдается в силу того, что в f все предмоментальные событияпредшествуют постмоментальным. Случай, когда f j является предмоментальнымсобытием, а fi — постмоментальным событием, исключен, ввиду того что сечениеL по предположению является согласованным; значит, если f j ∈ L и fi fj , то fi ∈∈ L, т.
е. fi является в этом случае предмоментальным событием. Отсюда следует,что последовательность f согласована с отношением .По теореме 10.5 достаточно скоординировать локальные моментальные состояния, чтобы гарантировать осуществимость полученного глобального моментального состояния. В результате требования, предъявляемые к алгоритму построения моментального состояния, ограничиваются следующими двумя свойствами.1.
Выбранные в каждом процессе локальные моментальные состояния должны быть реализованы.2. Получение постмоментального сообщения не может составлять предмоментальное событие.Во всех алгоритмах построения моментального состояния всякий процесс запечатлевает свое локальное моментальное состояние, до того как получит постмоментальное сообщение. Те два алгоритма, которые рассматриваются в настоящем параграфе, отличаются способом распознавания таких сообщений, а такжетем, как каждый процесс запечатлевает свое локальное моментальное состояние.Чтобы отличать сообщения в алгоритме построения моментального состоянияот сообщений в самом вычислении, мы будем называть сообщения первого видаконтрольными сообщениями, а сообщения второго вида базовыми сообщениями.10.2.1.
Алгоритм Ченди—ЛэмпортаВ этом параграфе мы будем придерживаться дополнительного предположенияо том, что во всех каналах соблюдается очередность передачи сообщений, т. е.для каждого отдельного канала получаемые по этому каналу сообщения следуютв том же порядке, в каком они были отправлены. В алгоритме Ченди —Лэмпорта(см. [45]), процессы сообщают друг другу о построении моментальных состоянийпутем отправления специальных сообщений (маркеров) hmkri по каждому каналу.
Каждый процесс, запечатлевая свое локальное состояние, отправляет маркерв точности один раз по каждому примыкающему к нему каналу; маркеры рассматриваются как контрольные сообщения. Получение сообщения hmkri каким-либопроцессом, который еще не запечатлел свое моментальное состояние, приводитк тому, что этот процесс запечатлевает свое моментальное состояние и такжеотправляет маркер hmkri (см. алгоритм 10.4, который выполняется параллельнос вычислением C).358var takenpГл. 10. Моментальные состояния системы: boolinit false ;Для запуска алгоритма:begin запомнить локальное состояние ; takenp := true ;forall q ∈ Neighp do send hmkri to qendЕсли был доставлен маркер:begin receive hmkri ;if not takenp thenbegin запомнить локальное состояние ; takenp := true ;forall q ∈ Neighp do send hmkri to qendendАлгоритм 10.4.
Алгоритм Ченди—Лэмпорта построения моментального состоянияЛемма 10.6. Если хотя бы один процесс запустит алгоритм 10.4, тоспустя конечный промежуток времени все процессы запечатлеют своелокальное моментальное состояние.Д о к а з а т е л ь с т в о. Поскольку каждый процесс запечатлевает моментальное состояние и отправляет сообщение hmkri не более одного раза, работаалгоритма построения моментального состояния системы рано или поздно завершится. Если процесс p к тому времени уже запечатлел свое моментальноесостояние и процесс q является соседом p, то процесс q также уже успел запечатлеть свое локальное состояние.
Это происходит потому, что сообщение hmkri,отправленное процессом p, было получено процессом q и вынудило его запечатлеть моментальное состояние, если только он не сделал этого ранее. Так какпо-меньшей мере один процесс запустил алгоритм, хотя бы один процесс запечатлел свое локальное состояние; связность сети приводит к тому, что этоуспевают сделать все процессы.Заметим, что алгоритм должен быть инициирован хотя бы одним процессом,но он будет работать правильно и в том случае, если он был запущен произвольным непустым множеством процессов.Теорема 10.7. Алгоритм Ченди—Лэмпорта (алгоритм 10.4) Вычисляет значимое моментальное состояние системы спустя конечный промежуток времени, после того как он был запущен хотя бы одним процессом.Д о к а з а т е л ь с т в о. Согласно предыдущей лемме алгоритму требуетсяконечный промежуток времени для вычисления моментального состояния системы. Остается показать, что построенное моментальное состояние системы является осуществимым, т.
е. получение каждого постмоментального (базового) сообщения составляет постмоментальное событие. Рассмотрим постмоментальноесообщение m, отправленное процессом p процессу q. Перед отправлением сообщения m, процесс p запечатлел свое моментальное локальное состояние и отпра-10.2. Два алгоритма построения моментального состояния359вил сообщение hmkri всем своим соседям, включая процесс q.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
