Алгоритм христианства - Cristians algorithm - Wikipedia

Алгоритм Кристиана (представлен Флавиу Кристиан в 1989 г.)[1] это метод для синхронизация часов который может использоваться во многих областях распределительной информатики, но в основном используется в малой задержке интрасети. Кристиан заметил, что этот простой алгоритм является вероятностным, поскольку он обеспечивает синхронизацию только в том случае, если время в оба конца (RTT) запроса является коротким по сравнению с требуемой точностью. Он также страдает в реализациях с использованием одного сервера, что делает его непригодным для многих распределительных приложений, где избыточность может иметь решающее значение.

Описание

Алгоритм Кристиана работает между процессом P и сервером времени S, подключенным к источнику привязки времени. Проще говоря:

  1. P запрашивает время у S
  2. После получения запроса от P, S готовит ответ и добавляет время T из своих собственных часов.
  3. Затем P устанавливает время равным T + RTT / 2.

Этот метод предполагает, что RTT делится поровну между запросом и ответом, что не всегда может иметь место, но является разумным предположением для подключения к локальной сети.

Дополнительную точность можно получить, сделав несколько запросов к S и используя ответ с самым коротким RTT.

Оценить точность системы можно следующим образом. Позволять мин быть минимальным временем для односторонней передачи сообщения. Самая ранняя точка, в которую S мог бы поместить время T, была мин после того, как P отправил свой запрос. Следовательно, время в S, когда сообщение P получено, находится в диапазоне (T + мин) в (T + RTT - мин). Ширина этого диапазона составляет (RTT - 2 *мин). Это дает точность (RTT / 2 - мин).

Смотрите также

Рекомендации

  1. ^ Кристиан, Ф. (1989), "Вероятностная синхронизация часов", Распределенных вычислений, Спрингер, 3 (3): 146–158, Дои:10.1007 / BF01784024