Алгоритм Беркли

Алгоритм Беркли — это протокол синхронизации времени в распределённых вычислительных системах, предназначенный для согласования показаний часов нескольких узлов (компьютеров, серверов) относительно одного ведущего узла (координатора). Алгоритм был разработан в 1989 году в Калифорнийском университете в Беркли (США) для использования в системах, где отсутствует доступ к точным внешним источникам времени, таким как GPS или спутниковые атомные часы. В отличие от протокола NTP, который ориентирован на синхронизацию с эталонными серверами, алгоритм Беркли работает в локальной сети и не требует внешнего эталона, а вычисляет «среднее» время на основе показаний всех участников.

Принцип работы

Алгоритм Беркли основан на модели «ведущий-ведомые» (master-slave). Один из узлов сети назначается координатором (ведущим), который периодически инициирует процедуру синхронизации. Координатор не обладает эталонным временем, а лишь собирает данные от других узлов и вычисляет корректирующее смещение.

Этапы синхронизации

1. Запрос времени — координатор отправляет широковещательное сообщение всем остальным узлам (ведомым) с запросом их текущего локального времени.
2. Ответы — каждый ведомый узел фиксирует момент получения запроса, считывает своё локальное время и отправляет его обратно координатору. Время передачи сообщения (задержка) обычно игнорируется или оценивается приблизительно, так как алгоритм рассчитан на работу в локальной сети с низкой и предсказуемой задержкой.
3. Вычисление среднего времени — координатор собирает все полученные значения времени, отбрасывает выбросы (например, значения, сильно отклоняющиеся от остальных, чтобы избежать влияния сбоев или неточных часов) и вычисляет среднее арифметическое время.
4. Расчёт смещений — для каждого узла координатор вычисляет разницу между его локальным временем и средним временем. Это смещение может быть положительным (часы спешат) или отрицательным (часы отстают).
5. Коррекция — координатор отправляет каждому ведомому узлу сообщение с величиной необходимой корректировки (смещением). Ведомые узлы применяют эту коррекцию, изменяя свои часы. Координатор также корректирует собственные часы на основе вычисленного среднего.
6. Повторение — процедура повторяется через заданный интервал (обычно от нескольких секунд до нескольких минут), чтобы компенсировать дрейф часов.

Особенности коррекции

• Коррекция может быть как положительной, так и отрицательной, то есть часы могут как ускоряться, так и замедляться.
• Чтобы избежать резких скачков времени, которые могут нарушить работу приложений (например, баз данных или систем реального времени), коррекция часто выполняется постепенно: часы подстраиваются с помощью изменения скорости хода (например, на несколько миллисекунд в секунду), а не мгновенным сбросом.
• В случае сбоя координатора (например, его отключения) алгоритм предусматривает выбор нового ведущего узла, обычно на основе голосования или заранее заданной иерархии.

История и происхождение

Алгоритм Беркли был разработан в 1989 году группой исследователей из Калифорнийского университета в Беркли под руководством Густаво Алонсо (Gustavo Alonso) и Дэвида Черитона (David Cheriton). Первоначально он был создан для операционной системы Sprite, экспериментальной распределённой ОС, разрабатываемой в том же университете. Целью было обеспечить синхронизацию времени в локальной сети без использования дорогостоящих аппаратных часов или внешних служб времени. В отличие от более ранних алгоритмов, таких как алгоритм Кристиана (Christian’s algorithm), который полагался на внешний эталон, алгоритм Беркли был полностью децентрализованным в том смысле, что все узлы равноправны, хотя один из них временно берёт на себя роль координатора.

В 1990-х годах алгоритм Беркли был включён в состав многих дистрибутивов UNIX и BSD, а также использовался в кластерных системах и встроенных решениях. С развитием протокола NTP (Network Time Protocol), который стал стандартом де-факто для синхронизации времени в интернете, популярность алгоритма Беркли снизилась, однако он остаётся востребованным в изолированных сетях, где нет доступа к внешним источникам времени.

Применение

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

• Кластерные вычисления — в суперкомпьютерах и вычислительных кластерах для синхронизации логов, планировщиков задач и распределённых транзакций.
• Встроенные системы — в промышленных контроллерах, системах автоматизации и IoT-устройствах, работающих в локальных сетях.
• Операционные системы — некоторые дистрибутивы Linux и BSD используют модификации алгоритма Беркли для синхронизации времени в виртуальных машинах или контейнерах.
• Распределённые базы данных — для обеспечения согласованности данных при репликации и транзакциях (например, в системах, не использующих глобальные часы, такие как Google Spanner, который применяет атомные часы, но в локальных решениях может использоваться алгоритм Беркли).

Ограничения и недостатки

• Зависимость от координатора — при отказе ведущего узла синхронизация прекращается до переизбрания нового координатора, что может вызвать временную рассинхронизацию.
• Игнорирование задержек — алгоритм не учитывает время передачи сообщений, что вносит погрешность, особенно в сетях с высокой задержкой или переменной нагрузкой. В локальных сетях с малыми задержками (менее 1 мс) эта погрешность незначительна, но в глобальных сетях она становится критической.
• Отсутствие внешнего эталона — алгоритм синхронизирует часы относительно друг друга, но не гарантирует соответствия абсолютному времени (UTC). Со временем среднее время может дрейфовать относительно реального.
• Уязвимость к сбоям — если один из узлов предоставляет ложные данные (например, из-за сбоя часов или злонамеренного вмешательства), это может исказить среднее время. Для защиты используются методы отбрасывания выбросов и проверки согласованности.

Сравнение с другими протоколами

Интересные факты

• Алгоритм Беркли иногда называют «алгоритмом среднего времени», так как он вычисляет среднее арифметическое, а не использует опорный сигнал.
• В некоторых реализациях вместо среднего арифметического используется медиана, что повышает устойчивость к выбросам.
• Алгоритм лёг в основу протокола PTP (Precision Time Protocol), который используется в промышленности для синхронизации с точностью до микросекунд.
• В 1990-х годах алгоритм Беркли был реализован в операционной системе Plan 9 от Bell Labs, где он использовался для синхронизации времени в распределённых файловых системах.

Источники

• Alonso, G., & Cheriton, D. (1989). "A Robust and Efficient Algorithm for Distributed Time Synchronization". University of California, Berkeley.
• Tanenbaum, A. S., & Van Steen, M. (2007). "Distributed Systems: Principles and Paradigms". Pearson.
• Coulouris, G., Dollimore, J., & Kindberg, T. (2012). "Distributed Systems: Concepts and Design". Addison-Wesley.
• RFC 1305 (NTPv3) и RFC 5905 (NTPv4) — для сравнения с алгоритмом Беркли.