Алгоритм выборов и распределенная обработка

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

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

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

У нас есть два алгоритма выбора для двух разных конфигураций распределенной системы.

1. Алгоритм хулигана -
Этот алгоритм применяется к системе, где каждый процесс может отправлять сообщение любому другому процессу в системе.

Алгоритм. Предположим, что процесс P отправляет сообщение координатору.

1. Если координатор не отвечает на него в течение интервала времени T, то предполагается, что координатор вышел из строя.
2. Теперь процесс P отправляет сообщение о выборах каждому процессу с номером с высоким приоритетом.
3. Он ждет ответов, если никто не отвечает в течение интервала времени T, тогда процесс P выбирает себя координатором.
4. Затем он отправляет сообщение всем процессам с более низким приоритетом, что он выбран в качестве их нового координатора.
5. Однако, если ответ получен в течение времени T от любого другого процесса Q,
   • (I) Процесс P снова ожидает в течение интервала времени T ', чтобы получить еще одно сообщение от Q о том, что он был выбран в качестве координатора.
   • (II) Если Q не отвечает в течение интервала времени T ', считается, что произошел сбой, и алгоритм перезапускается.

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

Алгоритм -

1. Если процесс P1 обнаруживает сбой координатора, он создает новый активный список, который изначально пуст. Он отправляет сообщение о выборах своему соседу справа и добавляет номер 1 в свой активный список.
2. Если процесс P2 получает сообщение о выборе от процессов слева, он отвечает тремя способами:
   • (I) Если полученное сообщение не содержит 1 в активном списке, то P1 добавляет 2 в свой активный список и пересылает сообщение.
   • (II) Если это первое полученное или отправленное сообщение о выборах, P1 создает новый активный список с номерами 1 и 2. Затем он отправляет сообщение о выборах 1, за которым следует 2.
   • (III) Если процесс P1 получает собственное сообщение выбора 1, то активный список для P1 теперь содержит номера всех активных процессов в системе. Теперь процесс P1 определяет номер с наивысшим приоритетом из списка и выбирает его в качестве нового координатора.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.