Синхронизация часов: различия между версиями

Координация работы процессоров, расположенных в разных местах, является одной из фундаментальных задач распределенных вычислений. В своей основополагающей работе Лэмпорт [4, 5] исследовал модель, в которой единственным источником координации является обмен сообщениями между процессорами; время, проходящее между последовательными шагами на одном и том же процессоре, а также время, проводимое сообщением в пути, может быть произвольно большим или малым. Лэмпорт заметил, что в этой модели, названной асинхронной, такие временные понятия, как «прошлое» и «будущее», являются производными от причинной зависимости – понятия, имеющего простую алгоритмическую интерпретацию. Работу Пэтт-Шамира и Раджсбаума [10] можно рассматривать как расширение качественной трактовки Лэмпорта с помощью количественных понятий. Например, утверждение типа «событие a произошло до события b» может быть уточнено до утверждения типа «событие a произошло как минимум за 2 единицы времени и как максимум за 5 единиц времени до события b». Их подход отличается от большинства предыдущих теоретических работ, в которых основное внимание уделялось аспектам синхронизации часов, связанным с линейным программированием (см. ниже).

Основная идея работы [ ] заключается в следующем. Во-первых, структура расширяется, позволяя устанавливать верхние и нижние границы времени, которое проходит между парами событий, используя спецификацию реального времени системы. Понятие спецификации реального времени представляется очень естественным. Например, большинство процессоров имеют локальные часы, скорость хода которых обычно ограничена по отношению к реальному времени (эти границы обычно называют границами «дрейфа» часов). Другим примером могут служить события отправки и получения некоторого сообщения: всегда верно, что событие получения происходит раньше события отправки, а во многих случаях возможны более жесткие нижние и верхние границы. Определив спецификацию реального времени, авторы работы [10] показывают, как с помощью простых теоретико-графовых понятий можно наилучшим образом объединить эти локальные ограничения с глобальными. Это позволяет вывести оптимальные протоколы, которые, например, говорят, каковы текущие показания удаленных часов. Если эти удаленные часы являются стандартными, в результате имеет место оптимальная синхронизация часов в общепринятом смысле (ниже это понятие будет названо «внешней синхронизацией»).

Система состоит из фиксированного множества взаимосвязанных процессоров. Каждый процессор имеет свои локальные часы. Выполнение системы представляет собой последовательность событий, в которой каждое событие является либо событием отправки, либо событием получения, либо внутренним событием. Что касается коммуникации, то предполагается, что каждое событие получения сообщения m имеет уникальное соответствующее событие отправки m. Это означает, что сообщения могут быть произвольно потеряны, продублированы или переупорядочены, но не повреждены. Каждое событие e происходит в одном определенном процессоре и имеет два вещественных числа, связанных с ним: его локальное время, обозначаемое LT(e), и его реальное время, обозначаемое RT(e). Локальное время события моделирует показания локальных часов в момент наступления этого события, и локальный процессор может использовать это значение, например, для вычислений или для передачи другому процессору. В отличие от этого, реальное время события не наблюдается процессорами: это абстрактное понятие, существующее только в анализе.