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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство))
(→‎3. Часы с прямой зависимостью (и их свойства) и матричные часы)
Строка 10: Строка 10:
  
 
===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
 
===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
 +
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
 +
*[[Параллельное программирование: Матричные часы|Матричные часы]]
 +
 
===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
 
===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
 
===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===
 
===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===

Версия 14:37, 26 июня 2010

Содержание

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

1 билет

2 билет

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Параллельное_программирование&oldid=1813»