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

редактировать

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

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

Содержание

  • 1 Стандартные проблемы
  • 2 Ссылки
  • 3 Дополнительная литература
  • 4 Внешние ссылки

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

Атомарная фиксация
Атомарная фиксация - это операция, в которой набор отдельных изменений применяется как одна операция. Если атомарная фиксация прошла успешно, это означает, что все изменения были применены. Если происходит сбой до того, как атомарная фиксация может быть завершена, «фиксация» прерывается и никакие изменения применяться не будут.
Алгоритмы для решения протокола атомарной фиксации включают протокол двухфазной фиксации и протокол трехфазной фиксации.
Консенсус
Алгоритмы консенсуса пытаются решить проблему нескольких процессов, согласовывающих общее решение.
Точнее, протокол консенсуса должен удовлетворяют четырем формальным свойствам, указанным ниже.
  • Завершение : каждый правильный процесс определяет какое-то значение.
  • Срок действия : если все процессы предлагают одно и то же значение v {\ displaystyle v}v , то каждый правильный процесс решает v {\ displaystyle v}v .
  • Integrity : каждый правильный процесс определяет не более одного значения, и если он определяет какое-то значение, v {\ displaystyle v}v , тогда v {\ displaystyle v}v должно быть предложено каким-то процессом.
  • Соглашение : если правильный процесс решает v {\ displaystyle v}v , затем каждая правильная процедура ess решает v {\ displaystyle v}v .
Распространенными алгоритмами для достижения консенсуса являются алгоритм Paxos и алгоритм Raft.
Распределенный поиск
Выбор лидера
Leader Выборы - это процесс назначения единственного процесса организатором некоторой задачи, распределенной между несколькими компьютерами (узлами). Перед тем, как задача будет запущена, все сетевые узлы не знают, какой узел будет служить «лидером» или координатором задачи. Однако после запуска алгоритма выбора лидера каждый узел в сети распознает конкретный уникальный узел в качестве лидера задачи.
Взаимное исключение
Неблокирующие структуры данных
Надежная широковещательная передача
Надежная широковещательная передача примитив коммуникации в распределенных системах. Надежная широковещательная рассылка определяется следующими свойствами:
  • Срок действия - если правильный процесс отправляет сообщение, то какой-то правильный процесс в конечном итоге доставит это сообщение
  • Соглашение - если правильный процесс доставляет сообщение, то все правильные процессы в конечном итоге доставляют это сообщение
  • Целостность - каждый правильный процесс доставляет одно и то же сообщение не более одного раза и только в том случае, если это сообщение было отправлено процессом
Надежная широковещательная передача может иметь последовательную, причинную или общий порядок.
Репликация
Распределение ресурсов
Связующее дерево поколение
Нарушение симметрии, например раскраска вершин

Ссылки

Дополнительная литература

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

Последняя правка сделана 2021-05-17 09:15:47
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте