Викиконспекты - Вклад участника [ru]

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

2012-01-08T23:25:05Z

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

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===2. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

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

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

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

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

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

*[[Глобальные свойства системы]]
*[[Слабый конъюнктивный предикат]]

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

Алгоритм Дейкстры и Шолтена в английской википедии<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref>.

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

*[[Локально стабильный предикат]]
*[[Согласованный интервал]]
*[[Барьерная синхронизация (3 алгоритма)]]

===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
Порядок сообщений:
# асинхронный
# FIFO (сообщения доходят получателю в том порядке, в котором они были ему отправлены)
# причинно-следственный (если одно сообщение было отправлено раньше другого, то оно будет доставлено раньше другого (в системе целиком)
# синхронный

===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
*[[Total order]]
*[[Алгоритм Лампорта]]
*[[Алгоритм Скрина]]

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

'''Алгоритм Чанди-Робертса''' (Chang and Roberts) выбора лидера <ref>http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm</ref>.

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

'''Алгоритм Хирчберга-Синклера''' <ref>http://en.wikipedia.org/wiki/HS_algorithm</ref> <ref>http://web.cs.gc.cuny.edu/~vmitsou/presentation.pdf слайды 16-18</ref>.

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

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

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

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

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

*Каждый узел посылает каждому свое число;
*Процессы запоминают пришедшие числа;
*Новые для себя числа процессы рассылают дальше;
*Каждый процесс выбирает минимально известное ему число.

(возможно, стоит дописать)

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

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

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

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

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

Данный вопрос достаточно хорошо описан в английской версии.

==Ссылки==
<references/>

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

2012-01-08T22:17:48Z

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

[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
==6 семестр==
===1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]

===2. Логические часы Лампорта и векторные часы, их свойства===
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
*[[Параллельное программирование: Векторные часы| Векторные часы]]

===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
*[[Параллельное программирование: Матричные часы|Матричные часы]]

===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]

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

*[[Задача обедающих философов]]
*[[Кворум]]
*[[Кворум простого большинства]]
*[[Кворум рушащейся стенки]]

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

*[[Срез, согласованный срез]]
*[[Алгоритм Чанди-Лампорта]]

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

*[[Глобальные свойства системы]]
*[[Слабый конъюнктивный предикат]]

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

Алгоритм Дейкстры и Шолтена в английской википедии<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref>.

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

*[[Локально стабильный предикат]]
*[[Согласованный интервал]]
*[[Барьерная синхронизация (3 алгоритма)]]

===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
Порядок сообщений:
# асинхронный
# FIFO (сообщения доходят получателю в том порядке, в котором они были ему отправлены)
# причинно-следственный (если одно сообщение было отправлено раньше другого, то оно будет доставлено раньше другого (в системе целиком)
# синхронный

===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
*[[Total order]]
*[[Алгоритм Лампорта]]
*[[Алгоритм Скрина]]

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

'''Алгоритм Чанди-Робертса''' (Chang and Roberts) выбора лидера <ref>http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm</ref>.

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

'''Алгоритм Хирчберга-Синклера''' <ref>http://en.wikipedia.org/wiki/HS_algorithm</ref> <ref>http://web.cs.gc.cuny.edu/~vmitsou/presentation.pdf слайды 16-18</ref>.

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

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

Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.

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

Пусть в системе имеется ''n'' узлов.
Пусть из них максимум ''f'' не работают.
Тогда можно решить задачу консенсуса:

*Каждый узел посылает каждому свое число;
*Процессы запоминают пришедшие числа;
*Новые для себя числа процессы рассылают дальше;
*Каждый процесс выбирает минимально известное ему число.

(возможно, стоит дописать)

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

'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)

Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].

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

'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)

Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?

Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.

*Каждый рассылает каждому свое число;
*Каждый рассылает каждому собранные значения;
*В полученных векторах каждый проводит голосование.

Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.

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

Данный вопрос достаточно хорошо описан в английской версии.

==Ссылки==
<references/>