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

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

Обозначим как векторные часы, поддерживаемые процессом i, обновление часов происходит следующим образом: ^[1]${\ displaystyle VC_ {i}}$

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

• Изначально все часы равны нулю.
• Каждый раз, когда в процессе происходит внутреннее событие, он увеличивает свои собственные логические часы в векторе на единицу. Например, при событии в процессе i он обновляется .${\ Displaystyle VC_ {я} [я] \ leftarrow VC_ {я} [я] +1}$
• Каждый раз, когда процесс отправляет сообщение, он увеличивает свои собственные логические часы в векторе на единицу (как в маркере выше, но не дважды для одного и того же события), а затем сообщение копирует копию своего собственного вектора.
• Каждый раз, когда процесс получает сообщение, он увеличивает свои собственные логические часы в векторе на единицу и обновляет каждый элемент в своем векторе, беря максимальное значение из своих собственных векторных часов и значение в векторе в полученном сообщении (для каждый элемент). Например, если процесс Pj получает сообщение m от Pi, он обновляется путем установки .${\displaystyle VC_{i}\leftarrow VC_{i}[k]+1,\forall k}$

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

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

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

t = <t1, …, tn>

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

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

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

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

• ${\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 году Торрес-Рохас и Ахамад разработал правдоподобным Часы , ^[6] механизм , который занимает меньше места , чем вектор часов , но это, в некоторых случаях, сможет полностью порядка событий, которые каузально одновременно.

• В 2005 году Agargwal и Garg создано Chain Часы , ^[7] система , которая отслеживает зависимости с использованием векторов с размером меньшим , чем число процессов , и что автоматически приспосабливается к системам с динамическим числом процессов.

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

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

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

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

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

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

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