292
правки
Изменения
Новая страница: «== Модель == Имеется несколько независимых '''процессов''', обычно обозначаются большими ла…»
== Модель ==
Имеется несколько независимых '''процессов''', обычно обозначаются большими латинскими буквами: $P, Q, R, \dots \in \mathbb P$.
Происходящее внутри процесса нас не интересует: там может быть сложная многопоточная система или простой цикл; может быть детерминированным, а может кидать монетку.
Процессы могут посылать друг другу '''сообщения''', обычно обозначаются $m \in \mathbb M$ (с индексами).
Нас интересует взаимодействие между процессами, оно бывает ровно одного вида: посылки сообщений друг другу.
С точки зрения внешнего мира процесс считается однопоточным: все отправки/получения сообщений одним процессом линейно упорядочены.
В каждом процессе могут происходить '''события''', обычно обозначаются маленькими латинскими буквами: $a, b, c, d, \dots \in \mathbb E$.
Можно узнать процесс, в котором произошло событие: $proc(e) \in \mathbb P$ (такая нотация встречается редко).
Если $e$ и $f$ произошли в одном процессе, то одно из двух произошло первым, обозначается $e < f$.
Каждому сообщению соответствуют ровно два события: отправка сообщения $snd(m) \in \mathbb E$ и его получение $rcv(m) \in \mathbb E$.
Другие события нас не интересуют.
=== Happens-before (произошло-до) ===
Транзитивное замыкание:
* Если $e < f$, то $e \to f$
* Для любого сообщения $m$: $snd(m) \to rcv(m)$
События $a$ и $c$, не связанные отношением произошло-до, называются '''параллельными'''.
"Времени" или "глобального времени" в распределённых системах '''не существует'''. Следствие: слова "одновременно" и "текущий момент" запрещены, если только не подкрепляются определением на основе "произошло-до". Можно почитать [https://queue.acm.org/detail.cfm?id=2745385 Justin Sheehy. 2015. There is No Now. Queue 13, 3, Pages 20 (March 2015), 8 pages. DOI: https://doi.org/10.1145/2742694.2745385]
=== Отличия от параллельных систем ===
Самая дорогая и длительная операция в распределённых системах обычно не вычисления, а посылка сообщения, потому что это включает в себя сеть (задержки между континентами порядка сотен миллисекунд).
Так что в алгоритмах нас интересует не время вычислений, а количество посланных сообщений, причём точное, а не просто асимптотика.
Отказ узлов или связи в распределённых системах — обычное дело, это основная сложность разработки распределённых алгоритмов.
Из-за сети сообщения могут идти непонятно сколько времени (в том числе на практике).
В '''синхронных''' системах гарантируется, что каждое сообщение либо доходит за некоторое константное время $C$, либо теряется.
В '''асинхронных''' системах сообщения могут идти сколь угодно долго.
Дополнительные сложности возникает с порядком сообщений: как между процессами, так и глобально во всей системе.
Имеется несколько независимых '''процессов''', обычно обозначаются большими латинскими буквами: $P, Q, R, \dots \in \mathbb P$.
Происходящее внутри процесса нас не интересует: там может быть сложная многопоточная система или простой цикл; может быть детерминированным, а может кидать монетку.
Процессы могут посылать друг другу '''сообщения''', обычно обозначаются $m \in \mathbb M$ (с индексами).
Нас интересует взаимодействие между процессами, оно бывает ровно одного вида: посылки сообщений друг другу.
С точки зрения внешнего мира процесс считается однопоточным: все отправки/получения сообщений одним процессом линейно упорядочены.
В каждом процессе могут происходить '''события''', обычно обозначаются маленькими латинскими буквами: $a, b, c, d, \dots \in \mathbb E$.
Можно узнать процесс, в котором произошло событие: $proc(e) \in \mathbb P$ (такая нотация встречается редко).
Если $e$ и $f$ произошли в одном процессе, то одно из двух произошло первым, обозначается $e < f$.
Каждому сообщению соответствуют ровно два события: отправка сообщения $snd(m) \in \mathbb E$ и его получение $rcv(m) \in \mathbb E$.
Другие события нас не интересуют.
=== Happens-before (произошло-до) ===
Транзитивное замыкание:
* Если $e < f$, то $e \to f$
* Для любого сообщения $m$: $snd(m) \to rcv(m)$
События $a$ и $c$, не связанные отношением произошло-до, называются '''параллельными'''.
"Времени" или "глобального времени" в распределённых системах '''не существует'''. Следствие: слова "одновременно" и "текущий момент" запрещены, если только не подкрепляются определением на основе "произошло-до". Можно почитать [https://queue.acm.org/detail.cfm?id=2745385 Justin Sheehy. 2015. There is No Now. Queue 13, 3, Pages 20 (March 2015), 8 pages. DOI: https://doi.org/10.1145/2742694.2745385]
=== Отличия от параллельных систем ===
Самая дорогая и длительная операция в распределённых системах обычно не вычисления, а посылка сообщения, потому что это включает в себя сеть (задержки между континентами порядка сотен миллисекунд).
Так что в алгоритмах нас интересует не время вычислений, а количество посланных сообщений, причём точное, а не просто асимптотика.
Отказ узлов или связи в распределённых системах — обычное дело, это основная сложность разработки распределённых алгоритмов.
Из-за сети сообщения могут идти непонятно сколько времени (в том числе на практике).
В '''синхронных''' системах гарантируется, что каждое сообщение либо доходит за некоторое константное время $C$, либо теряется.
В '''асинхронных''' системах сообщения могут идти сколь угодно долго.
Дополнительные сложности возникает с порядком сообщений: как между процессами, так и глобально во всей системе.
