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

Логические часы — механизм определения хронологической и причинно-следственной связи событий в распределённых системах, не имеющих единых физических часов. Алгоритмы логических часов позволяют получать частичное упорядочение событий по времени и обнаруживать нарушения причинно-следственных связей. Состояние логических часов может включаться в состав внутренних сообщений, пересылаемых между узлами системы. Впервые предложен и реализован Лэмпортом в 1978 году, его работа была отмечена Премией Тьюринга 2013 года.

Знание хронологической последовательности событий полезно для анализа вычислений, при создании распределённых алгоритмов, отслеживании отдельных событий или хода вычислений[1].

При реализации алгоритмов логических часов каждый процесс распределённой системы имеет собственные структуры данных для представления логического времени и использует специальный протокол при их обновлениях. Обычно в них хранится логическое локальное время для получения отметок времени для локальных событий и логическое глобальное время, соответствующее представлениям процесса о глобальном времени. Протокол задаёт правила обновления локального логического времени при выполнении событий и правила обновления логического глобального времени для отслеживания прогресса во всей распределённой системе[1].

Известные примеры логических часов:

Примечания
  1. Chapter 3: Logical Time // Ajay Kshemkalyani and Mukesh Singhal, Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press, 2008

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.