Логические часы механизм для захвата хронологических и причинно - следственных связей в распределенной системе . Часто распределенные системы могут не иметь физически синхронных глобальных часов. К счастью, во многих приложениях (таких как распределенная GNU make ), если два процесса никогда не взаимодействуют, отсутствие синхронизации не наблюдается. Более того, в этих приложениях процессам достаточно согласовать порядок событий (т. Е. Логические часы), а не время настенных часов. [1] Первая реализация логических часов, метки времени Лэмпорта , была предложена Лесли Лэмпортом в 1978 году ( премия Тьюринга в 2013 году).
Местное и глобальное время
В системах логических часов каждый процесс имеет две структуры данных: логическое местное время и логическое глобальное время . Логическое местное время используется процессом для отметки собственных событий, а логическое глобальное время - это локальная информация о глобальном времени. Специальный протокол используется для обновления логического местного времени после каждого локального события и логического глобального времени, когда процессы обмениваются данными. [2]
Приложения
Логические часы полезны при анализе вычислений, разработке распределенных алгоритмов, отслеживании отдельных событий и изучении прогресса вычислений.
Алгоритмы
Некоторые заслуживающие внимания алгоритмы логических часов:
- Метки времени Лампорта , которые представляют собой монотонно увеличивающиеся программные счетчики.
- Векторные часы , которые позволяют частично упорядочивать события в распределенной системе.
- Векторы версий , упорядочить реплики в соответствии с обновлениями в оптимистичной реплицируемой системе .
- Матричные часы , расширение векторных часов, которое также содержит информацию о представлениях системы другими процессами.
Рекомендации
- ^ «Распределенные системы, 3-е издание (2017)» . РАСПРОСТРАНЕННЫЕ СИСТЕМЫ.NET . Проверено 20 марта 2021 .
- ^ Глава 3: Логическое время // Аджай Кшемкаляни и Мукеш Сингхал, Распределенные вычисления: принципы, алгоритмы и системы, Cambridge University Press, 2008
Внешние ссылки
- Распределенная система логического времени // Роберто Бальдони, Сильвия Бономи. MIDLAB, Римский университет Ла Сапиенца
- Глава 3: Логическое время // Аджай Кшемкаляни и Мукеш Сингхал, Распределенные вычисления: принципы, алгоритмы и системы, Cambridge University Press, 2008
- Распределенные системы 06. Логические часы // Пол Кшизановски, Университет Рутгерса, осень 2014 г.