Предыдущая страница реферата | 13  14  15  16  17  18  19  20  21  22  23 | Следующая страница реферата

то есть ср = bp, cq = bq, xp ( M, и xq ( M. Важное наблюдение состоит в том, что хр и xq разделены, сообщение в xp (если есть такое) имеет назначением р, в то время как сообщение в хq (если есть такое) имеет назначением q.

Запишем (р = ер((), и запомним что

(р = (..., dp, ..., cq, ..., (M xp ) ( ур ).

Так как xq ( M и xq ( хр = (, следует, что хq ( (M xp ( ур ), и отсюда еq применимо в (р. Запишем (pq = eq((р), и запомним, что

(рq = (..., dp, ..., dq, ..., ((M xp ( ур ) xq ) ( уq ).

С помощью симметричного аргумента может быть показано, что ер применимо в (q = eq((). Запишем (qp = ep((q), и запомним, что

(qp = (..., dp, ..., dq, ..., ((M xq ( уq ) xp ) ( уp ).

Так как M – мультимножество сообщений, xp ( M, и xq ( M,

((M xp ( ур ) хq ( уq ) = ((M xq ( уq ) xp ( ур ),

и отсюда (pq = (qp .
(

Пусть ер и еq будут двумя событиями, которые появляются последовательно в исполнении, т.е. исполнение содержит подпоследовательность

..., (, ер((), еq(ер(()), ...

для некоторых (. Посылка теоремы 2.19 применима к этим событиям за исключением следующих двух случаев.

1) p = q; или

2) ер – событие отправки, и еq - соответствующее событие получения.

В самом деле, теорема явно утверждает, что p и q должны быть различными, и если еq получает сообщение, посланное в ер, событие отправки не применимо в начальной конфигурации события ep, как требуется. Таким образом, если одно из этих двух утверждений истина, события не могут появляться в обратном порядке, иначе они могут встречаться в обратном порядке и кроме того иметь результат в одной конфигурации. Запомните, что с глобальной точки зрения переходы не могут быть обменены, потому что (в нотации теоремы 2.19) переход из (р в (pq отличается от перехода из ( в (q.
Однако, с точки зрения процесса эти события неразличимы.

Тот факт, что конкретная пара событий не может быть обменена, выражается тем, что существует каузальное отношение между этими двумя событиями. Это отношение может быть расширено до частичного порядка на множестве событий в исполнении, называемого каузальный порядок исполнения.

Определение 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 Эквивалентность исполнений: вычисления

В этом подразделе показывается, что события исполнения могут быть переупорядочены в любом порядке, согласующимся с каузальным порядком, без воздействия на результат исполнения. Это переупорядочивание событий вызывает другую последовательность конфигураций, но это исполнение будет рассматриваться как эквивалент исходного исполнения.

Рекомендуем скачать другие рефераты по теме: педагогические рефераты, реферат машини.





Предыдущая страница реферата | 13  14  15  16  17  18  19  20  21  22  23 | Следующая страница реферата