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

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

Пример системы векторных часов. События в синей области - это причины, приводящие к событию B4, тогда как события в красной области - это последствия события B5.

• Изначально все часы равны нулю.
• Каждый раз, когда в процессе происходит внутреннее событие, он увеличивает свои логические часы в векторе на единицу.
• Каждый раз, когда процесс отправляет сообщение, он увеличивает свои собственные логические часы в векторе на единицу (как в маркере выше, но не дважды для одного и того же события), а затем отправляет копию своего собственного вектора.
• Каждый раз, когда процесс получает сообщение, он увеличивает свои собственные логические часы в векторе на единицу и обновляет каждый элемент в своем векторе, беря максимальное значение из собственных векторных часов и значение в векторе в полученном сообщении (для каждый элемент).

История [ править ]

Без использования специального названия «векторные часы» концепция векторных часов была впервые упомянута ^[1] в статье 1986 года Ривки Ладин и Барбары Лисков, где они использовали термин «составная временная метка». ^[2] Цитата из страницы 31 статьи Лискова / Ладина:

Мы решаем эту проблему, используя составные временные метки , где для каждой реплики есть одна часть. Таким образом, если имеется n реплик, метка времени t равна

t = <t1, …, tn>

где каждая часть - положительное целое число. Поскольку обычно будет небольшое количество реплик (например, от 3 до 7), использование такой отметки времени является практичным.

Термин «векторные часы» был впервые использован независимо Колином Фиджем и Фридеманом Маттерном в 1988 году. ^{[3] [4]}

Свойство частичного упорядочивания [ править ]

Векторные часы допускают частичную причинную последовательность событий. Определение следующего:

• ${\ displaystyle VC (x)}$обозначает векторные часы события и обозначает компонент этих часов для процесса .${\ displaystyle x}$${\ displaystyle VC (x) _ {z}}$${\ displaystyle z}$
• ${\displaystyle VC(x)<VC(y)\iff \forall z[VC(x)_{z}\leq VC(y)_{z}]\land \exists z'[VC(x)_{z'}<VC(y)_{z'}]}$
  • На английском языке: меньше , если и только если меньше или равно для всех индексов процесса , и по крайней мере одно из этих отношений строго меньше (то есть ).${\displaystyle VC(x)}$${\displaystyle VC(y)}$${\displaystyle VC(x)_{z}}$${\displaystyle VC(y)_{z}}$${\displaystyle z}$${\displaystyle VC(x)_{z'}<VC(y)_{z'}}$
• ${\displaystyle x\to y\;}$означает, что событие произошло до события . Он определяется как: если , то${\displaystyle x}$${\displaystyle y}$${\displaystyle x\to y\;}$${\displaystyle VC(x)<VC(y)}$

Характеристики:

• Антисимметрия : если , то ¬${\displaystyle VC(a)<VC(b)}$${\displaystyle (VC(b)<VC(a))}$
• Транзитивность : если и , то или если и , то${\displaystyle VC(a)<VC(b)}$${\displaystyle VC(b)<VC(c)}$${\displaystyle VC(a)<VC(c)}$${\displaystyle a\to b\;}$${\displaystyle b\to c\;}$${\displaystyle a\to c\;}$

Связь с другими заказами:

• Пусть будет реальное время, когда происходит событие . Если , то${\displaystyle RT(x)}$${\displaystyle x}$${\displaystyle VC(a)<VC(b)}$${\displaystyle RT(a)<RT(b)}$
• Позвольте быть меткой времени Lamport события . Если , то${\displaystyle C(x)}$${\displaystyle x}$${\displaystyle VC(a)<VC(b)}$${\displaystyle C(a)<C(b)}$

Другие механизмы [ править ]

• В 1999 году Торрес-Рохас и Ахамад разработал правдоподобным Часы , ^[5] механизм , который занимает меньше места , чем вектор часов , но это, в некоторых случаях, сможет полностью порядка событий, которые каузально одновременно.

• В 2008 году Алмейда и др. представили Interval Tree Clocks . ^{[6] [7] [8]} Этот механизм обобщает векторные часы и позволяет работать в динамических средах, когда идентификаторы и количество процессов в вычислениях заранее неизвестны.

• В 2019 году, Lum Ramabaja разработана Bloom Часы , ^[9] вероятностные структуры данных, пространство сложность не зависит от числа узлов в системе. Если два часа не сравнимы, часы цветения всегда могут определить это, т.е. ложноотрицательные результаты невозможны. Если два часа сопоставимы, часы Блума могут вычислить достоверность этого утверждения, т.е. они могут вычислить частоту ложных срабатываний между сопоставимыми парами часов.

Ссылки [ править ]

См. Также [ править ]

• Отметки времени Лэмпорта
• Матричные часы
• Вектор версии

Внешние ссылки [ править ]

• Почему логические часы просты (сравниваются истории причин, векторные часы и векторы версий)
• Объяснение векторных часов
• Реализация векторных часов на основе меток времени в Erlang
• Реализация векторных часов в Objective-C
• Реализация векторных часов в Erlang
• Почему векторные часы сложны
• Почему Кассандре не нужны векторные часы