Распределенные алгоритмы (стр. 15 из 85)
и отсюда gpq = gqp .
Пусть ер и еq будут двумя событиями, которые появляются последовательно в исполнении, т.е. исполнение содержит подпоследовательность
..., g, ер(g), еq(ер(g)), ...
для некоторых g. Посылка теоремы 2.19 применима к этим событиям за исключением следующих двух случаев.
(1) p = q; или
(2) ер – событие отправки, и еq - соответствующее событие получения.
В самом деле, теорема явно утверждает, что p и q должны быть различными, и если еq получает сообщение, посланное в ер, событие отправки не применимо в начальной конфигурации события ep, как требуется. Таким образом, если одно из этих двух утверждений истина, события не могут появляться в обратном порядке, иначе они могут встречаться в обратном порядке и кроме того иметь результат в одной конфигурации. Запомните, что с глобальной точки зрения переходы не могут быть обменены, потому что (в нотации теоремы 2.19) переход из gр в gpq отличается от перехода из g в gq. Однако, с точки зрения процесса эти события неразличимы.
Тот факт, что конкретная пара событий не может быть обменена, выражается тем, что существует каузальное отношение между этими двумя событиями. Это отношение может быть расширено до частичного порядка на множестве событий в исполнении, называемого каузальный порядок исполнения.
Определение 2.20 Пусть Е – исполнение. Отношение í, называемое каузальным порядком, на событиях исполнения есть самое малое отношение, которое удовлетворяет
(1) Если е и f – различные события одного процесса и е появляется перед f, то е í f.
(2) Если s – событие отправки и r – соответствующее событие получения, то s í r.
(3) Отношение í транзитивно.
Мы пишем а í= b, чтобы обозначить (а í b Ú а = b). Так как í= есть частичный порядок, могут существовать события а и b, для которых ни а í= b ни b í= а не выполняется. Говорят такие события конкурирующие, в нотации а || b. На рисунке 2.1, b || f, d || i, и т.д.
Каузальный порядок был впервые определен Лампортом [Lam78] и играет важную роль в рассуждениях, относящихся к распределенным алгоритмам. Определение í подразумевает существование каузальной цепочки между каузально связанными событиями. Этим мы подразумеваем, что а í b включает существование последовательности а = е0 , е1 , ..., ек = b такой, что каждая пара последовательных событий в цепочке удовлетворяет либо (1), либо (2) в определении 2.20. Каузальная цепочка может быть даже выбрана так, что каждая пара, удовлетворяющая (1), есть последовательная пара событий в процессе, где они встречаются, т.е., нет событий между ними. На рисунке 2.1 каузальная цепочка между событием а и событием l есть последовательность а, f, g, h, j, k, l.
2.3.2 Эквивалентность исполнений: вычисления
В этом подразделе показывается, что события исполнения могут быть переупорядочены в любом порядке, согласующимся с каузальным порядком, без воздействия на результат исполнения. Это переупорядочивание событий вызывает другую последовательность конфигураций, но это исполнение будет рассматриваться как эквивалент исходного исполнения.
Пусть f = (f0 , f1 , f2 ,...) будет последовательностью событий. Эта последовательность - последовательность событий относящихся к исполнению F = (d0, d1, d2, ...), если для каждого i, fi применимо в di и fi (di) = di+1. В этом случае F называется включенным исполнением последовательности f. Мы хотели бы, чтобы F уникально определялась последовательностью f, но это не всегда так. Если для некоторого процесса p нет события в p, включенного в f, то состояние процесса p может быть произвольным начальным состоянием. Однако, если f содержит по крайней мере одно событие из р, то первое событие в р, скажем (с, х, у, d), определяет, что начальное состояние процесса р будет с. Поэтому, если f содержит по крайней мере одно событие в каждом процессе, d0 уникально определено, и это определяет целое исполнение уникально.
Теперь пусть Е = (g0, g1, g2, ... ) будет исполнением с ассоциированной последовательностью событий Е’ = (е0 , е1 , е2 , ...) и положим, что f –перестановка из Е’. Это означает, что существует перестановка s натуральных чисел (или множества {0, ..., k-1}, если Е – конечное исполнение с k событиями) таких, что fi = еs(i). Перестановка (f0 , f1 , f2 , ...) событий из Е согласующаяся с каузальным порядком, если fi í= fj подразумевает i £ j, т.е., если нет события, которому предшествует в последовательности событие, которому оно само каузально предшествует.
Теорема 2.21 Пусть f = (f0 , f1 , f2 , ...) – перестановка событий из Е, которая согласуется с каузальным порядком исполнения Е. Тогда f определяет уникальное исполнение F, начинающееся в начальной конфигурации из Е. F имеет столько же событий сколько и Е, и если Е конечно, то последняя конфигурация из F такая же как и последняя конфигурация из Е.
Доказательство. Конфигурации из F строятся одна за другой, и чтобы построить di+1 достаточно показать, что fi применимо в di. Возьмем d0 = g0.
Предположим, что для всех j < i, fj применимо в конфигурации dj и dj+1 = fj (dj ). Пусть di = (cp1 , ..., cpN , M) и пусть fi =(c, x, y, d) будет событие в процессе р, тогда событие fi применимо в di, если сp = c и х Í М.
Чтобы показать, что сp = c нужно различать два случая. В обоих случаях мы должны помнить, что каузальный порядок исполнения Е абсолютно упорядочивает события в процессе р. Это подразумевает, что события в процессе р появляются в точно таком же порядке и в f и в Е’.
Случай 1: fi - первое событие в р из f, тогда ср – это начальное состояние р. Но тогда fi – также первое событие в р из Е’, что подразумевает, что с – это начальное состояние р. Следовательно, с = ср.
Случай 2: fi – не первое событие в р из f. Пусть последнее событие в р из f перед fi будет fi' = (c’, x’, y’, d’), тогда ср = d’. Но тогда fi' также последнее событие в р перед fi из Е’, что подразумевает, что с = d’. Следовательно, с = ср.
Чтобы показать, что х Í М мы должны помнить, что соответствующие события приема и посылки встречаются в одном порядке и в f и в Е’. Если fi не событие посылки, то х = Æ и х Í М выполняется тривиально. Если fi – это событие посылки, пусть fi будет соответствующим событием посылки. Так как fj í fi , j < i выполняется, т.е., событие посылки предваряет fi в f, следовательно, х Í М.
Мы сейчас показали, что для каждого i, fi применимо в di, и di+1 может быть взято как fi(di). Мы должны, наконец, показать, что последние конфигурации из F и Е совпадают, если Е конечно. Пусть gk будет последней конфигурацией из Е. Если Е’ не содержит события в р, то состояние р в gk равно его начальному состоянию. Так как f также не содержит события в р, то состояние р в dk также равно начальному состоянию, отсюда состояние р в dk равняется его состоянию в gk. Иначе, состояние р в gk есть состояние после последнего события в р из Е’. Это также последнее событие в р из f, так что это также состояние р в dk.
Сообщения в процессе передачи в gk есть такие сообщения, для которых событию посылки нет соответствующего события получения в Е’. Но так как Е’ и f содержат один и тот же набор событий, те же сообщения в процессе передачи в последней конфигурации из F.
Рис. 2.2 Пространственно-временная диаграмма эквивалентная рис. 2.1
Исполнения F и Е имеют один набор событий, и каузальный порядок этих событий – один и тот же для Е и F. Поэтому, также, в этом случае Е – это перестановка событий из F, которая согласуется с каузальным порядком исполнения F. Если применить условие теоремы 2.21, мы можем сказать, что Е и F – эквивалентные исполнения, что обозначается как E ~ F.
Рис. 2.2 показывает временную диаграмму исполнения, эквивалентного исполнению, изображенному на рис. 2.1. Эквивалентные временные диаграммы могут быть получены с помощью «трансформаций резиновой ленты» [Mat89c]. Полагая, что временная ось процесса может быть сжата и растянута пока стрелки сообщений продолжают указывать направо, рис. 2.1 может быть деформирован до рис. 2.2.
Хотя изображенные исполнения эквивалентны и содержат одинаковый набор событий, они не могут содержать одинаковый набор конфигураций. Рис. 2.1 содержит конфигурацию (g”), в которой сообщение, посланное в событии е и сообщение, посланное в событии l, передаются одновременно . Рис. 2.2 не содержит такой конфигурации, потому что сообщение, посланное в событии l, получено перед свершением события е.
Глобальный наблюдатель, кто имеет доступ к действительной последовательности событий, может различать два эквивалентных исполнения, т.е. может наблюдать либо одно, либо другое исполнение. Однако, процессы не могут различать две эквивалентных исполнения, т.к. для них невозможно решить, какое из двух исполнений имеет место. Это иллюстрируется следующим. Предположим, что мы должны решить будут ли посылаться сообщения в событии е и будут в передаче одновременно. Существует булевская переменная sim в одном из процессов, которая должна установлена в истину, если сообщения были в передаче одновременно, и ложь иначе. Таким образом, в последней конфигурации рис. 2.1 значение sim – истина, и в последней конфигурации на рис 2.2 значение – ложь. По теореме 2.21, конфигурации равны, что показывает, что требуемое присваивание sim невозможно.
Класс эквивалентности при отношении ~ полностью характеризуется набором событий и каузальным порядком на этих событиях. Классы эквивалентности называются вычислениями алгоритма.