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

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

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

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

История

Лампорт придумал идею логических часов Лампорта в 1978 году. ^[2] Однако логические часы в этой статье были скалярами, а не векторами. Обобщение векторного времени разрабатывалось несколько раз, по-видимому независимо, разными авторами в начале 1980-х годов. ^[3] Эта концепция содержится как минимум в 6 статьях. ^[4] Канонически цитируемые статьи о векторных часах — это работы Колина Фиджа и Фридемана Маттерна 1988 года: ^[5]^[6] поскольку они (независимо) установили название «векторные часы» и математические свойства векторных часов. ^[3]

Частичный заказ недвижимости

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

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

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

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

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

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

Другие механизмы

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

В 2005 году Агарвал и Гарг создали Chain Clocks . ^[8] система, которая отслеживает зависимости с использованием векторов, размер которых меньше количества процессов, и автоматически адаптируется к системам с динамическим количеством процессов.
В 2008 году Алмейда и др. представили часы интервального дерева . ^[9]^[10]^[11] Этот механизм обобщает векторные часы и позволяет работать в динамических средах, когда идентификаторы и количество процессов в вычислениях заранее неизвестны.

В 2019 году Лам Рамабаджа предложил Bloom Clocks — вероятностную структуру данных, основанную на фильтрах Блума . ^[12]^[13]^[14] По сравнению с векторными часами пространство, используемое на каждый узел, фиксировано и не зависит от количества узлов в системе. Сравнение двух часов либо приводит к истинному отрицательному результату (часы несопоставимы), либо к предположению, что одни часы предшествуют другим, с возможностью ложного положительного результата, когда эти два часа не связаны между собой. Уровень ложных срабатываний уменьшается по мере увеличения разрешенного объема памяти.

См. также

Ссылки

