Произошло до

редактировать

В информатике отношение произошло до (обозначается: $→ {\ displaystyle \ to \;}$ $\ to \;$ ) - это отношение между результатом двух событий, такое, что если одно событие должно произойти раньше другого, результат должен отражать это, даже если эти события на самом деле выполняются не по порядку (обычно для оптимизации выполнения программы). Это включает упорядочивание событий на основе потенциальной причинной связи пар событий в параллельной системе, особенно в асинхронных распределенных системах. Его сформулировал Лесли Лэмпорт. В частности, в Java связь происходит до - это гарантия того, что память, записанная оператором A, будет видна оператору B, то есть этот оператор A завершит свою запись до того, как оператор B начнет чтение. [1]

Отношение "произошло до" формально определяется как наименьший строгий частичный порядок для таких событий, что:

Если события $a {\ displaystyle a \;}$ $a \;$ и $b {\ displaystyle b \;}$ $b \;$ происходят в одном процессе, $a → b {\ displaystyle a \ to b \;}$ $a \ в b \;$ , если возникновение события $a {\ displaystyle a \;}$ $a \;$ предшествовало возникновению события $b {\ displaystyle b \;}$ $b \;$ .
Если событие $a {\ displaystyle a \;}$ $a \;$ - это отправка сообщения, а событие $b {\ displaystyle b \;}$ $b \;$ - получение сообщения, отправленного в событии $a {\ displaystyle a \;}$ $a \;$ , $a → b {\ displaystyle a \ to b \;}$ $a \ в b \;$ .

Если есть другие причинно-следственные связи между событиями в данной системе, например, между созданием процесса и его первым событием, эти относиться Корабли также добавлены к определению.

Как и все строгие частичные порядки, отношение «произошло до» является транзитивным, иррефлексивным и антисимметричным, то есть:

$∀ a, b, c {\ displaystyle \ forall a, b, c}$ $\ forall a, b, c$ , если $a → b {\ displaystyle a \ to b \;}$ $a \ в b \;$ и $b → с {\ displaystyle b \ to c \;}$ $b \ to c \;$ , затем $a → c {\ displaystyle a \ to c \;}$ $a \ to c \;$ (транзитивность). Это означает, что для любых трех событий $a, b, c {\ displaystyle a, b, c}$ $a, b, c$ , если $a {\ displaystyle a}$ $a$ произошло до $b {\ displaystyle b}$ $b$ и $b {\ displaystyle b}$ $b$ произошло до $c {\ displaystyle c}$ $c$ , затем $a {\ displaystyle a}$ $a$ должно было произойти до $c {\ displaystyle c}$ $c$ .
$∀ a, a ↛ a {\ displaystyle \ forall a, a \ nrightarrow a}$ $\ forall a, a \ nrightarrow a$ (невозмутимость). Это означает, что никакое событие не может произойти до самого себя.
$∀ a, b, {\ displaystyle \ forall a, b,}$ $\ forall a, b,$ где $a ≠ b {\ displaystyle a \ neq b}$ $a \ neq b$ , если $a → b {\ displaystyle a \ to b}$ $a \ to b$ , то $b ↛ a {\ displaystyle b \ nrightarrow a}$ $b \ nrightarrow a$ (антисимметрия). Это означает, что для любых двух различных событий $a, b {\ displaystyle a, b}$ $a, b$ , если $a {\ displaystyle a}$ $a$ произошло до $b {\ displaystyle b}$ $b$ , тогда $b {\ displaystyle b}$ $b$ не могло произойти до $a {\ displaystyle a}$ $a$ .

Процессы, составляющие распределенный Система не знает отношения «произошло до», если не использует логические часы, такие как часы Лампорта или векторные часы. Это позволяет разрабатывать алгоритмы для взаимного исключения и такие задачи, как отладка или оптимизация распределенных систем.

См. Также

Ссылки

^Лэмпорт, Лесли (1978). «Время, часы и порядок событий в распределенной системе», Сообщения ACM, 21 (7), 558-565.