2.1.5 Базовые ситуации

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

В ЭСС N два события e1 и e2 в состоянии c могут находиться по крайней мере в трех отношениях друг с другом:

  • причинной зависимости: e1 может произойти в c, а e2 не может, однако после того, как e1 произойдет, e2 тоже может произойти;
  • конфликта: каждое из событий e1 и e2 может произойти в c, однако вместе они не могут произойти, т.е. {e1}, {e2} — шаги в c, тогда как {e1,e2} не является таковым;
  • параллелизма: оба события e1 и e2 могут произойти в c, т.е. {e1,e2} — шаг в c.

Одним из достоинств теории сетей является то, что эти три базовых отношения между событиями распределенных систем могут быть не только представлены в явном виде, но и изображены графически. Например, графическое представление причинной зависимости событий в ЭСС показана на рис. 2.11, где в заданном состоянии событию e2 должно предшествовать событие e1, т.е. e2 причинно зависит от e1.

Определим отношение причинной зависимости формально следующим образом.

Определение 22  Пусть  N=(B,E,F,cin)ЭСС, e1,e2E  и  cCN. Тогда  e1и  e2   находятся в отношении  причинной зависимости в c,  если  c[e1>, ¬(c[e2>)  и  c'[e2>где  c[e1>c'.

Теперь рассмотрим рис. 2.12 с графическим представлением отношения конфликта. В заданном состоянии каждое из событий e1 и e2 может произойти, однако так как условие b является входным как для e1, так и для e2, то множество {e1,e2} не является шагом.

Определим отношение конфликта формально следующим образом.

Определение 23  Пусть  N=(B,E,F,cin)ЭСС, e1,e2E  и  cCN.  Тогда  e1  и  e2  находятся в отношении  конфликта в c, если  c[e1>, c[e2>  и  ¬(c[{e1,e2}>).

Далее рассмотрим на рис. 2.13 графическое представление отношения параллелизма. В заданном состоянии оба события e1 и e2 могут произойти. Более того, нет никакой зависимости в порядке, в котором они происходят. Как следствие реализация этих событий и вновь полученные состояния могут быть частично упорядочены.

Определим отношение параллелизма формально следующим образом.

Определение 24  Пусть  N=(B,E,F,cin)ЭСС, e1,e2E  и  cCN.  Тогда  e1  и  e2  находятся в отношении  параллелизма в c,  если  c[{e1,e2}>.

В заключение рассмотрим еще одно отношение между событиями системы — так называемое отношение конфузии, которое представляет собой комбинацию отношений параллелизма и конфликта. Графическое представление отношения конфузии показано на рис. 2.14. Рассмотрим состояния c={b1,b2,b3} и c'={b4,b5} такие, что c[{e1,e2}>c'. Если события e1 и e2 происходят параллельно, то у события e3 нет возможности быть реализованным, тогда как при последовательной реализации событий e1 и e2, если событие e2 произойдет первым, то события e1 и e3 входят в конфликт, который может быть разрешен успешно в пользу либо события e1, либо события e3. Таким образом, события e1 и e2 находятся в отношении конфузии. Такого рода ситуации возникают из-за "перекрытия" отношений параллелизма и конфликта и достаточно часто встречаются в реальных системах. Трудность анализа ситуаций с конфузией состоит в том, что невозможно использовать достоинства параллельного подхода и приходится анализировать все промежуточные состояния, а не только достижимые после одной возможной последовательности реализаций параллельных событий, поскольку промежуточные состояния, достижимые после различных последовательностей реализаций, в значительной степени отличаются друг от друга.

Введем формальное определение отношения конфузии между событиями распределенной системы. Для этого нам понадобится вспомогательное понятие. Пусть N=(B,E,F,cin) — ЭСС, eE и cCN такие, что c[e>. Тогда  конфликтное множество  события e в состоянии c определяется как cfl(e,c)={e'E|c[e'>¬(c[{e,e'}>)}. Таким образом, конфликтное множество события e в состоянии c — это множество всех событий, конфликтных с e в c.

Определение 25   Пусть  N=(B,E,F,cin)ЭСС, e1,e2E  и  cCN   такие, что  c[{e1,e2}>Тогда тройка  (c,e1,e2)  называется  конфузией  в состоянии c, если  cfl(e1,c)cfl(e1,c'), где  c[e2>c'.  N  находится в конфузии  в состоянии c, если существует конфузия в c.

Таким образом, тройка (c,e1,e2) — конфузия в состоянии c, если {e1,e2} — шаг в c и реализация события e2 в c изменяет конфликтное множество события e1. В качестве примера рассмотрим ЭСС, изображенную на рис. 2.14, и ее состояние c={b1,b2,b3} такое, что c[{e1,e2}>. Имеем cfl(e1,c)=. Тогда верон, что (c,e1,e2) — конфузия в c, поскольку cfl(e1,c')={e3}, т.е. cfl(e1,c)cfl(e1,c'), где c'={b1,b3,b4}.

Далее будем различать два типа конфузии.

Определение 26  Пусть  N=(B,E,F,cin)ЭСС, e1,e2E  и  cCN. Пусть  γ=(c,e1,e2)  конфузия в c и  c[e1>c'.  Тогда:

  • γ — увеличивающаяся конфузия,  если  cfl(e1,c)cfl(e1,c');
  • γ — уменьшающаяся конфузия,  если  cfl(e1,c')cfl(e1,c).

Вновь рассмотрим ЭСС на рис. 2.14. Так как cfl(e1,c)cfl(e1,c'), то (c,e1,e2) — увеличивающаяся конфузия. Далее рассмотрим состояния c={b1,b2} и c'={b1,b3} ЭСС, показанной на рис. 2.15. Имеем, что (c,e1,e2) — конфузия в c, так как cfl(e1,c)={e3}=cfl(e1,c'). Кроме того, поскольку cfl(e1,c')cfl(e1,c), то (c,e1,e2) — уменьшающаяся конфузия. Теперь рассмотрим еще один пример — ЭСС, изображенную на рис. 2.16. Имеем, что (c,e1,e2) — конфузия в c={b1,b2,b4}, так как cfl(e1,c)={e3}{e4}=cfl(e1,c'), где c'={b2,b3,b4}. Однако (c,e1,e2) не является конфузией ни первого типа, ни второго. Такого типа конфузии в литературе часто называются ассиметричными, тогда как конфузии, упомянутые выше, — симметричными.

Определение 27   Пусть  N=(B,E,F,cin)ЭСС.

  • N — последовательная,  если  uUN    |u|=1;
  • N — детерминированная,  если  cCNe1,e2E    (c[e1>c[e2>c[{e1,e2}>);
  • N — свободная от конфузий,  если не находится в конфузии ни при одном своем состоянии.

ЭСС, приведенная на рис. 2.17, а, является последовательной и детерминированной, тогда как ЭСС на рис. 2.17, б — последовательная, но не обладающая свойством детерминированности. Пример детерминированной и непоследовательной ЭСС показан на рис. 2.17, в. Непоследовательная и недетерминированная ЭСС, но обладающая свойством свободы от конфузий, изображена на рис. 2.17, г. На рис. 2.17, д приведена непоследовательная и недетерминированная ЭСС, также имеющая два типа конфузий. Из данных примеров и определений, рассмотренных выше, легко установить факты, показанные на рис. 2.18.