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

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

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

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

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