Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 94

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 94)

10.2. Несогласованное моментальное состояниеТребование осуществимости моментального состояния налагает условия наотношения только между локальными моментальными состояниями соседних про­цессов, в то время как значимость является глобальным свойством моменталь­ного состояния всей системы. Однако далее мы покажем (теорема 10.5), чтоосуществимость моментального состояния равносильна его значимости, а так­же что такие моментальные состояния соответствуют согласованным сечениям.Сечение называется согласованным, если оно замкнуто влево относительно от­ношения причинно-следственной зависимости 2\Определение 10.4.

Согласованным сечечнием на множестве событий Evназывается такое подмножество L С Ev, для которого выполняется соотношениеТеорема 10.5. Пусть S * — моментальное состояние системы и L —сечение, порожденное S*. Тогда равносильны следующие три утвержде­ния :1) 5* осуществимо',2) L согласовано',3) 5* значимо.Доказательство.и из 3) следует 1 ).2*Глобальной— Прим, перев.Мы покажем, что из 1) следует 2), из 2) следует 3),Гл. 10.

Моментальные состояния системы3561) =£> 2). Допустим, что состояние 5* осуществимо. Чтобы убедиться в том,что L согласовано, рассмотрим е € L и е' -< е. По определению отношения ■<достаточно показать, что включение e'&L выполняется в следующих двух случаях.— Выполняется соотношение е' ■<р е (где р — это процесс, в котором про­исходят е' и е).

В таком случае включение е' € L выполняется благодаря тому,что L — сечение.— Событие е' — это событие отправления сообщения, а событие е — соот­ветствующее ему событие приема сообщения. Рассмотрим процесс р, в которомпроисходит событие е' , процесс q, в котором происходит е, и сообщение т, ко­торым обмениваются процессы. Тогдае € L =>• т € rcvd*q, поскольку е — предмоментальное событие=> т € sent*q, поскольку S* осуществимо=*> е' е L.2) =Ф 3). Идея состоит в том, чтобы построить такое выполнение вычисления,в котором все предмоментальные события произошли ранее любого постмомен­тального события.Введем следующую нумерацию / = (Jo, fi, ...) событий множества Ev. Вна­чале перечислим все предмоментальные события из Ev в произвольном порядке,согласованном с отношением ■<, а далее перечислим все постмоментальные со­бытия в произвольном порядке, согласованном с отношением ■< (см.

рис. 10.3).—<1Пространственновременнаядиаграмма С\7~—1ы ы/0\w чJXX<м м мtПоследовательность fРис. 10.3. Вы полнение/7Чтобы воспользоваться теоремой 2.21, нужно показать, что вся последова­тельность / согласована с отношением ■<. Допустим, что fi ff, если оба событияJ и fj являются предмоментальными, то имеет место неравенство i ^ посколькув / предмоментальные события перечислены в таком порядке, который согласо­ван с отношением ■<. По тем же причинам это неравенство выполняется и в томслучае, когда оба события fi и fj являются постмоментальными. Если же /, явля­ется предмоментальным событием, а событие fj является постмоментальным, тонеравенство i ^ / соблюдается в силу того, что в / все предмоментальные событияпредшествуют постмоментальным.

Случай, когда fj является предмоментальнымсобытием, г fi — постмоментальным событием, исключен, ввиду того что сечениеL по предположению является согласованным; значит, если fj&L и J ■<fj, то / , <Е6.L, т. е. fi является в этом случае предмоментальным событием. Отсюда следует,что последовательность / согласована с отношением ■<.10.2. Два алгоритма построения моментального состояния357По теореме 2.21 существует выполнение вычисления F, состоящее из всехсобытий множества Ev, осуществляемых в том порядке, который представленпоследовательностью /. Выполнение F содержит конфигурацию у*, которая воз­никает сразу же после осуществления всех предмоментальных событий.3)=>• 1).

Если моментальное состояние S* является значимым, то конфигура­ция у* возникает при выполнении вычисления С. В каждом выполнении всякоесообщение не может быть доставлено по назначению, прежде чем оно будет от­правлено. Отсюда следует, что для каждой пары процессов р и q имеет местосоотношение rcvd*pq С sent*pq. Поэтому состояние 5* осуществимо.□10.2. Два алгоритма построения моментального состоянияПо теореме 10.5 достаточно скоординировать локальные моментальные со­стояния, чтобы гарантировать осуществимость полученного глобального момен­тального состояния. В результате требования, предъявляемые к алгоритму по­строения моментального состояния, ограничиваются следующими двумя свой­ствами.1.

