Изменения

Перейти к: навигация, поиск

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

560 байт добавлено, 17:32, 2 июня 2019
Нет описания правки
[[Категория: Параллельное программирование]]
'''Логическими векторными часами''' называется функция из множества событий распределенных систем (внутреннее событие, событие отправки сообщения и событие приема сообщения) в вектор из целых чисел.
{{Определение|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, далее значения в текущем векторе выставляются в покомпонентный максимум от текущего и полученного.
Значением вышеупомянутой функции на событии является значение переменной, принадлежащей тому же потоку, что и событие. Стоит заметить, что векторное время уникально для каждого события.
292
правки

Навигация