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

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

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

С этой после­довательностью событий может быть связано выполнение F = (8 о, §ь 8 2 , ...),если для каждого i событие /; является допустимым в конфигурации 8 ; и приэтом /;(8 ;) = 8 ;+ 1 . В таком случае будем говорить, что последовательность / под­разумевает выполнение F. Мы бы предпочли, чтобы выполнение F однозначноопределялось последовательностью /, но это не всегда возможно: если ни однособытие процесса р не содержится в последовательности /, то любое состояниепроцесса р можно взять в качестве начального. Если, однако, в / содержится хотябы одно событие процесса р, то первое событие (с, х, у, d), которое совершаетсяв процессе р, указывает на то, что начальным состоянием процесса р является с.Таким образом, если в / содержится хотя бы одно событие каждого процесса, то70Гл.

2. Модельначальная конфигурация §о определяется однозначно, и за счет этого однозначноопределяется и все выполнение.Рассмотрим некоторое выполнение Е = (уо, у i , уг, • • •) и связанную с ним по­следовательность событий Е = (ео, в\, в2 , •••)• Предположим, что задана пере­становка / элементов последовательности Е.

Это означает, что существует такаяперестановка о на множестве натуральных чисел (или на конечном множестве{0,— 1}, если Е — конечное выполнение, в котором совершается k собы­тий), что fi = ea(i). Перестановка (/о, /ь / 2 , • • •) событий выполнения Е сохраня­ет причинно-следственный порядок, если отношение fi ■<fj влечет неравенство/ ^ /, т. е. ни одно событие не появляется в этой последовательности прежде тогособытия, от которого оно зависит.Теорема 2.21.

Пусть / = (/о, / 1 , / 2 , • • •) — перестановка событий выпол­нения Е, сохраняющая причинно-следственный порядок событий выполне­ния . Тогда / определяет единственное выполнение F, которое начинаетсяс той же конфигурации , что и выполнение Е. При этом в F совершаетсястолько же событий, сколько их совершается в Е, и в том случае, еслиЕ — конечное выполнение, то последняя конфигурация выполнения F бу­дет точно такой же, как последняя конфигурация выполнения Е.Д о к а з а т е л ь с т в о . Будем формировать конфигурации выполнения F по­следовательно одну за другой; для построения Si+i достаточно показать, что со­бытие fi является допустимым в конфигурации 8,-.

Будем полагать, что 8о = уоПредположим, что для всех / < i событие fj является допустимым в кон­фигурации bj и при этом 8y+i = fj(bj). Пусть 8; = (cPl, . . . , cPN, М), и пустьfi = (с, х, у, d) — это событие процесса р. Тогда событие fi будет допустимымв конфигурации 8;, если ср = с и х С М.Чтобы показать, что имеет место равенство ср = с, нужно рассмотреть дваслучая. В обоих случаях мы принимаем во внимание то обстоятельство, чтопричинно-следственный порядок в исполнении Е линейно упорядочивает собы­тия процесса р\ это означает, что порядок расположения событий процесса рв последовательности / будет тем же самым, что и в последовательности Е.Случай 1: ft — это первое событие процесса р в последовательности /. То­гда ср является начальным состоянием процесса р.

Значит, fi также являетсяи первым событием процесса р в последовательности Е, и поэтому с — началь­ное состояние процесса р. Следовательно, с = ср.Случай 2: fi не является первым событием процесса р в последовательно­сти /. Пусть последним событием процесса р в последовательности /, предше­ствующим fi, является событие /г = (с', х ', у', d'). Тогда ср = d!. Но тогда /г —это также и последнее событие процесса р, предшествующее fi в последователь­ности Е. Поэтому с = d!, и отсюда следует равенство с = ср.Чтобы показать, что имеет место включение х С М, мы заметим, что соот­ветствующие друг другу события отправления и приема сообщений расположеныв последовательностях / и Е в одном и том же порядке. Если fi не является собы­тием приема сообщения, то х = 0 , и включение х С М, очевидно, выполняется.Если же fi — это событие приема сообщения, то рассмотрим соответствующее2.3.

Причинно-следственный порядок событий и логические часы71ему событие отправления сообщения fj. Так как fj -< fi, справедливо неравенство/ < г, т. е. событие отправления сообщения предшествует в последовательности /событию fi. Следовательно, х С М.Покажем теперь, что для любого i событие fi является допустимым в кон­фигурации 8; и при этом в качестве 8;+i можно взять /,(8,). В конечном итогемы должны показать, что последние конфигурации выполнений F и Е совпадают,если Е — конечная последовательность. Пусть у* — это последняя конфигурациявыполнения Е. Если в £ не содержится ни одного события процесса р, то состо­янием процесса р в конфигурации у* является начальное состояние.

