Выбор координатора

Физические часы.

После изобретения в 17 веке механических часов время измерялось астрономически. Интервал между двумя последовательными достижениями солнцем наивысшей точки на небе называется солнечным днем. Солнечная секунда равняется 1/86400(24*3600) части солнечного дня.

В 1940-х годах было установлено, что период вращения земли не постоянен - земля замедляет вращение из-за приливов и атмосферы. Геологи считают, что 300 миллионов лет назад в году было 400 дней. Происходят и изменения длительности дня по другим причинам. Поэтому стали вычислять за длительный период среднюю солнечную секунду.

С изобретением в 1948 году атомных часов появилась возможность точно измерять время независимо от колебаний солнечного дня. В настоящее время 50 лабораторий в разных точках земли имеют часы, базирующиеся на частоте излучения Цезия-133. Среднее значение является международным атомным временем (TAI), исчисляемым с 1 июля 1958 года.

Отставание TAI от солнечного времени компенсируется становится добавлением секунды тогда, когда разница больше 800 мксек. Это скорректированное время, называеемое UTC (Universal Coordinated Time), заменило прежний стандарт (Среднее время по Гринвичу - астрономическое время). При объявлении о добавлении секунды к UTC электрические компании меняют частоту с 60 Hz на 61 Hz (c 50 на 51) на период времени в 60 (50) секунд. Для обеспечения точного времени сигналы WWV передаются коротковолновым передатчиком (Fort Collins, Colorado) в начале каждой секунды UTC. Есть и другие службы времени.

В алгоритмах синхронизации времени есть две проблемы:

1. часы не должны ходить назад (надо ускорять или замедлять их для проведения коррекции)

2. ненулевое время прохождения сообщения о времени (можно многократно замерять время прохождения и брать среднее).

Многие распределенные алгоритмы требуют, чтобы один из процессов выполнял функции координатора, инициатора или некоторую другую специальную роль. Выбор такого специального процесса будем называть выбором координатора. При этом очень часто бывает не важно, какой именно процесс будет выбран. Можно считать, что обычно выбирается процесс с самым большим уникальным номером. Могут применяться разные алгоритмы, имеющие одну цель - если процедура выборов началась, то она должна закончиться согласием всех процессов относительно нового координатора.

Алгоритм "задиры"

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

1. P посылает сообщение "ВЫБОРЫ" всем процессам с большими чем у него номерами.

2. Если нет ни одного ответа, то P считается победителем и становится координатором.

3. Если один из процессов с большим номером ответит, то он берет на себя проведение выборов. Участие процесса P в выборах заканчивается.

В любой момент процесс может получить сообщение "ВЫБОРЫ" от одного из коллег с меньшим номером. В этом случае он посылает ответ "OK", чтобы сообщить, что он жив и берет проведение выборов на себя, а затем начинает выборы (если к этому моменту он уже их не вел). Следовательно, все процессы прекратят выборы, кроме одного - нового координатора. Он извещает всех о своей победе и вступлении в должность сообщением "КООРДИНАТОР". Если процесс выключился из работы, а затем захотел восстановить свое участие, то он проводит выборы (отсюда и название алгоритма).

Дата добавления: 2015-04-25