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

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

В данной работе генерация и доставка сообщений полностью отделены от информации о них. Формально предполагается, что сообщения генерируются некоторым «модулем отправки», а доставляются «системой коммуникации». Задача алгоритмов заключается в том, чтобы добавить содержимое в сообщения и переменные состояния в каждом узле. (Идея отделения информации о синхронизации от генерации сообщений была предложена в работе [1]). Алгоритм располагает только локальной информацией, то есть содержимым локальных переменных состояния и показаниями локальных часов, а также содержимым входящего сообщения, если мы имеем дело с событием приема. Также предполагается, что алгоритму известна спецификация реального времени. Совокупность событий, их … и локальных времен (но не реальных времен) называется ''ракурсом'' данного выполнения.  Алгоритмы, таким образом, могут использовать в качестве входных данных только ракурс выполнения и его спецификацию реального времени.

Ключевой конструкцией, используемой в [ ], является граф синхронизации выполнения, определяемый путем объединения понятий локального времени и спецификации реального времени следующим образом.

Определение 1. Пусть f$ – ракурс выполнения системы, а H – спецификация реального времени для f$. Граф синхронизации, порожденный f$ и H, является ориентированным взвешенным графом Грц = (V;E;w), где V – множество событий в /}, и для каждой упорядоченной пары событий p q в /}, такой, что H(p; q) < 1, существует ориентированное ребро (p; q) 2 E.

Вес ребра (p, q) равен w(p; q) = H(p; q)-UT(p) + LT(q).

Естественное понятие расстояния от события p до события q в графе синхронизации Г, обозначаемое drip, Ф> определяется длиной кратчайшего взвешенного пути от p до q, или бесконечностью, если q недостижимо из p. Поскольку веса могут быть отрицательными, необходимо доказать, что понятие точно определено: действительно, было показано, что если Грн получен из выполнения с ракурсом f$, удовлетворяющего спецификации реального времени H, то Грн не содержит ориентированных циклов с отрицательным весом.

Теорема 1. Пусть a – выполнение с ракурсом f$. Тогда a удовлетворяет спецификации реального времени H тогда и только тогда, когда RT(p) - RT(q) < dr(p, q) + LT(p) - LT(q) для любых двух событий p и q в Грн.

Теорема 2. Пусть Грн = (V, E, w) – граф синхронизации, полученный из ракурса f$, удовлетворяющего спецификации реального времени H. Тогда для любого заданного события p0 2 V и для любого конечного числа N > 0 существуют исполнения ao и a\ с ракурсом f$, удовлетворяющие спецификации H, такие, что выполняются следующие присваивания реального времени.

В aQ для всех q 2 V с dpiq,po) < 1, RTao((j) = LT(q) + dp(q,po)> и для всех q 2 V с dp(q,po) =

- В a\,для всех q 2 V с dripo, q) < 1, RTai((j) = LT(q) - dripo, q), и для всех q 2 V с dripo, q) = ™,R7ai(q)<L7(q)-N.

С алгоритмической точки зрения важным недостатком результатов теорем 1 и 2 является то, что они зависят от ракурса выполнения, которое может неограниченно расти. Так ли оно необходимо? Последний общий результат в работе [10] отвечает на этот вопрос утвердительно. В частности, было показано, что в некотором варианте вычислительной модели ветвящейся программы пространственная сложность любого алгоритма синхронизации, работающего с произвольными спецификациями реального времени, не может быть ограничена функцией от размера системы. Результат доказывается путем рассмотрения нескольких сценариев на простой системе из четырех процессоров на одной линии.

Основываясь на понятии графа синхронизации, Островский и Пэтт-Шамир представляют уточненный оптимальный алгоритм общего вида для синхронизации часов [ ]. Идея в работе [9] заключается в том, чтобы отбрасывать части графов синхронизации, которые больше не имеют значения. Грубо говоря, сложность алгоритма ограничена полиномом от размера системы и соотношения скоростей процессоров.

Много теоретических работ было посвящено варианту задачи с внутренней синхронизацией. Например, Ланделиус и Линч [ ] доказали, что в системе из n процессоров с полной связностью, если задержки сообщений могут принимать произвольные значения в диапазоне [0, 1], а локальные часы не имеют дрейфа, то наилучшая синхронизация, которую можно гарантировать, равна 1 – ^. Хелперн и др. [ ] распространили свой результат на графы общего вида, используя методы линейного программирования. Эта работа, в свою очередь, была расширена Аттией и др. [ ] для анализа любого конкретного выполнения (а не только наихудшего случая для данной топологии), но анализ выполняется в оффлайновом режиме и централизованно. Работа Пэтт-Шамира и Раджсбаума [11] распространила точку зрения «на отдельное выполнение» на распределенные онлайн-алгоритмы и сместила фокус проблемы на внешнюю синхронизацию.

Недавно Фэн и Линч [ ] доказали, что в линии из n процессоров, часы которых могут дрейфовать, ни один алгоритм не может гарантировать, что разница между показаниями часов всех пар соседей составляет o(log n/log log n).

Синхронизация часов очень полезна на практике. Некоторые увлекательные примеры можно найти , например, в работе Барбары Лисков [ ]. Стоит отметить, что Интернет предоставляет протокол для внешней синхронизации часов под названием NTP [8].

Теорема 1 сразу же дает алгоритм синхронизации часов: каждый процессор поддерживает известное ему представление части графа синхронизации. Это можно сделать с помощью протокола полной информации: этот граф отправляется в каждом исходящем сообщении, и всякий раз, когда приходит сообщение, граф расширяется, чтобы включить новую информацию из графа в пришедшем сообщении. Согласно Теореме 2, полученный таким образом граф синхронизации представляет в любой момент времени всю доступную информацию, необходимую для оптимальной синхронизации. Для примера рассмотрим внешнюю синхронизацию. Непосредственно из определений следует, что все события, связанные с часами без дрейфа (например, события в узле-источнике), находятся на расстоянии 0 друг от друга в графе синхронизации и поэтому могут рассматриваться при вычислении расстояния как один узел s. Теперь, предполагая, что часы источника действительно показывают реальное время, легко увидеть, что для любого события p,

RT(p) 2 [LT(p) - d(s; p); LT(p) + d(p; s)] ;

и, более того, никаким корректным алгоритмом нельзя получить лучшие границы.

Наконец, отметим, что асинхронная модель также может рассматриваться как частный случай этой общей теории, в котором событие p «происходит раньше» события q тогда и только тогда, когда d(p, q) < 0.