Коль скоров / также не содержится ни одного события процесса р, состоянием процессар в конфигурации 8* также будет начальное состояние. Следовательно, состоя­ние процесса р в конфигурации 8* будет тем же самым, что и в конфигурации у*.В противном случае состояние процесса р в конфигурации у* — это то состояние,в которое переходит процесс р, после того как в этом процессе совершится по­следнее событие из числа тех, которые содержатся в последовательности Ё. Этособытие также является последним событием, которое совершается в процессер по ходу осуществления последовательности событий /.

Значит, точно таким жебудет и состояние процесса р в конфигурации 8*.Сообщения, пребывающие на этапе пересылки в конфигурации у*, — этов точности те самые сообщения, для которых события отправления сообщенийне имеют парных им соответствующих событий приема сообщений в последова­тельности Е. Но коль скоро в последовательностях Ё и / содержится одна и таже совокупность сообщений, те же самые сообщения будут пребывать на этапепересылки и в последней конфигурации последовательности F.□В обоих выполнениях F и Е происходит одна и та же совокупность событий,и причинно-следственный порядок на множестве событий выполнения Е тот жесамый, что и на множестве событий выполнения F.

Поэтому последовательностьсобытий Е может быть образована в результате перестановки событий выполне­ния F, сохраняющей частичный порядок на множестве событий этого выполнения.В том случае, если выполняются условия теоремы 2.21, мы будем говорить, чтовыполнения Е и F эквивалентны и обозначать это отношение Е ~ F.На рис. 2.2 изображена временная диаграмма выполнения, эквивалентноготому выполнению, которое представлено на рис.

2.1. Эквивалентные временныедиаграммы можно получить из заданной диаграммы путем ее растяжения и сжа­тия, как резиновой ленты; см. [142]. Представьте себе, что оси времени отдельныхпроцессов можно сжимать и растягивать как угодно, лишь бы только стрелки наних оставались ориентированными слева направо, и диаграмма на рис. 2.1 пре­вратиться в диаграмму на рис.

2.2.Хотя изображенные на этих рисунках выполнения эквивалентны и в них про­исходит одно и то же множество событий, эти выполнения содержат разныесовокупности конфигураций. Выполнение, диаграмма которого изображена нарис. 2.1, содержит конфигурацию у, в которой оба сообщения, отправленныепри осуществлении событий е й /, пребывают на этапе пересылки одновременно.А выполнение, диаграмма которого изображена на рис. 2.2, не содержит ни од-72Гл. 2. МодельаЬсР 1Р2№Р4FafBhibkdliecРис. 2.2. Пространственно-временная диаграмма, эквивалентная диаграмме,изображенной на рис. 2.1.ной такой конфигурации, поскольку сообщение, отправленное при осуществлениисобытия /, достигает адресата раньше , чем происходит событие е.Сторонний наблюдатель, который имеет возможность видеть подлинную по­следовательность событий, способен отличить одно эквивалентное выполнениеот другого, т.

е. он всякий раз видит только одно из возможных выполнений. Од­нако процессы не могут отличить два эквивалентных выполнения, так как с точкизрения процессов невозможно понять, какое из двух эквивалентных выполненийпроисходит на самом деле. Это можно объяснить на следующем примере. Пред­положим, что нужно выяснить, действительно ли сообщения, отправленные приосуществлении событий е й / , пребывают на этапе пересылки одновременно. З а ­ведем в одном из процессов булеву переменную sim, значение которой положимравным true, если сообщения пребывают на этапе пересылки одновременно, иравным false в противном случае. Тогда в последней конфигурации выполнения,изображенного на рис. 2.1, значение переменной sim должно быть равно true,а в последней конфигурации выполнения, изображенного на рис.

2.2, значениепеременной sim должно быть равно false. Но по теореме 2.21 эти конфигура­ции должны быть эквивалентны, и поэтому ожидаемого присваивания значенийпеременной sim достичь невозможно.Класс эквивалентности выполнений по отношению эквивалентности ~ од­нозначно определяется множеством событий и действующим на нем причинноследственным порядком; эти классы эквивалентности называются вычислениямиалгоритма.Определение 2.22.

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

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