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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast[править]

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

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

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

27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора.[править]

28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.[править]

30 билет. Raft. Алгоритм, его свойства.[править]

31 билет. Транзакции в распределенных системах. 2 Phase Locking[править]

32 билет. Транзакции в распределенных системах. 2 Phase Commit.[править]

33 билет. СAP теорема (концепции, подходы, без доказательства)[править]

34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)[править]

35 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева[править]

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