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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

Примечания[править | править вики-текст]

  1. Colin J. Fidge (February 1988). "Timestamps in Message-Passing Systems That Preserve the Partial Ordering". K. Raymond (Ed.) Proc. of the 11th Australian Computer Science Conference (ACSC'88): 56–66. Проверено 2009-02-13. 

Литература[править | править вики-текст]

  • Косяков М. С. Введение в распределенные вычисления. –. — СПб: НИУ ИТМО, 2014. — С. 75-82. — 155 с.