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

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

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

Такая перестановка событий приводит к другой последовательности конфигураций, но полученное при этом выполнение будет считатьсяэквивалентным исходному выполнению.Пусть задана последовательность событий f = (f0 , f1 , f2 , . . .). С этой последовательностью событий может быть связано выполнение F = ( 0 , 1 , 2 , . . .),если для каждого i событие fi является допустимым в конфигурации i и приэтом fi ( i) = i+1 . В таком случае будем говорить, что последовательность f подразумевает выполнение F. Мы бы предпочли, чтобы выполнение F однозначноопределялось последовательностью f, но это не всегда возможно: если ни однособытие процесса p не содержится в последовательности f, то любое состояниепроцесса p можно взять в качестве начального.

Если, однако, в f содержится хотябы одно событие процесса p, то первое событие (c, x, y, d), которое совершаетсяв процессе p, указывает на то, что начальным состоянием процесса p является c.Таким образом, если в f содержится хотя бы одно событие каждого процесса, тоqpБудем использовать запись a b для обозначения отношения, которое определятся формулой (a ≺ b ∨ a = b). Поскольку является отношением частичного порядка, могут найтись события a и b, для которых не выполняется a bи b a.

Такие события будем называть параллельными и будем использоватьдля обозначения этого факта запись a k b. Например, для выполнения, изображенного на рис 2.1, имеют место b k f, d k i, и т. п..Причинно-следственный порядок был впервые введен в работе Лампорта[124] , и он играет значительную роль при проведении логического анализа распределенных алгоритмов.

Как следует из определения отношения ≺, события,связанные причинно-следственной зависимостью, могут образовывать причинноследственные цепочки. Это означает, что выполнимость отношения a ≺ b предполагает существование такой последовательности событий a = e 0 , e1 , . . . , ek == b, что для каждой пары соседних ее членов выполняется либо п. 1), либоп. 2) определения 2.20. Можно выбрать такую причинно-следственная цепочку,в которой любые два события, удовлетворяющие п. 1), происходят в том процессе, к которому они относятся, последовательно, т.

е. между ними не происходит никаких событий. Для выполнения, изображенного на рис. 2.1, причинноследственной цепочкой между событием a и событием l может служить последовательность a, f, g, h, j, k, l.Учитывая, что рассматриваемые процессы равноправны, мы можем, применяя теже рассуждения, показать, что событие ep является допустимым в конфигурацииq = eq ( ).

Рассмотрим конфигурацию qp = ep ( q) и заметим, что= (. . . , dp , . . . , dq , . . . , ((M \ xp ∪ yp) \ xq) ∪ yq ).pq691) если e и f — два разных события одного и того же процесса и при этомсобытие e происходит прежде события f, то e ≺ f;2) если s — это событие отправления сообщения, а r — вазаимосвязанноес ним событие приема сообщения, то s ≺ r;3) Отношение ≺ обладает свойством транзитивности.Так как xq ⊆ M и xq ∩ xp = ∅, справедливо включение xq ⊆ (M \ xp ∪ yp), и поэтомусобытие eq является допустимым в конфигурации p . Рассмотрим конфигурациюpq = eq ( p) и заметим, что2.3.

Причинно-следственный порядок событий и логические часы682.3. Причинно-следственный порядок событий и логические часыему событие отправления сообщения fj . Так как fj ≺ fi , справедливо неравенствоj < i, т. е. событие отправления сообщения предшествует в последовательности fсобытию fi . Следовательно, x ⊆ M.Покажем теперь, что для любого i событие fi является допустимым в конфигурации i и при этом в качестве i+1 можно взять fi ( i). В конечном итогемы должны показать, что последние конфигурации выполнений F и E совпадают,если E — конечная последовательность.

Пусть k — это последняя конфигурациявыполнения E. Если в Ē не содержится ни одного события процесса p, то состоянием процесса p в конфигурации k является начальное состояние. Коль скоров f также не содержится ни одного события процесса p, состоянием процессаp в конфигурации k также будет начальное состояние. Следовательно, состояние процесса p в конфигурации k будет тем же самым, что и в конфигурации k .В противном случае состояние процесса p в конфигурации k — это то состояние,в которое переходит процесс p, после того как в этом процессе совершится последнее событие из числа тех, которые содержатся в последовательности Ē. Этособытие также является последним событием, которое совершается в процессеp по ходу осуществления последовательности событий f.