^ «Распределенные системы, 3-е издание (2017 г.)» . РАСПРЕДЕЛЕННЫЕ-СИСТЕМЫ.NET . Проверено 21 марта 2021 г.
^ Лэмпорт, Л. (1978). «Время, часы и порядок событий в распределенной системе» (PDF) . Коммуникации АКМ . 21 (7): 558–565. дои : 10.1145/359545.359563 . S2CID 215822405 .
^ Jump up to: ^а ^б Шварц, Рейнхард; Маттерн, Фридеманн (март 1994 г.). «Обнаружение причинно-следственных связей в распределенных вычислениях: В поисках Святого Грааля» . Распределенные вычисления . 7 (3): 149–174. дои : 10.1007/BF02277859 . S2CID 3065996 .
^
Купер, Линдси (8 апреля 2023 г.). «Кто изобрел векторные часы?» . разложение ∘ др . Документы (в хронологическом порядке):
- Фишер, Майкл Дж.; Майкл, Алан (1982). «Жертвовать сериализуемостью ради достижения высокой доступности данных в ненадежной сети». Материалы 1-го симпозиума ACM SIGACT-SIGMOD по принципам систем баз данных - PODS '82 . п. 70. дои : 10.1145/588111.588124 . ISBN 0897910702 . S2CID 8774876 .
- Паркер, Д.С.; Попек, Дж.Дж.; Рудисин Г.; Стоутон, А.; Уокер, Би Джей; Уолтон, Э.; Чоу, Дж. М.; Эдвардс, Д.; Кисер, С.; Клайн, К. (май 1983 г.). «Обнаружение взаимной несогласованности в распределенных системах». Транзакции IEEE по разработке программного обеспечения . СЭ-9 (3): 240–247. дои : 10.1109/TSE.1983.236733 . S2CID 2483222 .
- Вуу, Джин ТиДжей; Бернштейн, Артур Дж. (1984). «Эффективные решения проблем с реплицируемым журналом и словарем». Материалы третьего ежегодного симпозиума ACM по принципам распределенных вычислений — PODC '84 . стр. 233–242. дои : 10.1145/800222.806750 . ISBN 0897911431 . S2CID 2384672 .
- Стром, Роб; Йемини, Шаула (август 1985 г.). «Оптимистическое восстановление в распределенных системах» . Транзакции ACM в компьютерных системах . 3 (3): 204–226. дои : 10.1145/3959.3962 . S2CID 1941122 .
- Шмук, Фрэнк Б. (ноябрь 1985 г.). Программные часы и порядок событий в распределенной системе (неопубликовано).
- Лисков, Варвара; Ладин, Ривка (1986). «Высокодоступные распределенные сервисы и отказоустойчивая распределенная сборка мусора». Материалы пятого ежегодного симпозиума ACM по принципам распределенных вычислений - PODC '86 . стр. 29–39. дои : 10.1145/10590.10593 . ISBN 0897911989 . S2CID 16148617 .
- Рейналь, Мишель (февраль 1987 г.). «Распределенный алгоритм для предотвращения взаимного дрейфа между n логическими часами». Письма об обработке информации . 24 (3): 199–202. дои : 10.1016/0020-0190(87)90186-4 .
^ Фидж, Колин Дж. (февраль 1988 г.). «Временные метки в системах передачи сообщений, сохраняющие частичный порядок» (PDF) . В К. Раймонде (ред.). Материалы 11-й Австралийской конференции по информатике (ACSC'88) . Том. 10. С. 56–66 . Проверено 13 февраля 2009 г.
^ Маттерн, Фридеманн (октябрь 1988 г.). «Виртуальное время и глобальные состояния распределенных систем». В Коснаре, М. (ред.). Учеб. Практикум по параллельным и распределенным алгоритмам . Шато де Бонас, Франция: Эльзевир. стр. 215–226.
^ Франсиско Торрес-Рохас; Мустак Ахамад (1999), «Правдоподобные часы: логические часы постоянного размера для распределенных систем» , Distributed Computing , 12 (4): 179–195, doi : 10.1007/s004460050065 , S2CID 2936350
^ Агарвал, Анураг; Гарг, Виджай К. (17 июля 2005 г.). «Эффективное отслеживание зависимостей для соответствующих событий в системах с общей памятью» (PDF) . Материалы двадцать четвертого ежегодного симпозиума ACM по принципам распределенных вычислений . Ассоциация вычислительной техники. стр. 19–28. дои : 10.1145/1073814.1073818 . ISBN 1-58113-994-2 . S2CID 11779779 . Проверено 21 апреля 2021 г.
^ Алмейда, Пауло; Бакеро, Карлос; Фонте, Виктор (2008), «Часы интервального дерева: логические часы для динамических систем», Бейкер, Теодор П.; Буи, Ален; Тиксёй, Себастьян (ред.), Принципы распределенных систем (PDF) , Конспекты лекций по информатике, том. 5401, Springer-Verlag, Конспекты лекций по информатике, стр. 259–274, Bibcode : 2008LNCS.5401.....B , doi : 10.1007/978-3-540-92221-6 , ISBN 978-3-540-92220-9
^ Алмейда, Пауло; Бакеро, Карлос; Фонте, Виктор (2008), «Часы дерева интервалов: логические часы для динамических систем», Часы интервального дерева: логические часы для динамических систем , Конспект лекций по информатике, том. 5401, с. 259, номер doi : 10.1007/978-3-540-92221-6_18 , hdl : 1822/37748 , ISBN 978-3-540-92220-9
^ Чжан, И (2014), «Предварительные сведения: результаты синхронизации дерева интервалов», Предварительные сведения: результаты синхронизации дерева интервалов (PDF)
^ Поццетти, Томмазо; Кшемкальяни, Аджай Д. (1 апреля 2021 г.). «Сбрасываемые векторные часы для анализа причинно-следственных связей с применением к динамическому обнаружению гонок» . Транзакции IEEE в параллельных и распределенных системах . 32 (4): 772–785. дои : 10.1109/TPDS.2020.3032293 . S2CID 220362525 .
^ Лум Рамабаджа (2019), The Bloom Clock , arXiv : 1905.13064 , Бибкод : 2019arXiv190513064R
^ Кулкарни, Сандип С; Эпплтон, Гейб; Нгуен, Дуонг (4 января 2022 г.). «Достижение причинности с помощью физических часов». Материалы 23-й Международной конференции по распределенным вычислениям и сетям . стр. 97–106. arXiv : 2104.15099 . дои : 10.1145/3491003.3491009 . ISBN 9781450395601 . S2CID 233476293 .

Внешние ссылки

[1] «Распределенные системы, 3-е издание (2017 г.)» . РАСПРЕДЕЛЕННЫЕ-СИСТЕМЫ.NET . Проверено 21 марта 2021 г.

[Lamport_1978-2] Лэмпорт, Л. (1978). «Время, часы и порядок событий в распределенной системе» (PDF) . Коммуникации АКМ . 21 (7): 558–565. дои : 10.1145/359545.359563 . S2CID 215822405 .

[Schwarz-3] Jump up to: ^а ^б Шварц, Рейнхард; Маттерн, Фридеманн (март 1994 г.). «Обнаружение причинно-следственных связей в распределенных вычислениях: В поисках Святого Грааля» . Распределенные вычисления . 7 (3): 149–174. дои : 10.1007/BF02277859 . S2CID 3065996 .

[4] Купер, Линдси (8 апреля 2023 г.). «Кто изобрел векторные часы?» . разложение ∘ др . Документы (в хронологическом порядке):
Фишер, Майкл Дж.; Майкл, Алан (1982). «Жертвовать сериализуемостью ради достижения высокой доступности данных в ненадежной сети». Материалы 1-го симпозиума ACM SIGACT-SIGMOD по принципам систем баз данных - PODS '82 . п. 70. дои : 10.1145/588111.588124 . ISBN 0897910702 . S2CID 8774876 .
Паркер, Д.С.; Попек, Дж.Дж.; Рудисин Г.; Стоутон, А.; Уокер, Би Джей; Уолтон, Э.; Чоу, Дж. М.; Эдвардс, Д.; Кисер, С.; Клайн, К. (май 1983 г.). «Обнаружение взаимной несогласованности в распределенных системах». Транзакции IEEE по разработке программного обеспечения . СЭ-9 (3): 240–247. дои : 10.1109/TSE.1983.236733 . S2CID 2483222 .
Вуу, Джин ТиДжей; Бернштейн, Артур Дж. (1984). «Эффективные решения проблем с реплицируемым журналом и словарем». Материалы третьего ежегодного симпозиума ACM по принципам распределенных вычислений — PODC '84 . стр. 233–242. дои : 10.1145/800222.806750 . ISBN 0897911431 . S2CID 2384672 .
Стром, Роб; Йемини, Шаула (август 1985 г.). «Оптимистическое восстановление в распределенных системах» . Транзакции ACM в компьютерных системах . 3 (3): 204–226. дои : 10.1145/3959.3962 . S2CID 1941122 .
Шмук, Фрэнк Б. (ноябрь 1985 г.). Программные часы и порядок событий в распределенной системе (неопубликовано).
Лисков, Варвара; Ладин, Ривка (1986). «Высокодоступные распределенные сервисы и отказоустойчивая распределенная сборка мусора». Материалы пятого ежегодного симпозиума ACM по принципам распределенных вычислений - PODC '86 . стр. 29–39. дои : 10.1145/10590.10593 . ISBN 0897911989 . S2CID 16148617 .
Рейналь, Мишель (февраль 1987 г.). «Распределенный алгоритм для предотвращения взаимного дрейфа между n логическими часами». Письма об обработке информации . 24 (3): 199–202. дои : 10.1016/0020-0190(87)90186-4 .

[5] Фишер, Майкл Дж.; Майкл, Алан (1982). «Жертвовать сериализуемостью ради достижения высокой доступности данных в ненадежной сети». Материалы 1-го симпозиума ACM SIGACT-SIGMOD по принципам систем баз данных - PODS '82 . п. 70. дои : 10.1145/588111.588124 . ISBN 0897910702 . S2CID 8774876 .

[6] Паркер, Д.С.; Попек, Дж.Дж.; Рудисин Г.; Стоутон, А.; Уокер, Би Джей; Уолтон, Э.; Чоу, Дж. М.; Эдвардс, Д.; Кисер, С.; Клайн, К. (май 1983 г.). «Обнаружение взаимной несогласованности в распределенных системах». Транзакции IEEE по разработке программного обеспечения . СЭ-9 (3): 240–247. дои : 10.1109/TSE.1983.236733 . S2CID 2483222 .

[7] Вуу, Джин ТиДжей; Бернштейн, Артур Дж. (1984). «Эффективные решения проблем с реплицируемым журналом и словарем». Материалы третьего ежегодного симпозиума ACM по принципам распределенных вычислений — PODC '84 . стр. 233–242. дои : 10.1145/800222.806750 . ISBN 0897911431 . S2CID 2384672 .

[8] Стром, Роб; Йемини, Шаула (август 1985 г.). «Оптимистическое восстановление в распределенных системах» . Транзакции ACM в компьютерных системах . 3 (3): 204–226. дои : 10.1145/3959.3962 . S2CID 1941122 .

[9] Шмук, Фрэнк Б. (ноябрь 1985 г.). Программные часы и порядок событий в распределенной системе (неопубликовано).

[10] Лисков, Варвара; Ладин, Ривка (1986). «Высокодоступные распределенные сервисы и отказоустойчивая распределенная сборка мусора». Материалы пятого ежегодного симпозиума ACM по принципам распределенных вычислений - PODC '86 . стр. 29–39. дои : 10.1145/10590.10593 . ISBN 0897911989 . S2CID 16148617 .

[11] Рейналь, Мишель (февраль 1987 г.). «Распределенный алгоритм для предотвращения взаимного дрейфа между n логическими часами». Письма об обработке информации . 24 (3): 199–202. дои : 10.1016/0020-0190(87)90186-4 .

[5] Фидж, Колин Дж. (февраль 1988 г.). «Временные метки в системах передачи сообщений, сохраняющие частичный порядок» (PDF) . В К. Раймонде (ред.). Материалы 11-й Австралийской конференции по информатике (ACSC'88) . Том. 10. С. 56–66 . Проверено 13 февраля 2009 г.

[6] Маттерн, Фридеманн (октябрь 1988 г.). «Виртуальное время и глобальные состояния распределенных систем». В Коснаре, М. (ред.). Учеб. Практикум по параллельным и распределенным алгоритмам . Шато де Бонас, Франция: Эльзевир. стр. 215–226.

[7] Франсиско Торрес-Рохас; Мустак Ахамад (1999), «Правдоподобные часы: логические часы постоянного размера для распределенных систем» , Distributed Computing , 12 (4): 179–195, doi : 10.1007/s004460050065 , S2CID 2936350

[8] Агарвал, Анураг; Гарг, Виджай К. (17 июля 2005 г.). «Эффективное отслеживание зависимостей для соответствующих событий в системах с общей памятью» (PDF) . Материалы двадцать четвертого ежегодного симпозиума ACM по принципам распределенных вычислений . Ассоциация вычислительной техники. стр. 19–28. дои : 10.1145/1073814.1073818 . ISBN 1-58113-994-2 . S2CID 11779779 . Проверено 21 апреля 2021 г.

[9] Алмейда, Пауло; Бакеро, Карлос; Фонте, Виктор (2008), «Часы интервального дерева: логические часы для динамических систем», Бейкер, Теодор П.; Буи, Ален; Тиксёй, Себастьян (ред.), Принципы распределенных систем (PDF) , Конспекты лекций по информатике, том. 5401, Springer-Verlag, Конспекты лекций по информатике, стр. 259–274, Bibcode : 2008LNCS.5401.....B , doi : 10.1007/978-3-540-92221-6 , ISBN 978-3-540-92220-9

[10] Алмейда, Пауло; Бакеро, Карлос; Фонте, Виктор (2008), «Часы дерева интервалов: логические часы для динамических систем», Часы интервального дерева: логические часы для динамических систем , Конспект лекций по информатике, том. 5401, с. 259, номер doi : 10.1007/978-3-540-92221-6_18 , hdl : 1822/37748 , ISBN 978-3-540-92220-9

[11] Чжан, И (2014), «Предварительные сведения: результаты синхронизации дерева интервалов», Предварительные сведения: результаты синхронизации дерева интервалов (PDF)

[12] Поццетти, Томмазо; Кшемкальяни, Аджай Д. (1 апреля 2021 г.). «Сбрасываемые векторные часы для анализа причинно-следственных связей с применением к динамическому обнаружению гонок» . Транзакции IEEE в параллельных и распределенных системах . 32 (4): 772–785. дои : 10.1109/TPDS.2020.3032293 . S2CID 220362525 .

[13] Лум Рамабаджа (2019), The Bloom Clock , arXiv : 1905.13064 , Бибкод : 2019arXiv190513064R

[14] Кулкарни, Сандип С; Эпплтон, Гейб; Нгуен, Дуонг (4 января 2022 г.). «Достижение причинности с помощью физических часов». Материалы 23-й Международной конференции по распределенным вычислениям и сетям . стр. 97–106. arXiv : 2104.15099 . дои : 10.1145/3491003.3491009 . ISBN 9781450395601 . S2CID 233476293 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]