Векторные часы (Fytmkjudy cgvd)

Векторные часы — алгоритм получения частичного упорядочения событий в распределённой системе и обнаружения нарушений причинно-следственных связей (логические часы).

Таким же образом, как и во временных метках Лэмпорта, внутренние сообщения, передаваемые в системе, содержат состояние логических часов процесса. Векторные часы в системе $N$ процессов — массив или вектор из $N$ логических часов, одни часы на процесс. Локальный экземпляр вектора с наименьшими возможными значениями часов для каждого процесса строится следующим образом:

изначально все значения часов равны 0;
в случае внутреннего события счётчик текущего процесса увеличивается на 1;
перед отправкой сообщения внутренний счётчик, соответствующий текущему процессу, увеличивается на 1, и вектор целиком прикрепляется к сообщению;
при получении сообщения счётчик текущего процесса увеличивается на 1, далее значения в текущем векторе выставляются в максимум от текущего и полученного.

Векторные часы были разработаны независимо Фиджем и Маттерном в 1988 году^[1].

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

Примечания

↑ Colin J. Fidge (1988). "Timestamps in Message-Passing Systems That Preserve the Partial Ordering" (PDF). In K. Raymond (Ed.) (ed.). Proc. of the 11th Australian Computer Science Conference (ACSC'88). pp. 56—66. Архивировано из оригинала (PDF) 15 сентября 2009. Дата обращения: 13 февраля 2009. {{cite conference}}: Неизвестный параметр |month= игнорируется (справка) Источник (неопр.). Дата обращения: 3 июня 2011. Архивировано из оригинала 15 сентября 2009 года.

Литература

Косяков М. С. Введение в распределенные вычисления.. — СПб.: НИУ ИТМО, 2014. — С. 75-82. — 155 с.
Chapter 3: Logical Time Архивная копия от 23 сентября 2015 на Wayback Machine // Ajay Kshemkalyani and Mukesh Singhal, Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press, 2008 (Vector Time)

[1] Colin J. Fidge (1988). "Timestamps in Message-Passing Systems That Preserve the Partial Ordering" (PDF). In K. Raymond (Ed.) (ed.). Proc. of the 11th Australian Computer Science Conference (ACSC'88). pp. 56—66. Архивировано из оригинала (PDF) 15 сентября 2009. Дата обращения: 13 февраля 2009. {{cite conference}}: Неизвестный параметр |month= игнорируется (справка) Источник (неопр.). Дата обращения: 3 июня 2011. Архивировано из оригинала 15 сентября 2009 года.

[1]