Параллельное программирование

Материал из Викиконспекты
Перейти к: навигация, поиск

Содержание

[править] Программирование параллельных и распределенных систем

[править] 6 семестр

[править] 1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью

[править] 2. Логические часы Лампорта и векторные часы, их свойства

[править] 3. Часы с прямой зависимостью (и их свойства) и матричные часы

[править] 4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы

[править] 5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)

[править] 6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя

[править] 7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы

[править] 8. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена

Алгоритм Дейкстры и Шолтена в английской википедии[1].

[править] 9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки

[править] 10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка

Порядок сообщений:

  1. асинхронный
  2. FIFO (сообщения доходят получателю в том порядке, в котором они были ему отправлены)
  3. причинно-следственный (если одно сообщение было отправлено раньше другого, то оно будет доставлено раньше другого (в системе целиком)
  4. синхронный

[править] 11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка

[править] 12. Общий порядок (total order). Алгоритмы Лампорта и Скина

[править] 13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера

Алгоритм Чанди-Робертса (Chang and Roberts) выбора лидера [2].

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

Алгоритм Хирчберга-Синклера [3] [4].

[править] 14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)

  1. Отказ узла
  2. Отказ связи
  3. Неустойчивая связь / пропуск пакетов
  4. Византийская ошибка (сломавшийся процесс может слать любой мусор)

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

Также решение - уйти от требования детерминированности алгоритма.

[править] 15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов

Пусть в системе имеется n узлов. Пусть из них максимум f не работают. Тогда можно решить задачу консенсуса:

  • Каждый узел посылает каждому свое число;
  • Процессы запоминают пришедшие числа;
  • Новые для себя числа процессы рассылают дальше;
  • Каждый процесс выбирает минимально известное ему число.

(возможно, стоит дописать)

[править] 16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации

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

Два процесса в случае ненадежного канала не могут достичь консенсуса.

Consider the last such message that was successfully delivered. If that last message had not been successfully delivered, then one general at least (presumably the receiver) would decide not to attack. From the viewpoint of the sender of that last message, however, the sequence of messages sent and delivered is exactly the same as it would have been, had that message been delivered.

Для недетерминнированного - аналогично. Посмотрим на "успешную" последовательность. И отменим успешность последнего сообщения. Для 1-ого все ок, для 2-ого все испортилось.

[править] 17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы

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

Проблема византийских генералов формулируется так: имеется n генералов из которых f являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при n > 3f задача решаема, а иначе нет.

  • Каждый рассылает каждому свое число;
  • Каждый рассылает каждому собранные значения;
  • В полученных векторах каждый проводит голосование.

Можно доказать, например, что при n = 3, f = 1 консенсус невозможен.

[править] 18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1

Данный вопрос достаточно хорошо описан в английской версии.

[править] Ссылки

  1. http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm
  2. http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm
  3. http://en.wikipedia.org/wiki/HS_algorithm
  4. http://web.cs.gc.cuny.edu/~vmitsou/presentation.pdf слайды 16-18
Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты