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

Правило 2: в каждое передаваемое сообщение добавляется значение матричного времени M_i процесса-отправителя P_i на момент отправки этого сообщения. Когда процесс P_j получает сообщение от процесса P_i с отметкой времени M_msg, он выполняет следующие шаги:

1. 
   обновляет показания своих векторных часов в строке M_j[j, .] согласно векторному времени процесса P_i, полученному в строке M_msg[i, .]:
   

1 ≤ k ≤ N: M_j[j, k] = max(M_j[j, k], M_msg[i, k]); остальные элементы матрицы M_j обновляются по правилу:
1 ≤ k, l ≤ N: M_j[k, l] = max(M_j[k, l], M_msg[k, l]).

2. 
   исполняет Правило 1;
   
3. 
   доставляет сообщение и приступает к его обработке. Элементы матрицы M_i[k, l] инициализируется нулем, 1 ≤ k, l ≤ N.
   

2

2

2
Пример работы алгоритма матричных часов для d = 1 приведен на рис. 3.10. Рассмотрим матричную отметку времени для события e ⁶ процесса P₂. Событие e₁⁵ является последним событием в процессе P₁, которое предшествует e₂⁶ согласно отношению причинно-следственного порядка. Поэтому M(e₂⁶)[2,1] = M(e ⁶)[1,1] = 5. Аналогично, M(e ⁶)[2,3] =

1

2
M(e₂⁶)[3,3] = 4. По сведениям процесса P₂ последним событием процесса P₁, о котором "знает" процесс P₃, является событие e ². Поэтому M(e ⁶)[3,1] = 2.
Аналогично, e ⁴ – последнее событие в P , о котором "знает" P по
3 3 1
сведениям P₂, т.е. M(e₂⁶)[1,3] = 4.

Рис. 3.10. Пример работы алгоритма матричных часов.

3.5.1 Основные свойства

По определению строка M_i[i, .] обладает всеми свойствами векторных часов. Кроме этого, если для матричного времени процесса P_i верно неравенство min_k (M_i[k, l]) ≥ t, то по сведениям процесса P_i каждый из процессов P_k "знает" о том, что локальное время процесса P_l достигло значения t или превышает его. Например, исходя из матричной отметки
времени события e ⁶ на рис. 3.10 процессу P известно, что все процессы в
2 2
системе обладают информацией о том, что ход выполнения процесса P₁
достиг события e ². Из данного неравенства процесс P может сделать
1 i
вывод, что всем другим процессам в системе известно о том, что процесс P_l уже не будет передавать информацию с отметкой своего логического локального времени меньшей, либо равной t. Во многих приложениях это означает, что процессам больше не нужно хранить какие-либо данные, полученные ранее от процесса P_l, и они могут без проблем удалять устаревшую информацию (англ. obsolete information).
Если значение прироста локальных логических часов всегда равно единице (d = 1), то элемент матрицы M_i[k, l] будет содержать в себе число событий, выполненных в процессе P_l и известных процессу P_k настолько, насколько об этом "знает" процесс P_i.