Выбранные в каждом процессе локальные моментальные состояния долж­ны быть реализованы.2. Получение постмоментального сообщения не может составлять предмоментальное событие.Во всех алгоритмах построения моментального состояния всякий процесс за­печатлевает свое локальное моментальное состояние, до того как получит пост­моментальное сообщение. Те два алгоритма, которые рассматриваются в настоя­щем параграфе, отличаются способом распознавания таких сообщений, а такжетем, как каждый процесс запечатлевает свое локальное моментальное состояние.Чтобы отличать сообщения в алгоритме построения моментального состоянияот сообщений в самом вычислении, мы будем называть сообщения первого видаконтрольными сообщениями, а сообщения второго вида базовыми сообщениями.10.2.1.

Алгоритм Ченди—ЛэмпортаВ этом параграфе мы будем придерживаться дополнительного предположенияо том, что во всех каналах соблюдается очередность передачи сообщений, т. е.для каждого отдельного канала получаемые по этому каналу сообщения следуютв том же порядке, в каком они были отправлены. В алгоритме Ченди—Лэмпорта(см. [45]), процессы сообщают друг другу о построении моментальных состоянийпутем отправления специальных сообщений (маркеров) (mkr) по каждому кана­лу. Каждый процесс, запечатлевая свое локальное состояние, отправляет маркерв точности один раз по каждому примыкающему к нему каналу; маркеры рассмат­риваются как контрольные сообщения.

Получение сообщения (mkr) каким-либопроцессом, который еще не запечатлел свое моментальное состояние, приводитк тому, что этот процесс запечатлевает свое моментальное состояние и такжеотправляет маркер (mkr) (см. алгоритм 10.4, который выполняется параллельнос вычислением С).Гл. 10. Моментальные состояния системы358vartakerip:boolinit f a l s e ;Для запуска алгоритма:begin запомнить локальное состояние ; t a k e n p := t r u e ;forall q € N e ig h p do send (mkr) to qendЕсли был доставлен маркер:begin receive (mkr) ;if not takerip thenbegin запомнить локальное состояние ; t a k e n p :=forall q 6 N e ig h p do send (mkr) to qendtru e;endАлгоритм 10.4.

Алгоритм Ченди—Лэмпорта построения моментального состоянияЛемма 10.6. Если хотя бы один процесс запустит алгоритм 10.4, тоспустя конечный промежуток времени все процессы запечатлеют своелокальное моментальное состояние.Д о к а з а т е л ь с т в о . Поскольку каждый процесс запечатлевает момен­тальное состояние и отправляет сообщение (mkr) не более одного раза, работаалгоритма построения моментального состояния системы рано или поздно за­вершится. Если процесс р к тому времени уже запечатлел свое моментальноесостояние и процесс q является соседом р, то процесс q также уже успел запе­чатлеть свое локальное состояние. Это происходит потому, что сообщение (mkr),отправленное процессом р, было получено процессом q и вынудило его запечат­леть моментальное состояние, если только он не сделал этого ранее.

Так какпо-меныней мере один процесс запустил алгоритм, хотя бы один процесс за­печатлел свое локальное состояние; связность сети приводит к тому, что этоуспевают сделать все процессы.□Заметим, что алгоритм должен быть инициирован хотя бы одним процессом,но он будет работать правильно и в том случае, если он был запущен произволь­ным непустым множеством процессов.Теорема 10.7. Алгоритм Ченди—Лэмпорта (алгоритм 10.4) Вычисля­ет значимое моментальное состояние системы спустя конечный проме­жуток времени, после того как он был запущен хотя бы одним процессом.Д о к а з а т е л ь с т в о . Согласно предыдущей лемме алгоритму требуетсяконечный промежуток времени для вычисления моментального состояния систе­мы. Остается показать, что построенное моментальное состояние системы явля­ется осуществимым, т.

е. получение каждого постмоментального (базового) со­общения составляет постмоментальное событие. Рассмотрим постмоментальноесообщение т, отправленное процессом р процессу q. Перед отправлением сооб­щения т, процесс р запечатлел свое моментальное локальное состояние и отпра-10.2. Два алгоритма построения моментального состояния359вил сообщение (mkr) всем своим соседям, включая процесс q. Так как в каналахподдерживается очередность сообщений, процесс q получил сообщение (mkr),до того как получил т, и в соответствии с приведенным алгоритмом процесс qзапечатлел свое моментальное состояние сразу по получении этого сообщенияили еще ранее того. Следовательно, получение сообщения т относится к числупостмоментальных событий.□В алгоритме Ченди—Лэмпорта требуется совершить обмен 2\Е\ сообщениями(mkr) и использовать один дополнительный бит памяти (и, конечно же, к это­му следует добавить память для хранения моментального состояния) в каждомпроцессе.

Характеристики

Список файлов книги