Версия 17:08, 26 июня 2010

Содержание

1 Программирование параллельных и распределенных систем
- 1.1 6 семестр

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

6 семестр

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Данный вопрос достаточно хорошо описан в ^[4].

[1] ttp://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm

[2] ttp://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm

[3] ttp://en.wikipedia.org/wiki/HS_algorithm

[4] ttp://ru.wikipedia.org/wiki/Задача_византийских_генералов

[1]

[2]

[3]

[4]

@@ Строка 39: / Строка 39: @@
 ===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена===
+Алгоритм Дейксты и Шолтена в английской википедии<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref>.
 ===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
 ===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===

Параллельное программирование — различия между версиями