Алгоритм смещения

Алгоритм предназначен для динамического выбора координатора на основе локальных оценок сайтов. Предполагается, что каналы связи надежны, а сайты иногда могут прерывать (например, из-за отказов) свое функционирование.

Сайты обмениваются сообщениями с тремя возможными значениями: «выборы», «ответ», «координатор». Сообщение «выборы» посылается для объявления выборов. Сообщение «ответ» посылается в ответ на объявление выборов. Сообщение «координатор» посылается для объявления идентификатора нового координатора.

Алгоритм выборов может начать любой сайт S_i, который определил, что текущий координатор S_C не функционирует (например, если ему слишком долго приходится ожидать сообщения от координатора).

Алгоритм состоит из следующих шагов.

1. Сайт S_i рассылает сообщение «выборы» всем другим сайтам, имеющим большую оценку est (S_j), чем у него. Он ожидает, что они отправят ему сообщения «ответ».

2. Ожидание сайтом S_i ответов длится не более чем время T. Если за это время ответы не получены, то сайт S_i объявляет себя координатором и уведомляет об этом сайты с меньшей оценкой, чем est (S_i) путем отправки им сообщений «координатор». Если же ответы получены, то сайт S_i ожидает еще некоторое ограниченное время прихода сообщения «координатор» (возможно, кто-то из «старших» товарищей возьмет на себя функции координатора). Если он не дождался сообщения «координатор», сайт S_i начинает новые выборы.

3. Если сайт S_i получает сообщение «координатор», то он записывает идентификатор сайта, с которого это сообщение было получено, и в дальнейшем общается с этим сайтом как с координатором.

4. Если сайт S_j получает сообщение «выборы» и намерен участвовать в выборах, то он возвращает сообщение «ответ», после чего начинает новые выборы (напомним, его оценка est (S_j) больше, чем оценка est (S_i) сайта, проводящего сейчас выборы).

5. Если происходит рестарт сайта S_C, то он начинает выборы. В том случае, если его оценка est (S_C) является наивысшей, он объявляет себя координатором и сообщает об этом другим сайтам. Это происходит, несмотря на то, что какой-то сайт в период неработоспособности S_C выиграл выборы и функционирует сейчас как координатор. Происходит смещение «временщика». Поэтому этот алгоритм выбора можно назвать алгоритмом смещения (английское название – the bully algorithm; слово bully имеет значения: задира, забияка, хвастун, хулиган, первоклассный, великолепный).

Рис. 29. Пример выполнения алгоритма выбора «смещение»

На рис. 29 изображены четыре шага выполнения алгоритма. Алгоритм начинается с того, что сайт S ₁ обнаружил, что сайт S_C не выполняет свои функции координатора. Тогда он объявляет выборы, посылая соответствующие сообщения на сайты S ₂ и S ₃. Те посылают сайту S ₁ «ответы» (шаг 1) и начинают собственные выборы (шаг 2). На рисунке предполагается, что оценки est сайтов увеличиваются слева направо.

Сайт S ₃ посылает «ответ» сайту S ₂, но сам дождаться ответа от S_C не может, так как тот не функционирует. Поэтому S ₃ решает взять на себя функции координатора. Но ему не везет: он тоже выходит из строя (шаг 3), не успев послать сообщение «координатор».

Тем временем истекает период ожидания сайтом S ₁ окончания выборов. Сообщения «ответ» он получил, а сообщение «координатор» – нет. Тогда он начинает новые выборы, по окончании которых координатором (C) становится сайт S ₂.

Во всех приведенных ниже алгоритмах процесс на сайте p имеет переменную state с возможными значениями coordinator (координатор) и lost (проигравший). Иногда мы будем предполагать, что state имеет значение sleep (спящий), когда p еще не выполнил ни одного шага алгоритма, и значение cand (кандидат), если p вступил в вычисление, но еще не знает, победил он или проиграл. Некоторые алгоритмы используют дополнительные состояния, такие как active, passive и др., которые будут указаны в самом алгоритме.

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