Распределенный алгоритм - Distributed algorithm

А распределенный алгоритм является алгоритм предназначен для работы на компьютерное железо построен из соединенных между собой процессоры. Распределенные алгоритмы используются во многих различных областях применения распределенных вычислений, Такие как телекоммуникации, научные вычисления, распространяется обработка информации, и в реальном времени контроль над процессом. Стандартные задачи, решаемые распределенными алгоритмами, включают: выборы лидера, консенсус, распространяется поиск, остовное дерево поколение, взаимное исключение, и распределение ресурсов.^[1]

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

Стандартные задачи

Атомарная фиксация

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

Алгоритмы решения протокола атомарной фиксации включают: протокол двухфазной фиксации и протокол трехфазной фиксации.

Консенсус

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

Точнее, протокол консенсуса должен удовлетворять четырем формальным свойствам, указанным ниже.

• Прекращение: каждый правильный процесс определяет какую-то ценность.
• Период действия: если все процессы предлагают одно и то же значение ${ displaystyle v}$, то каждый правильный процесс решает ${ displaystyle v}$.
• Честность: каждый правильный процесс определяет не более одного значения, и если он определяет какое-то значение ${ displaystyle v}$, тогда ${ displaystyle v}$ должно быть было предложено каким-то процессом.
• Соглашение: если правильный процесс решит ${ displaystyle v}$, то каждый правильный процесс решает ${ displaystyle v}$.

Общие алгоритмы достижения консенсуса - это Алгоритм Паксоса и Алгоритм Raft.

Распределенный поиск

Выборы лидера

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

Взаимное исключение

Неблокирующие структуры данных

Надежная трансляция

Надежная трансляция - это коммуникационный примитив в распределенных системах. Надежная трансляция определяется следующими свойствами:

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

Надежная трансляция может иметь последовательный, причинный или полный порядок.

Репликация

Распределение ресурсов

Остовное дерево поколение

Нарушение симметрии, например раскраска вершин

Рекомендации

дальнейшее чтение

• Кристиан Качин; Рашид Геррауи; Луис Родригес (2011), Введение в надежное и безопасное распределенное программирование (2-е изд.), Springer, ISBN  978-3-642-15259-7
• К. Родригес, М. Вильягра и Б. Баран, Асинхронные командные алгоритмы для логической выполнимости, Bionetics2007, стр. 66–69, 2007.

внешняя ссылка

• СМИ, связанные с Распределенные алгоритмы в Wikimedia Commons
• MIT Open Courseware - Распределенные алгоритмы