Алгоритм предназначен для динамического выбора координатора на основе локальных оценок сайтов. Предполагается, что каналы связи надежны, а сайты иногда могут прерывать (например, из-за отказов) свое функционирование.
Сайты обмениваются сообщениями с тремя возможными значениями: «выборы», «ответ», «координатор». Сообщение «выборы» посылается для объявления выборов. Сообщение «ответ» посылается в ответ на объявление выборов. Сообщение «координатор» посылается для объявления идентификатора нового координатора.
Алгоритм выборов может начать любой сайт Si , который определил, что текущий координатор SC не функционирует (например, если ему слишком долго приходится ожидать сообщения от координатора).
Алгоритм состоит из следующих шагов.
1. Сайт Si рассылает сообщение «выборы» всем другим сайтам, имеющим большую оценку est(Sj), чем у него. Он ожидает, что они отправят ему сообщения «ответ».
2. Ожидание сайтом Si ответов длится не более чем время T. Если за это время ответы не получены, то сайт Si объявляет себя координатором и уведомляет об этом сайты с меньшей оценкой, чем est(Si) путем отправки им сообщений «координатор». Если же ответы получены, то сайт Si ожидает еще некоторое ограниченное время прихода сообщения «координатор» (возможно, кто-то из «старших» товарищей возьмет на себя функции координатора). Если он не дождался сообщения «координатор», сайт Si начинает новые выборы.
3. Если сайт Si получает сообщение «координатор», то он записывает идентификатор сайта, с которого это сообщение было получено, и в дальнейшем общается с этим сайтом как с координатором.
4. Если сайт Sj получает сообщение «выборы» и намерен участвовать в выборах, то он возвращает сообщение «ответ», после чего начинает новые выборы (напомним, его оценка est(Sj) больше, чем оценка est(Si) сайта, проводящего сейчас выборы).
5. Если происходит рестарт сайта SC , то он начинает выборы. В том случае, если его оценка est(SC) является наивысшей, он объявляет себя координатором и сообщает об этом другим сайтам. Это происходит, несмотря на то, что какой-то сайт в период неработоспособности SC выиграл выборы и функционирует сейчас как координатор. Происходит смещение «временщика». Поэтому этот алгоритм выбора можно назвать алгоритмом смещения (английское название – the bully algorithm; слово bully имеет значения: задира, забияка, хвастун, хулиган, первоклассный, великолепный).
Рис. 29. Пример выполнения алгоритма выбора «смещение»
На рис. 29 изображены четыре шага выполнения алгоритма. Алгоритм начинается с того, что сайт S1 обнаружил, что сайт SC не выполняет свои функции координатора. Тогда он объявляет выборы, посылая соответствующие сообщения на сайты S2 и S3 . Те посылают сайту S1 «ответы» (шаг 1) и начинают собственные выборы (шаг 2). На рисунке предполагается, что оценки est сайтов увеличиваются слева направо.
Сайт S3 посылает «ответ» сайту S2 , но сам дождаться ответа от SC не может, так как тот не функционирует. Поэтому S3 решает взять на себя функции координатора. Но ему не везет: он тоже выходит из строя (шаг 3), не успев послать сообщение «координатор».
Тем временем истекает период ожидания сайтом S1 окончания выборов. Сообщения «ответ» он получил, а сообщение «координатор» – нет. Тогда он начинает новые выборы, по окончании которых координатором (C) становится сайт S2 .
Во всех приведенных ниже алгоритмах процесс на сайте p имеет переменную state с возможными значениями coordinator (координатор) и lost (проигравший). Иногда мы будем предполагать, что state имеет значение sleep (спящий), когда p еще не выполнил ни одного шага алгоритма, и значение cand (кандидат), если p вступил в вычисление, но еще не знает, победил он или проиграл. Некоторые алгоритмы используют дополнительные состояния, такие как active, passive и др., которые будут указаны в самом алгоритме.
Важность уникальных идентификаторов в задаче выбора состоит в том, что они могут использоваться не только для адресации сообщений, но и для оценки сайтов. При разработке алгоритма выбора можно, например, потребовать, что сайт с наибольшей (или наоборот, с наименьшей) оценкой должен победить. Тогда задача состоит в поиске идентификатора с наибольшей оценкой с помощью децентрализованного алгоритма. В этом случае задачу выбора называют задачей поиска экстремума.