Векторные часы и причинность

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

Definition

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

Scope

Эта тема охватывает механизм векторных часов — один счетчик на процесс, обновляемый при локальных событиях и объединяемый при получении сообщения — частичный порядок, который он индуцирует, и его использование для обнаружения причинности и параллелизма. Она также охватывает векторы версий, тесно связанную структуру, используемую для обнаружения конфликтующих обновлений среди реплик, и присущие затраты на пространство для точного отслеживания причинности.

Core questions

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

Key theories

Характеристика причинности с помощью векторных часов

Поддерживая вектор счетчиков для каждого процесса, который покомпонентно максимизируется при получении сообщения, векторные часы делают покомпонентный порядок меток времени точно равным отношению «произошло до», так что параллелизм может быть обнаружен.

Векторы версий для обнаружения конфликтов реплик

Векторы версий применяют ту же идею к реплицированным объектам, позволяя репликам определять, доминирует ли одна версия над другой или две версии конфликтуют и должны быть согласованы.

Связь с логическими часами

Векторные часы строго уточняют скалярные логические часы Лэмпорта: скалярные метки времени только гарантируют, что порядок согласуется с причинностью, тогда как векторные метки времени точно определяют причинность ценой O(n) пространства на метку времени.

Clinical relevance

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

History

Основываясь на логическом времени Лэмпорта, Фидж и Маттерн независимо представили векторные часы в 1988-1989 годах; тесно связанные векторы версий уже появились в 1983 году для обнаружения несогласованности среди реплик, и эти структуры остаются центральными для современных систем реплицированных данных.

Debates

Затраты на пространство для точного отслеживания причинности

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

Key figures

• Colin Fidge
• Friedemann Mattern
• Leslie Lamport

Seminal works

• fidge1988
• mattern1989
• parker1983

Frequently asked questions

Как векторные часы улучшают часы Лэмпорта?

Часы Лэмпорта только гарантируют, что порядок меток времени согласуется с причинностью, поэтому они не могут определить, являются ли два события параллельными. Векторные часы делают сравнение точным: вы можете напрямую определить, произошло ли одно событие до другого или они являются параллельными.