292
правки
Изменения
→Отличия от параллельных систем
[[Категория: Параллельное программирование]]
== Модель ==
Нас интересует взаимодействие между процессами, оно бывает ровно одного вида: посылки сообщений друг другу.
С точки зрения внешнего мира процесс считается однопоточным: все отправки/получения сообщений одним процессом линейно упорядочены.
Обычно каждый процесс может послать сообщение каждому, но иногда это ограничивается.
В реальном мире может быть такое, что кому-то отослать сообщение быстрее, чем другому.
В каждом процессе могут происходить '''события''', обычно обозначаются маленькими латинскими буквами: $a, b, c, d, \dots \in \mathbb E$.
Так что в алгоритмах нас интересует не время вычислений, а количество посланных сообщений, причём точное, а не просто асимптотика.
Отказ узлов или связи в распределённых системах — обычное дело, это '''основная сложность ''' разработки распределённых алгоритмов(в отличие от просто параллельных).До билетов про иерархию ошибок мы считаем, что ошибок нет (например, в алгоритмах взаимного исключения).
Из-за сети сообщения могут идти непонятно сколько времени (в том числе на практике).
В '''синхронных''' системах гарантируется, что каждое сообщение либо доходит за некоторое константное время $C$, либо теряется.
В '''асинхронных''' системах сообщения могут идти сколь угодно долго. До билетов про синхронные системы мы считаем всё асинхронным.На практике же везде ставят таймаут, превращая систему в синхронную. Дополнительные сложности возникает с порядком сообщений: как между процессами (отсутствует, FIFO), так и глобально во всей системе (отсутствует, casual ordering, synchronous ordering), глобально во всей системе с учётом multicast-broadcast (отсутствует, casual total order). == Задачи ===== Взаимное исключение === Почти как в [[Алгоритмы взаимного исключения|параллельных системах]]: {{Определение|definition=Критическая секция $CS_i$ — это пара из двух событий: $Enter(CS_i), Exit(CS_i) \in E$ (вход и выход из критической секции), при этом $Enter(CS_i) < Exit(CS_i)$ (в частности, они выполняются в одном процессе) и для всех $i$ верно: $Exit(CS_i) \to Enter(CS_{i+1})$ (т.е. критические секции линейно упорядочены).}} Это требование ''корректности'' — что алгоритм ''не может допустить''.Мы здесь нигде не пользовались словом "одновременно".Более того, нам даже не требуется вводить отдельные события входа/выхода, достаточно уже имеющихся событий отправки/получения сообщений (т.к. в системе ничего кроме сообщений принципиально происходить не может). Также можно вводить дополнительные требования прогресса (что алгоритм ''должен делать''), но мы это делаем неформально. Можно требовать (от более слабых к более строгим): # Если "сейчас" ни один процесс в критической секции не находится, но кто-то "хочет" в неё попасть, то хотя бы один процесс рано или поздно туда попадёт.# "Честность": если процесс хочет попасть в критическую секции, то он рано или поздно туда попадёт независимо от действий остальных (если они, конечно, секцию будут освобождать). === Запуск нескольких алгоритмов и перезапуск ===Некоторые алгоритмы в курсе алгоритмы "одноразовые" (например, достижение консенсуса или снятие согласованного среза).Чтобы запустить их несколько раз, на практике можно запустить несколько копий алгоритма и к каждому сообщению прикреплять номер копии.Тогда они будут работать независимо друг от друга и работать корректно, хотя нет никаких гарантий про то, как они будут соотноситься между собой (например, алгоритм, запущенный позже, может завершиться раньше). Также могут быть тонкости с "запуском" алгоритмов: например, [[алгоритм Чанди-Лампорта]] требует сохранять все отправленные с начала времён сообщения.
