Happened-before

В інформатиці, відношення відношення happened-before (англ. happened-before — «сталося раніше») (позначається: $\to \;$ ) - це відношення між результатом двох подій, таким чином, що якщо одна подія повинна відбутися до іншої події, результат повинен відображати це, навіть якщо ці події насправді виконуються поза порядком (як правило, для оптимізації потоку програми). Це включає впорядкування подій на основі потенційного причинно-наслідкового зв’язку пар подій у паралельній системі, особливо асинхронних розподілених систем . Його сформулював Леслі Лампорт . Спеціально для Java відносини " раніше" - це гарантія того, що пам'ять, записана в оператор A, є видимою для оператора B, тобто те, що A завершує його запис до того, як твердження B розпочне його читання. [1] [Архівовано 6 січня 2020 у Wayback Machine.]

Ставлення happened-before формально визначається як найменш суворий частковий порядок подій:

• Якщо події $a\;$ і $b\;$ відбуваються в одному і тому ж процесі, $a\to b\;$ якщо поява події $a\;$ передує виникнення події $b\;$.
• Якщо подія $a\;$ це відправлення повідомлень та подія $b\;$ - це прийом повідомлень, відправлених у разі $a\;$, $a\to b\;$.

Якщо між подіями в даній системі існують інші причинно-наслідкові зв’язки, наприклад, між створенням процесу та його першою подією, ці зв'язки також додаються до визначення.

Як і всі суворі часткові порядки, відносини, що відбулися раніше, є транзитивними, нерефлексивними та антисиметричними, тобто:

• $\forall a,b,c$, якщо $a\to b\;$ і $b\to c\;$, потім $a\to c\;$ (транзитивність). Це означає, що для будь-яких трьох подій $a,b,c$, якщо $a$ сталося раніше $b$, і $b$ сталося раніше $c$, потім $a$ повинно відбуватися раніше $c$ .
• $\forall a,a\nrightarrow a$ (нерефлексивність). Це означає, що жодна подія не може відбутися перед собою.
• $\forall a,b,$ де $a\neq b$, якщо $a\to b$ потім $b\nrightarrow a$ (антисиметрія). Це означає, що для будь-яких двох різних подій $a,b$, якщо $a$ сталося раніше $b$ потім $b$ не могло статися раніше $a$ .

Процеси, що складають розподілену систему, не знають відношення, що сталося раніше, якщо вони не використовують логічний годинник, наприклад, годинник Лампорт або векторний годинник . Це дозволяє розробляти алгоритми взаємного виключення та такі завдання, як налагодження чи оптимізація розподілених систем.