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

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

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

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

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