Синхронизация часов
Постановка задачи
Предыстория и обзор
Координация работы процессоров, расположенных в разных местах, является одной из фундаментальных задач распределенных вычислений. В своей основополагающей работе Лэмпорт [4, 5] исследовал модель, в которой единственным источником координации является обмен сообщениями между процессорами; время, проходящее между последовательными шагами на одном и том же процессоре, а также время, проводимое сообщением в пути, может быть произвольно большим или малым. Лэмпорт заметил, что в этой модели, названной асинхронной, такие временные понятия, как «прошлое» и «будущее», являются производными от причинной зависимости – понятия, имеющего простую алгоритмическую интерпретацию. Работу Пэтт-Шамира и Раджсбаума [10] можно рассматривать как расширение качественной трактовки Лэмпорта с помощью количественных понятий. Например, утверждение типа «событие [math]\displaystyle{ a }[/math] произошло до события [math]\displaystyle{ b }[/math]» может быть уточнено до утверждения типа «событие [math]\displaystyle{ a }[/math] произошло как минимум за 2 единицы времени и как максимум за 5 единиц времени до события [math]\displaystyle{ b }[/math]». Их подход отличается от большинства предыдущих теоретических работ, в которых основное внимание уделялось аспектам синхронизации часов, связанным с линейным программированием (см. ниже).
Основная идея работы [10] заключается в следующем. Во-первых, структура расширяется, позволяя устанавливать верхние и нижние границы времени, которое проходит между парами событий, используя спецификацию реального времени системы. Понятие спецификации реального времени представляется очень естественным. Например, большинство процессоров имеют локальные часы, скорость хода которых обычно ограничена по отношению к реальному времени (эти границы обычно называют границами «дрейфа» часов). Другим примером могут служить события отправки и получения некоторого сообщения: всегда верно, что событие получения происходит раньше события отправки, а во многих случаях возможны более жесткие нижние и верхние границы. Определив спецификацию реального времени, авторы работы [10] показывают, как с помощью простых теоретико-графовых понятий можно наилучшим образом объединить эти локальные ограничения с глобальными. Это позволяет вывести оптимальные протоколы, которые, например, говорят, каковы текущие показания удаленных часов. Если эти удаленные часы являются стандартными, в результате имеет место оптимальная синхронизация часов в общепринятом смысле (ниже это понятие будет названо «внешней синхронизацией»).
Формальная модель
Система состоит из фиксированного множества взаимосвязанных процессоров. Каждый процессор имеет свои локальные часы. Выполнение системы представляет собой последовательность событий, в которой каждое событие является либо событием отправки, либо событием получения, либо внутренним событием. Что касается коммуникации, то предполагается только, что каждое событие получения сообщения [math]\displaystyle{ m }[/math] имеет уникальное соответствующее событие отправки [math]\displaystyle{ m }[/math]. Это означает, что сообщения могут быть произвольно потеряны, продублированы или переупорядочены, но не повреждены. Каждое событие [math]\displaystyle{ e }[/math] происходит в одном определенном процессоре и имеет два вещественных числа, связанных с ним: его локальное время, обозначаемое LT(e), и его реальное время, обозначаемое RT(e). Локальное время события моделирует показания локальных часов в момент наступления этого события, и локальный процессор может использовать это значение, например, для вычислений или для передачи другому процессору. В отличие от этого, реальное время события не наблюдается процессорами: это абстрактное понятие, существующее только в анализе.
Наконец, свойства реального времени системы моделируются парой функций, которые отображают каждую пару событий на [math]\displaystyle{ \mathbb{R} \cup \{ - \infty, \infty \} }[/math]: если даны два события [math]\displaystyle{ e }[/math] и [math]\displaystyle{ e' }[/math], то [math]\displaystyle{ L(e, e') = \ell }[/math] означает, что [math]\displaystyle{ RT(e') - RT(e) \ge \ell }[/math], а [math]\displaystyle{ H(e, e') = h }[/math] означает, что [math]\displaystyle{ RT(e') - RT(e) \le h }[/math], то есть, что количество единиц (реального) времени с момента наступления события [math]\displaystyle{ e }[/math] до наступления [math]\displaystyle{ e' }[/math] не меньше [math]\displaystyle{ \ell }[/math] и не больше [math]\displaystyle{ h }[/math]. Без потери общности можно предположить, что [math]\displaystyle{ L(e, e') = - H(e', e) }[/math] для всех событий [math]\displaystyle{ e }[/math], [math]\displaystyle{ e' }[/math] (просто используем меньшее из них). В дальнейшем изложении для представления спецификации реального времени будет использоваться только функция верхних границ [math]\displaystyle{ H }[/math].
Некоторые особые случаи свойств реального времени особенно важны. В полностью асинхронной системе [math]\displaystyle{ H(e', e) = 0 }[/math], либо если [math]\displaystyle{ e }[/math] происходит раньше [math]\displaystyle{ e' }[/math] в том же процессоре, либо если [math]\displaystyle{ e }[/math] и [math]\displaystyle{ e' }[/math] являются событиями отправки и получения, соответственно, одного и того же сообщения. (Для простоты предполагается, что два упорядоченных события могут иметь одинаковое реальное время наступления). Во всех остальных случаях [math]\displaystyle{ H(e, e') = \infty }[/math]. Противоположный конец модельного спектра представляет модель часов без дрейфа, в которой все локальные часы идут точно со скоростью реального времени. Формально в этом случае [math]\displaystyle{ H(e, e') = LT(e') - LT(e) }[/math] для любых двух событий [math]\displaystyle{ e }[/math] и [math]\displaystyle{ e' }[/math], происходящих в одном и том же процессоре. Очевидно, это имеет место, когда только некоторые часы в системе свободны от дрейфа.
Алгоритмы
В данной работе генерация и доставка сообщений полностью отделены от информации о них. Формально предполагается, что сообщения генерируются некоторым «модулем отправки», а доставляются «системой коммуникации». Задача алгоритмов заключается в том, чтобы добавлять содержимое в сообщения и переменные состояния в каждом узле. (Идея отделения информации о синхронизации от генерации сообщений была предложена в работе [1]). Алгоритм располагает только локальной информацией, то есть содержимым локальных переменных состояния и показаниями локальных часов, а также содержимым входящего сообщения, если мы имеем дело с событием получения. Также предполагается, что алгоритму известна спецификация реального времени. Совокупность событий, их … и локальных времен (но не реальных времен) называется ракурсом данного выполнения. Алгоритмы, таким образом, могут использовать в качестве входных данных только ракурс выполнения и его спецификацию реального времени.
Формулировка задачи
Простейшим вариантом синхронизации часов является внешняя синхронизация, при которой у одного из процессоров, называемого источником, имеются часы без дрейфа, и задачей всех процессоров является поддержка как можно более точной оценки текущего показания часов источника. Эта формулировка соответствует ньютоновской модели, в которой процессоры находятся в четко определенной системе временных координат, а часы источника отсчитывают стандартное время. Говоря формально, при внешней синхронизации каждый процессор [math]\displaystyle{ v }[/math] имеет две выходные переменные [math]\displaystyle{ \Delta_v }[/math] и [math]\displaystyle{ \varepsilon_v }[/math]; оценка [math]\displaystyle{ v }[/math] времени источника в заданном состоянии равна [math]\displaystyle{ LT_v + \Delta_v }[/math], где [math]\displaystyle{ LT_v }[/math] – текущее локальное время в [math]\displaystyle{ v }[/math]. От алгоритма требуется, чтобы разница между временем источника и его оценкой была не более [math]\displaystyle{ \varepsilon_v }[/math] (заметим, что [math]\displaystyle{ \Delta_v }[/math], как и [math]\displaystyle{ \varepsilon_v }[/math], может динамически меняться в процессе выполнения). О производительности алгоритма судят по значению переменных [math]\displaystyle{ \varepsilon_v }[/math]: чем они меньше, тем лучше.
В другом варианте задачи, называемом внутренней синхронизацией, нет выделенного процессора, а требование сводится к тому, чтобы все часы имели значения, близкие друг к другу. Определение этого варианта не так уж просто, поскольку тривиальные решения (например, «установить на всех часах значение 0 на все время») должны быть исключены.
Основные результаты
Ключевой конструкцией, используемой в работе [10], является граф синхронизации выполнения, определяемый путем объединения понятий локального времени и спецификации реального времени следующим образом.
Определение 1. Пусть [math]\displaystyle{ \beta }[/math] – ракурс выполнения системы, а [math]\displaystyle{ H }[/math] – спецификация реального времени для [math]\displaystyle{ \beta }[/math]. Граф синхронизации, порожденный [math]\displaystyle{ \beta }[/math] и [math]\displaystyle{ H }[/math], является ориентированным взвешенным графом [math]\displaystyle{ \Gamma_{\beta H} = (V, E, w) }[/math], где [math]\displaystyle{ V }[/math] – множество событий в [math]\displaystyle{ \beta }[/math], и для каждой упорядоченной пары событий [math]\displaystyle{ p \; q }[/math] в [math]\displaystyle{ \beta }[/math], такой, что [math]\displaystyle{ H(p, q) \lt \infty }[/math], существует ориентированное ребро [math]\displaystyle{ (p, q) \in E }[/math].
Вес ребра [math]\displaystyle{ (p, q) }[/math] равен [math]\displaystyle{ w(p, q) \overset{def}{=} H(p, q) - LT(p) + LT(q) }[/math].
Естественное понятие расстояния от события [math]\displaystyle{ p }[/math] до события [math]\displaystyle{ q }[/math] в графе синхронизации [math]\displaystyle{ \Gamma }[/math], обозначаемое [math]\displaystyle{ d_{\Gamma}(p, q) }[/math] определяется длиной кратчайшего взвешенного пути от [math]\displaystyle{ p }[/math] до [math]\displaystyle{ q }[/math] или равно бесконечности, если [math]\displaystyle{ q }[/math] недостижимо из [math]\displaystyle{ p }[/math]. Поскольку веса могут быть отрицательными, необходимо доказать, что понятие точно определено: действительно, было показано, что если [math]\displaystyle{ \Gamma_{\beta H} }[/math] получен из выполнения с ракурсом [math]\displaystyle{ \beta }[/math], удовлетворяющего спецификации реального времени [math]\displaystyle{ H }[/math], то [math]\displaystyle{ \Gamma_{\beta H} }[/math] не содержит ориентированных циклов с отрицательным весом.
Основной алгоритмический результат, касающийся графов синхронизации, представлен в виде следующей теоремы.
Теорема 1. Пусть [math]\displaystyle{ \alpha }[/math] – выполнение с ракурсом [math]\displaystyle{ \beta }[/math]. Тогда [math]\displaystyle{ \alpha }[/math] удовлетворяет спецификации реального времени [math]\displaystyle{ H }[/math] тогда и только тогда, когда [math]\displaystyle{ RT(p) - RT(q) \le d_{\Gamma}(p, q) + LT(p) - LT(q) }[/math] для любых двух событий [math]\displaystyle{ p }[/math] и [math]\displaystyle{ q }[/math] в [math]\displaystyle{ \Gamma_{\beta H} }[/math].
Заметим, что все величины, входящие в правую часть неравенства, доступны алгоритму синхронизации, который в результате может определить верхние границы реального времени, проходящего между событиями. Более того, эти границы являются наилучшими из возможных, что следует из нижеследующей теоремы.
Теорема 2. Пусть [math]\displaystyle{ \Gamma_{\beta H} = (V, E, w) }[/math] – граф синхронизации, полученный из ракурса [math]\displaystyle{ \beta }[/math], удовлетворяющего спецификации реального времени [math]\displaystyle{ H }[/math]. Тогда для любого заданного события [math]\displaystyle{ p_0 \in V }[/math] и для любого конечного числа [math]\displaystyle{ N \gt 0 }[/math] существуют исполнения [math]\displaystyle{ \alpha_0 }[/math] и [math]\displaystyle{ \alpha_1 }[/math] с ракурсом [math]\displaystyle{ \beta }[/math], удовлетворяющие спецификации [math]\displaystyle{ H }[/math], такие, что выполняются следующие присваивания реального времени.
- В [math]\displaystyle{ \alpha_0 }[/math] для всех [math]\displaystyle{ q \in V }[/math] с [math]\displaystyle{ d_{\Gamma} (q, p_0) \lt \infty }[/math] верно [math]\displaystyle{ RT_{\alpha_0}(q) = LT(q) + d_{\Gamma}(q, p_0) }[/math], и для всех [math]\displaystyle{ q \in V }[/math] с [math]\displaystyle{ d_{\Gamma}(q, p_0) = \infty }[/math] верно [math]\displaystyle{ RT_{\alpha_0} \gt LT(q) + N. }[/math]
- В [math]\displaystyle{ \alpha_1 }[/math] для всех [math]\displaystyle{ q \in V }[/math] с [math]\displaystyle{ d_{\Gamma} (p_0, q) \lt \infty }[/math] верно [math]\displaystyle{ RT_{\alpha_1}(q) = LT(q) - d_{\Gamma}(p_0, q) }[/math], и для всех [math]\displaystyle{ q \in V }[/math] с [math]\displaystyle{ d_{\Gamma}(p_0, q) = \infty }[/math] верно [math]\displaystyle{ RT_{\alpha_1} \lt LT(q) - N. }[/math]
С алгоритмической точки зрения важным недостатком результатов теорем 1 и 2 является то, что они зависят от ракурса выполнения, который может неограниченно расти. Так ли он необходим? Последний общий результат в работе [10] отвечает на этот вопрос утвердительно. В частности, было показано, что в некотором варианте вычислительной модели ветвящейся программы пространственная сложность любого алгоритма синхронизации, работающего с произвольными спецификациями реального времени, не может быть ограничена функцией от размера системы. Результат доказывается путем рассмотрения нескольких сценариев на простой системе из четырех процессоров на одной линии.
Последующие разработки
Основываясь на понятии графа синхронизации, Островский и Пэтт-Шамир представили уточненный оптимальный алгоритм общего вида для синхронизации часов [9]. Идея упомянутой работы заключается в том, чтобы отбрасывать части графов синхронизации, которые больше не имеют значения. Грубо говоря, сложность алгоритма ограничена полиномом от размера системы и соотношения скоростей процессоров.
Много теоретических работ было посвящено варианту задачи с внутренней синхронизацией. Например, Ланделиус и Линч [7] доказали, что в системе из [math]\displaystyle{ n }[/math] процессоров с полной связностью, если задержки сообщений могут принимать произвольные значения в диапазоне [0, 1], а локальные часы не имеют дрейфа, то наилучшая синхронизация, которую можно гарантировать, равна [math]\displaystyle{ 1 – \frac{1}{n} }[/math]. Хелперн и др. [3] распространили этот результат на графы общего вида, используя методы линейного программирования. Их работа, в свою очередь, была расширена Аттией и др. [1] для анализа любого конкретного выполнения (а не только наихудшего случая для данной топологии), но анализ выполняется в оффлайновом режиме и централизованно. Работа Пэтт-Шамира и Раджсбаума [11] распространила точку зрения «отдельного выполнения» на распределенные онлайн-алгоритмы и сместила фокус проблемы на внешнюю синхронизацию.
Недавно Фэн и Линч [2] доказали, что в линии из [math]\displaystyle{ n }[/math] процессоров, часы которых могут дрейфовать, ни один алгоритм не может гарантировать, что разница между показаниями часов всех пар соседей составляет o(log n/log log n).
Синхронизация часов очень полезна на практике. Некоторые увлекательные примеры можно найти, например, в работе Барбары Лисков [6]. Стоит отметить, что Интернет поддерживает протокол внешней синхронизации часов под названием NTP [8].
Применение
Теорема 1 сразу же дает алгоритм синхронизации часов: каждый процессор поддерживает известное ему представление части графа синхронизации. Это можно сделать с помощью протокола полной информации: этот граф отправляется в каждом исходящем сообщении, и всякий раз, когда приходит сообщение, граф расширяется, чтобы включить новую информацию из графа в пришедшем сообщении. Согласно теореме 2, полученный таким образом граф синхронизации представляет в любой момент времени всю доступную информацию, необходимую для оптимальной синхронизации. Для примера рассмотрим внешнюю синхронизацию. Непосредственно из определений следует, что все события, связанные с часами без дрейфа (например, события в узле-источнике), находятся на расстоянии 0 друг от друга в графе синхронизации и поэтому могут рассматриваться при вычислении расстояний как один узел s. Теперь, предполагая, что часы источника действительно показывают реальное время, легко увидеть, что для любого события p имеет место [math]\displaystyle{ RT(p) \in [LT(p) - d(s, p), LT(p) + d(p, s)] }[/math] и, более того, никаким корректным алгоритмом нельзя получить лучшие границы.
Описанный выше алгоритм общего вида (сохраняющий полный граф синхронизации) может быть использован и для получения оптимальных результатов для внутренней синхронизации.
Любопытен специальный случай, когда все часы не имеют дрейфа. В этом случае размер графа синхронизации остается фиксированным: аналогично узлу-источнику при внешней синхронизации, все события, происходящие на одном процессоре, могут быть отображены на один узел; параллельные ребра могут быть заменены одним новым ребром, вес которого минимален среди всех старых ребер. Таким образом, можно получить особенно эффективный распределенный алгоритм для решения задачи внешней синхронизации, основанный на распределенном алгоритме Беллмана-Форда для вычисления расстояний.
Наконец, отметим, что асинхронная модель также может рассматриваться как частный случай этой общей теории, в котором событие [math]\displaystyle{ p }[/math] «происходит раньше» события [math]\displaystyle{ q }[/math] тогда и только тогда, когда [math]\displaystyle{ d(p, q) \le 0 }[/math].
Открытые вопросы
Одной из центральных проблем при синхронизации часов являются ошибочные выполнения, при которых нарушается спецификация реального времени. Графы синхронизации выявляют любую обнаруживаемую ошибку: ракурсы, не имеющие выполнения, соответствующего спецификации реального времени, приводят к графам синхронизации с отрицательными циклами. Однако желательно преодолеть такие ошибки – например, удалив из графа синхронизации некоторые ребра, чтобы разорвать все циклы с отрицательным весом. Естественной целью в этом случае является удаление наименьшего числа ребер. Эта задача является APX-трудной, поскольку она обобщает задачу о множестве обратных дуг. К сожалению, нетривиальные приближенные алгоритмы для ее решения неизвестны.
См. также
Литература
1. Attiya, H., Herzberg, A., Rajsbaum, S.: Optimal clock synchronization under different delay assumptions. SIAM J. Comput. 25(2),369-389(1996)
2. Fan, R., Lynch, N.A.: Gradient clock synchronization. Distrib. Comput. 18(4), 255-266 (2006)
3. Halpern, J.Y., Megiddo, N., Munshi, A.A.: Optimal precision in the presence of uncertainty. J. Complex. 1,170-196 (1985)
4. Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21 (7), 558-565 (1978)
5. Lamport, L.: The mutual exclusion problem. Part I: A theory of interprocess communication. J. ACM 33(2), 313-326 (1986)
6. Liskov, B.: Practical uses of synchronized clocks in distributed systems. Distrib. Comput. 6,211 -219 (1993). Invited talk at the 9th Annual ACM Symposium on Principles of Distributed Computing, Quebec City 22-24 August 1990
7. Lundelius, J., Lynch, N.: A new fault-tolerant algorithm for clock synchronization. Inf. Comput. 77,1-36 (1988)
8. Mills, D.L.: Computer Network Time Synchronization: The Network Time Protocol. CRC Press, Boca Raton (2006)
9. Ostrovsky, R., Patt-Shamir, B.: Optimal and efficient clock synchronization under drifting clocks. In: Proceedings of the 18th Annual Symposium on Principles of Distributed Computing, pp. 3-12, Atlanta, May (1999)
10. Patt-Shamir, B., Rajsbaum, S.: A theory of clock synchronization. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pp. 810-819, Montreal, May (1994)
11. Patt-Shamir, B., Rajsbaum, S.: A theory of clock synchronization. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pp. 810-819, Montreal 23-25 May 1994
