Векторные часы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
[[Категория: Параллельное программирование]]
 
[[Категория: Параллельное программирование]]
'''Логическими векторными часами''' называется функция из множества событий распределенных систем (внутреннее событие, событие отправки сообщения и событие приема сообщения) в вектор из целых чисел.
 
  
* каждый поток имеет целочисленный n-мерный вектор (n количество потоков), проинициализированный нулями.
+
{{Определение
 +
|id = vector_clock
 +
|definition =
 +
'''Векторные часы''' — это функция $VC(e) \colon E \to \mathbb R^n$ (из событий в вектор константного размера) такая, что для любых двух событий $e$ и $f$ следующие утверждения равносильны:
 +
* $e \to f$ ($e$ [[Частичный порядок|произошло-до]] $f$)
 +
* $VC(e) < VC(f)$ (все компоненты $VC(e)$ меньше всех компонент $VC(f)$)
 +
}}
 +
 
 +
Алгоритм векторных часов можно построить из [Логические часы Лампорта|логических часов Лампорта], если попросить каждый процесс помнить счётчики всех процессов, а не только свой:
 +
 
 +
* каждый поток имеет целочисленный $n$-мерный вектор ($n$ — количество потоков), проинициализированный нулями.
 
* в случае внутреннего события счётчик текущего процесса увеличивается на 1;
 
* в случае внутреннего события счётчик текущего процесса увеличивается на 1;
 
* перед отправкой сообщения внутренний счётчик, соответствующий текущему процессу, увеличивается на 1, и вектор целиком прикрепляется к сообщению;
 
* перед отправкой сообщения внутренний счётчик, соответствующий текущему процессу, увеличивается на 1, и вектор целиком прикрепляется к сообщению;
* при получении сообщения счётчик текущего процесса увеличивается на 1, далее значения в текущем векторе выставляются в максимум от текущего и полученного.
+
* при получении сообщения счётчик текущего процесса увеличивается на 1, далее значения в текущем векторе выставляются в покомпонентный максимум от текущего и полученного.
  
 
Значением вышеупомянутой функции на событии является значение переменной, принадлежащей тому же потоку, что и событие. Стоит заметить, что векторное время уникально для каждого события.
 
Значением вышеупомянутой функции на событии является значение переменной, принадлежащей тому же потоку, что и событие. Стоит заметить, что векторное время уникально для каждого события.

Версия 17:32, 2 июня 2019


Определение:
Векторные часы — это функция $VC(e) \colon E \to \mathbb R^n$ (из событий в вектор константного размера) такая, что для любых двух событий $e$ и $f$ следующие утверждения равносильны:
  • $e \to f$ ($e$ произошло-до $f$)
  • $VC(e) < VC(f)$ (все компоненты $VC(e)$ меньше всех компонент $VC(f)$)


Алгоритм векторных часов можно построить из [Логические часы Лампорта|логических часов Лампорта], если попросить каждый процесс помнить счётчики всех процессов, а не только свой:

  • каждый поток имеет целочисленный $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]).

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