Алгоритм Беркли - Berkeley algorithm

В Алгоритм Беркли это метод синхронизация часов в распределенных вычислений что предполагает, что ни одна машина не имеет точного источника времени. Он был разработан Гуселлой и Затти в Калифорнийском университете в Беркли в 1989 году.[1] Нравиться Алгоритм Кристиана, он предназначен для использования в интрасети.

Алгоритм

В отличие от Алгоритм Кристиана, серверный процесс в алгоритме Беркли, называемый лидер, периодически опрашивает других последователь процессы. В общем, алгоритм таков:

  1. А лидер выбирается через избирательный процесс Такие как Алгоритм Чанга и Робертса.
  2. В лидер опрашивает подписчики кто отвечает за свое время так же, как Алгоритм Кристиана.
  3. В лидер наблюдает за время в оба конца (RTT) сообщений и оценивает время каждого последователь и свое собственное.
  4. В лидер затем усредняет время часов, игнорируя любые получаемые значения, далеко выходящие за рамки других значений.
  5. Вместо того, чтобы отправлять обновленное текущее время обратно другому процессу, лидер затем отправляет сумму (положительную или отрицательную), которую каждый последователь должен настроить свои часы. Это позволяет избежать дополнительной неопределенности из-за RTT на последователь процессы.

С помощью этого метода среднее значение компенсирует тенденцию отдельных часов к смещению. Гуселла и Затти опубликовали результаты с участием 15 компьютеров, часы которых были синхронизированы с точностью до 20-25 миллисекунд с использованием их протокола.

Компьютерные системы обычно избегают перемотки своих часов, когда они получают отрицательное изменение часов от лидера. Это нарушит свойство монотонности времени, которое является фундаментальным допущением в некоторых алгоритмах самой системы или в таких программах, как делать. Простым решением этой проблемы является остановка часов на время, указанное лидером, но это упрощенное решение также может вызвать проблемы, хотя они менее серьезны. Для незначительных корректировок большинство систем замедляют часы (так называемое «вращение часов»), применяя корректировку в течение более длительного периода времени.

Часто любой клиент, часы которого отличаются на значение вне заданного допуска, не учитывается при усреднении результатов. Это предотвращает резкое искажение общего системного времени из-за ошибочных часов.

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

  1. ^ Gusella, R .; Затти, С. (1989), "Точность синхронизации часов, достигаемая с помощью TEMPO в Berkeley UNIX 4.3BSD", IEEE Transactions по разработке программного обеспечения, IEEE, 15 (7): 847–853, Дои:10.1109/32.29484