Параллельное программирование
Программирование параллельных и распределенных систем
6 семестр
1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью
2. Логические часы Лампорта и векторные часы, их свойства
3. Часы с прямой зависимостью (и их свойства) и матричные часы
4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы
5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)
6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя
7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы
8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена
Алгоритм Дейксты и Шолтена в английской википедии[1].
9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки
10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка
Порядок сообщений:
- асинхронный
- FIFO (сообщения доходят получателю в том порядке, в котором они были ему отправлены)
- причинно-следственный (если одно сообщение было отправлено раньше другого, то оно будет доставлено раньше другого (в системе целиком)
- синхронный
11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка
12. Общий порядок (total order). Алгоритмы Лампорта и Скина
13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера
Алгоритм Чанди-Робертса (Chang and Roberts) выбора лидера [2].
Пусть процессы находятся в кольце. Посылаем свой номер налево по кольцу. При получении номера справа посылаем налево максимум из своего номера и полученного справа. Если полученный справа номер является нашим номером, то заканчиваем работу.
Алгоритм Хирчберга-Синклера [3] [4].
14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)
- Отказ узла
- Отказ связи
- Неустойчивая связь / пропуск пакетов
- Византийская ошибка (сломавшийся процесс может слать любой мусор)
Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.
15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов
Пусть в системе имеется n узлов. Пусть из них максимум f не работают. Тогда можно решить задачу консенсуса:
- Каждый узел посылает каждому свое число;
- Процессы запоминают пришедшие числа;
- Новые для себя числа процессы рассылают дальше;
- Каждый процесс выбирает минимально известное ему число.
(возможно, стоит дописать)
16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации
Задача двух генералов — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)
Два процесса в случае ненадежного канала не могут достичь консенсуса.
17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы
Задача византийских генералов — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)
Проблема византийских генералов формулируется так: имеется n генералов из которых f являются предателями. Как прийти к консенсусу честным генералам?
Известно, что при n > 3f задача решаема, а иначе нет.
- Каждый рассылает каждому свое число;
- Каждый рассылает каждому собранные значения;
- В полученных векторах каждый проводит голосование.
Можно доказать, например, что при n = 3, f = 1 консенсус невозможен.
18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1
Данный вопрос достаточно хорошо описан в [5].
