Логические часы

Механизм фиксации хронологических и причинно-следственных связей

Логические часы — это механизм фиксации хронологических и причинно-следственных связей в распределенной системе . Часто в распределенных системах могут отсутствовать физически синхронные глобальные часы. Во многих приложениях (таких как распределенное GNU make ), если два процесса никогда не взаимодействуют, отсутствие синхронизации незаметно, и в этих приложениях достаточно, чтобы процессы согласовали порядок событий (т. е. логические часы), а не настенные часы. время часов. ^[1] Первая реализация логических часов, метки времени Лэмпорта , была предложена Лесли Лэмпортом в 1978 году ( Премия Тьюринга в 2013 году).

Местное и глобальное время

В системах логических часов каждый процесс имеет две структуры данных: логическое локальное время и логическое глобальное время . Логическое локальное время используется процессом для обозначения собственных событий, а логическое глобальное время — это локальная информация о глобальном времени. Специальный протокол используется для обновления логического локального времени после каждого локального события и логического глобального времени, когда процессы обмениваются данными. ^[2]

Приложения

Логические часы полезны при анализе вычислений, разработке распределенных алгоритмов, отслеживании отдельных событий и изучении прогресса вычислений.

Алгоритмы

Некоторые заслуживающие внимания алгоритмы логических часов:

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

Рекомендации

1. «Распределенные системы, 3-е издание (2017 г.)» . РАСПРЕДЕЛЕННЫЕ-СИСТЕМЫ.NET . Проверено 20 марта 2021 г.
2. Глава 3: Логическое время // Аджай Кшемкальяни и Мукеш Сингхал, Распределенные вычисления: принципы, алгоритмы и системы, Cambridge University Press, 2008 г.

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

• Логическое время распределенной системы // Роберто Бальдони, Сильвия Бономи. MIDLAB, Римский университет Сапиенца
• Глава 3: Логическое время // Аджай Кшемкальяни и Мукеш Сингхал, Распределенные вычисления: принципы, алгоритмы и системы, Cambridge University Press, 2008 г.
• Распределенные системы 06. Логические часы // Пол Кржижановский, Университет Рутгерса, осень 2014 г.