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

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

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

Стандартные проблемы

Атомарный коммит

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

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

Консенсус

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

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

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

Распространенными алгоритмами для решения консенсуса являются алгоритм Paxos и алгоритм Raft .

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

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

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

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

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

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

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

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

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

Репликация

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

Генерация связующего дерева

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

Ссылки

1. Lynch, Nancy (1996). Распределенные алгоритмы . Сан-Франциско, Калифорния: Morgan Kaufmann Publishers . ISBN 978-1-55860-348-6.

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

• Кристиан Кашен; Рашид Геррауи; Луис Родригес (2011), Введение в надежное и безопасное распределенное программирование (2-е изд.), Springer, Bibcode : 2011itra.book.....C, ISBN 978-3-642-15259-7
• C. Rodríguez, M. Villagra и B. Barán, Асинхронные командные алгоритмы для булевой выполнимости, Bionetics2007, стр. 66–69, 2007.

Внешние ссылки

• Медиафайлы по теме Распределенные алгоритмы на Wikimedia Commons
• MIT Open Courseware - Распределенные алгоритмы