Проблемы с пониманием алгоритма Беркли

Question

Я читал и пытался обернуть голову вокруг Алгоритма Беркли .

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

Например, рассмотрим трехпроцессную систему с процессами A, B и C, являющимися A лидером.

Теперь, если я прав, следует ожидать, что если B имеет значение дрейфа, равное 0,001 (т. Е. Каждые 1000 реальных секунд будет тикать только 999 раз), и я хочу убедиться, что ни один процесс Я бы сказал, что когда-нибудь выйдет из строя более, чем на 0,1 секунды, нужно будет синхронизировать часы каждые 100 секунд. Это означает, что я использую выражение

существо:

• delta_t максимальное время, которое мне разрешено ждать перед синхронизацией часы снова;
• дельта максимальной ошибки часов; скорость дрейфа;
• rho = дрейф

Моя проблема в том, что в заметках моего профессора можно найти следующее выражение:

, который также можно найти в других литературных источниках. Может кто-нибудь объяснить мне, почему у нас есть эти 2 во втором выражении? Я не уверен, что переменные действительно такие, какими я их предполагаю.

Спасибо

Answer 1

(небольшой отказ от ответственности: я не много занимался распределенными вычислениями. Возможно, я неправильно понял проблему. Почему бы не спросить профессора?)

Я считаю, что деление на два должно учитывать положительный и отрицательный дрейф нескольких процессов.

Если ваш наихудший дрейф составляет 0.001, рассмотрим B имеет дрейф +0.001 и C имеет -0.001. Если вы выберете delta-t в соответствии с вашей первоначальной формулой, разница во времени между B и C может увеличиться вдвое по сравнению с delta , который вы хотите получить до синхронизации.