Значит, точно таким жебудет и состояние процесса p в конфигурации k .Сообщения, пребывающие на этапе пересылки в конфигурации k , — этов точности те самые сообщения, для которых события отправления сообщенийне имеют парных им соответствующих событий приема сообщений в последовательности Ē. Но коль скоро в последовательностях Ē и f содержится одна и таже совокупность сообщений, те же самые сообщения будут пребывать на этапепересылки и в последней конфигурации последовательности F.Теорема 2.21. Пусть f = (f0 , f1 , f2 , . . .) — перестановка событий выполнения E, сохраняющая причинно-следственный порядок событий выполнения .

Тогда f определяет единственное выполнение F, которое начинаетсяс той же конфигурации, что и выполнение E. При этом в F совершаетсястолько же событий, сколько их совершается в E, и в том случае, еслиE — конечное выполнение, то последняя конфигурация выполнения F будет точно такой же, как последняя конфигурация выполнения E.Д о к а з а т е л ь с т в о. Будем формировать конфигурации выполнения F последовательно одну за другой; для построения i+1 достаточно показать, что событие fi является допустимым в конфигурации i . Будем полагать, что 0 = 0 .Предположим, что для всех j < i событие fj является допустимым в конфигурации j и при этом j+1 = fj ( j).

Пусть i = (cp1 , . . . , cpN , M), и пустьfi = (c, x, y, d) — это событие процесса p. Тогда событие fi будет допустимымв конфигурации i , если cp = c и x ⊆ M.Чтобы показать, что имеет место равенство cp = c, нужно рассмотреть дваслучая. В обоих случаях мы принимаем во внимание то обстоятельство, чтопричинно-следственный порядок в исполнении E линейно упорядочивает события процесса p; это означает, что порядок расположения событий процесса pв последовательности f будет тем же самым, что и в последовательности Ē.Случай 1: fi — это первое событие процесса p в последовательности f. Тогда cp является начальным состоянием процесса p.

Значит, f i также являетсяи первым событием процесса p в последовательности Ē, и поэтому c — начальное состояние процесса p. Следовательно, c = c p .Случай 2: fi не является первым событием процесса p в последовательности f. Пусть последним событием процесса p в последовательности f, предшествующим fi , является событие fi0 = (c0 , x0 , y0 , d0). Тогда cp = d0 . Но тогда fi0 —это также и последнее событие процесса p, предшествующее f i в последовательности Ē. Поэтому c = d0 , и отсюда следует равенство c = cp .Чтобы показать, что имеет место включение x ⊆ M, мы заметим, что соответствующие друг другу события отправления и приема сообщений расположеныв последовательностях f и Ē в одном и том же порядке. Если fi не является событием приема сообщения, то x = ∅, и включение x ⊆ M, очевидно, выполняется.Если же fi — это событие приема сообщения, то рассмотрим соответствующееначальная конфигурация 0 определяется однозначно, и за счет этого однозначноопределяется и все выполнение.Рассмотрим некоторое выполнение E = ( 0 , 1 , 2 , .

. .) и связанную с ним последовательность событий Ē = (e0 , e1 , e2 , . . .). Предположим, что задана перестановка f элементов последовательности Ē. Это означает, что существует такаяперестановка на множестве натуральных чисел (или на конечном множестве{0, . . . , k − 1}, если E — конечное выполнение, в котором совершается k событий), что fi = e (i) . Перестановка (f0 , f1 , f2 , .

. .) событий выполнения E сохраняет причинно-следственный порядок, если отношение fi fj влечет неравенствоi 6 j, т. е. ни одно событие не появляется в этой последовательности прежде тогособытия, от которого оно зависит.71Гл. 2. Модель70В обоих выполнениях F и E происходит одна и та же совокупность событий,и причинно-следственный порядок на множестве событий выполнения E тот жесамый, что и на множестве событий выполнения F. Поэтому последовательностьсобытий Ē может быть образована в результате перестановки событий выполнения F, сохраняющей частичный порядок на множестве событий этого выполнения.В том случае, если выполняются условия теоремы 2.21, мы будем говорить, чтовыполнения E и F эквивалентны и обозначать это отношение E ∼ F.На рис.

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

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

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