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

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

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

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

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

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

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

Консенсус

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

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

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

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

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

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

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

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

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

Надежное вещание

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

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

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

Репликация

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

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

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

Ссылки

^ Перейти обратно: ^а ^б Линч, Нэнси (1996). Распределенные алгоритмы . Сан-Франциско, Калифорния: Издательство Morgan Kaufmann . ISBN 978-1-55860-348-6 .

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

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

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

СМИ, связанные с распределенными алгоритмами, на Викискладе?
Открытые курсы MIT — Распределенные алгоритмы

[lynch1997-1] Перейти обратно: ^а ^б Линч, Нэнси (1996). Распределенные алгоритмы . Сан-Франциско, Калифорния: Издательство Morgan Kaufmann . ISBN 978-1-55860-348-6 .

[1]