Введение в распределенные

partial vector clock), представляющими собой множество упорядоченных пар вида (j, x), каждая из которых указывает на то, что текущее состояние P_i находится в псевдо-прямой зависимости от зарегистрированного события e_j^x с порядковым номером x в процессе P_j. Пара (i, v) определяет текущее логическое локальное время v процесса P_i. Зависимости регистрируемого события e_i сохраняются в его отметке
времени, которая определяется показаниями частично-векторных часов на момент наступления e_i и обозначается через PV(e_i). Исходные показания частично-векторных часов для P_i: PV_i = {(i, 0)}.
Пусть PV_i = {(i₁, v₁), … (i, v), … (i_n, v_n)} – текущие показания частично-векторных часов процесса P_i. По методу Жарда-Жордана каждый процесс P_i использует следующие правила для работы со своими логическими часами:

• 
  При регистрации очередного (v + 1)-го события e_i^v+1 процесс P_i вычисляет новое значение своего логического локального времени и записывает его в PV_i:
  

PV_i = {(i₁, v₁), … (i, v + 1), … (i_n, v_n)}.
После этого показания частично-векторных часов процесса P_i сохраняются в отметке времени PV(e_i^v+1) и затем сбрасываются в состояние зависимости только от события e_i^v+1:
PV_i = {(i, v + 1)}.

• 
  При отправке сообщения из P_i в P_j вместе с сообщением передаются текущие показания PV_i.
  
• 
  Когда процесс P_i принимает сообщение с отметкой времени PV_msg = {(i_m1, v_m1), (i_m2, v_m2), … (i_mk, v_mk)}, он устанавливает показания своих частично-векторных часов PV_i в виде множества следующих пар:
  

1. 
   все пары (i_mx, v_mx), такие что (i_mx, .) не содержатся в PV_i;
   
2. 
   все пары (i_x, v_x), такие что (i_x, .) не содержатся в PV_msg;
   
3. 
   пары (i_x, max(v_x, v_mx)) для всех (i_x, .), которые содержатся и в
   

PV_i и в PV_msg.
Пример работы адаптивного метода Жарда-Жордана приведен на рис. 3.9; регистрируемые события отмечены жирным кружочком. Рассмотрим работу процесса P₂. Исходные показания логических часов PV₂ этого процесса равны (2, 0). При регистрации события e₂¹ процесс P₂ вычисляет новое значение своего локального времени и копирует его в отметку времени PV(e₂¹). При получении сообщения от процесса P₁ в показания логических часов PV₂ добавляется пара (1, 0). Аналогичная ситуация возникает при получении сообщения от процесса P₃ с отметкой времени {(3, 1), (4, 0)}. В итоге PV₂ = {(1 ,0), (2, 1), (3, 1), (4, 0)}. Когда же
регистрируется событие e ², процесс P увеличивает свое локальное время,
2 2
и полученные показания логических часов сохраняются в отметке времени PV(e₂²) данного события. После этого показания PV₂ сбрасываются в значение (2, 2). Таким образом легко видеть, что событие e₂² напрямую
зависит от событий e ⁰, e ¹ и e ¹. Кроме того, данное событие находится в
1 2 3

4
отношении псевдо-прямой зависимости от события e ⁰.

Рис. 3.9. Пример работы адаптивного метода Жарда-Жордана.

Транзитивные зависимости заданного события e_i могут быть восстановлены путем анализа отметок времени событий, c которыми e_i связано отношением псевдо-прямой зависимости. Если такой анализ провести рекурсивно, то могут быть найдены все события, произошедшие раньше e_i.

Основное преимущество метода Жарда-Жордана заключается в том, что этот метод позволяет настраивать оптимальный размер отметки времени, передаваемой с каждым сообщением. А именно, количество пар, содержащихся в логических частично-векторных часах, может быть ограничено сверху путем регистрации дополнительных событий. Например, если требуется, чтобы размер логического времени не превышал k пар, достаточно, чтобы процесс зарегистрировал дополнительное событие, когда число накопленных им зависимостей достигнет k. Такое свойство адаптивной регистрации событий позволяет гибко контролировать накладные расходы на передачу сообщений при распределенном вычислении.

5.