Векторные часы

Логическими векторными часами называется функция из множества событий (прием/посылка сообщений) в вектор из целых чисел.

• каждый поток имеет целочисленный n-мерный вектор (n – количество потоков), проинициализированный нулями.
• в случае внутреннего события счётчик текущего процесса увеличивается на 1;
• перед отправкой сообщения внутренний счётчик, соответствующий текущему процессу, увеличивается на 1, и вектор целиком прикрепляется к сообщению;
• при получении сообщения счётчик текущего процесса увеличивается на 1, далее значения в текущем векторе выставляются в максимум от текущего и полученного.

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

Оказывается, что если в распределенной системе ввести частичный порядок предшествования на событиях, то имеет место следующее утверждение:
a предшествует b, тогда и только тогда, когда логическое время векторных часов события a меньше логического времени события b (при этом вектор x меньше вектора y, если для каждой компоненты выполяется [math]x_i \le y_i[/math] и [math]\exists j: x_j \lt y_j[/math]).

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