Параллельное программирование — различия между версиями
(→2 билет) |
Ulyantsev (обсуждение | вклад) (→Программирование параллельных и распределенных систем) |
||
| Строка 8: | Строка 8: | ||
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]] | *[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]] | ||
*[[Параллельное программирование: Векторные часы| Векторные часы]] | *[[Параллельное программирование: Векторные часы| Векторные часы]] | ||
| + | |||
| + | ===3. Часы с прямой зависимостью (и их свойства) и матричные часы=== | ||
| + | ===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы=== | ||
| + | ===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)=== | ||
| + | ===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя=== | ||
| + | ===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы=== | ||
| + | ===8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена=== | ||
| + | ===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки=== | ||
| + | ===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка=== | ||
| + | ===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка=== | ||
| + | ===12. Общий порядок (total order). Алгоритмы Лампорта и Скина=== | ||
| + | ===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера=== | ||
| + | ===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)=== | ||
| + | ===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов=== | ||
| + | ===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации=== | ||
| + | ===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы=== | ||
| + | ===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1=== | ||
Версия 14:14, 26 июня 2010
Содержание
- 1 Программирование параллельных и распределенных систем
- 1.1 1 билет
- 1.2 2 билет
- 1.3 3. Часы с прямой зависимостью (и их свойства) и матричные часы
- 1.4 4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы
- 1.5 5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)
- 1.6 6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя
- 1.7 7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы
- 1.8 8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена
- 1.9 9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки
- 1.10 10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка
- 1.11 11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка
- 1.12 12. Общий порядок (total order). Алгоритмы Лампорта и Скина
- 1.13 13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера
- 1.14 14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)
- 1.15 15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов
- 1.16 16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации
- 1.17 17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы
- 1.18 18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1
