Реферат: Распределенные алгоритмы
Если приняты свойства справедливости, то можно заключить из более слабых посылок (чем в теореме 2.17), что Р в конце концов станет истиной. Значение нормирующей функции не должно уменьшаться при каждом переходе. Предположение справедливости может быть использовано, чтобы показать, что бесконечные исполнения содержат переходы определенного типа бесконечно часто. Затем будет достаточно показать, что f никогда не увеличивается, а уменьшается с каждым переходом этого типа.
В некоторых случаях мы будем использовать следующий результат, который есть специальный случай теоремы 2.17
Теорема 2.18 Если S завершается правильно и есть число К такое, что каждое исполнение содержит по крайней мере К переходов, то Р истина в некоторой конфигурации каждого исполнения.
Рис. 2.1 Пример пространственно-временной диаграммы
2.3 Каузальный порядок событий и логические часы
Взгляд на исполнения как последовательности переходов естественным образом порождает понятие времени в исполнениях. Говорят, что переход а появляется раньше перехода b, если a встречается в последовательности перед b. Для исполнения Е = (g0, g1, ...) определим ассоциированную последовательность событий Е’=(е0, е1, ...), где еi – это событие, при котором конфигурация изменяется из gi в gi+1. Заметьте, что каждое исполнение определяет уникальную последовательность событий этим путем. Исполнение может быть визуализировано в пространственно-временной диаграмме, рисунок 2.1, которой, представляет пример. В такой диаграмме, горизонтальная линия нарисована для каждого процесса, и каждое событие нарисовано точкой на линии процесса, где оно имеет место. Если сообщение m послано при событии s и получено при событии r, стрелка рисуется от s к r. Говорят, что события s и r соответственные в этом случае.
Как мы увидим в подразделе 2.3.1, события распределенного исполнения могут иногда быть взаимно обменены без воздействия на последующие конфигурации исполнения. Поэтому понятие времени как абсолютного порядка на событиях исполнения не приемлемо для распределенных исполнений, и вместо этого представляется понятие каузальной зависимости. Эквивалентность исполнений при переупорядочивании событий изучается в подразделе 2.3.2. Мы обсуждаем в подразделе 2.3.3 как могут быть определены часы для измерения каузальной зависимости (а не времени), и представляем логические часы Лампорта, важный пример таких часов.
2.3.1 Независимость и зависимость событий
Уже было замечено, что переходы распределенной системы влияют, и подвержены влиянию, только на часть конфигураций. Это ведет к тому наблюдению, что два последовательных события, влияя на разделенные части конфигурации, независимы и могут также появляться в обратном порядке. Для систем с асинхронной передачей сообщений, это выражается в следующей теореме.
Теорема 2.19 Пусть g будет конфигурацией распределенной системы (с асинхронной передачей сообщений) и пусть ер и еq будут событиями различных процессов р и q, применимых в g. Тогда ер применимо в еq(g), еq применимо в ер(g), и ер(еq(g)) = еq(ер(g)).
Доказательство. Чтобы избежать анализа случаев, которые есть посылка, получение, или внутренние события, мы представим каждое событие однородной нотацией (с, х, у, d). Здесь с и d обозначают состояние процесса до и после события, х – набор сообщений, полученных во время события, и у – набор сообщений, посланных во течение события. Таким образом, внутренне событие (с, d) обозначается как (c,Æ,Æ,d), событие отправки (с, m, d) обозначается как (с, Æ, {m}, d), и событие приема (с, m, d) – (c, {m}, Æ, d). В этой нотации, событие е = (с, x, y, d) процесса p применимо в конфигурации g = (Сp1, ..., Cp, ..., СрN, M), если ср = с и x Í M. В этом случае
е(g) = (Сp1, ..., d, ..., (M \ x) È у).
Теперь предположим ер = (bp, xр, ур, dp) и еq = (bq, xq, уq, dq) применимы в
g = (..., ср, ..., сq, ..., M),
то есть ср = bp, cq = bq, xp
Í M, и xq Í M. Важное наблюдение состоит в том,
что хр и xq разделены, сообщение в xp (если
есть такое) имеет назначением р, в то время как сообщение в хq (если
есть такое) имеет назначением q.
Запишем gр = ер(g), и запомним что
gр = (..., dp, ..., cq, ..., (M \ xp ) È ур ).
Так как xq Í M и xq Ç хр = Æ, следует, что хq Í (M \ xp È ур ), и отсюда еq применимо в gр. Запишем gpq = eq(gр), и запомним, что
gрq = (..., dp, ..., dq, ..., ((M \ xp È ур ) \ xq ) È уq ).
С помощью симметричного аргумента может быть показано, что ер применимо в gq = eq(g). Запишем gqp = ep(gq), и запомним, что
gqp = (..., dp, ..., dq, ..., ((M \ xq È уq ) \ xp ) È уp ).
Так как M – мультимножество сообщений, xp Í M, и xq Í M,
((M \ xp È ур ) \ хq È уq ) = ((M \ xq È уq ) \ xp È ур ),
и отсюда 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, т.е., если нет события, которому предшествует в последовательности событие, которому оно само каузально предшествует.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
