以前に起こったこと

コンピュータサイエンスにおいて、事前発生 関係（表記：）は、2つのイベントの結果の関係であり、あるイベントが別のイベントの前に発生する場合、それらのイベントが実際には順序どおりに実行されなかったとしても（通常はプログラムフローを最適化するため）、結果はそれを反映する必要があります。これは、並行システム、特に非同期分散システムにおけるイベントのペアの潜在的な因果関係に基づいてイベントを順序付けすることを伴います。これは、レスリー・ランポートによって定式化されました。^[1]${\displaystyle \to \;}$

以前に起こった関係は、次のようなイベントの 最も厳密でない半順序として正式に定義されます。

• イベントと が同じプロセスで発生する場合、イベント の発生がイベント の発生に先行していた場合。${\displaystyle a\;}$${\displaystyle b\;}$${\displaystyle a\to b\;}$${\displaystyle a\;}$${\displaystyle b\;}$
• イベントがメッセージの送信であり、イベントがイベントで送信されたメッセージの受信である場合、。${\displaystyle a\;}$${\displaystyle b\;}$${\displaystyle a\;}$${\displaystyle a\to b\;}$

2つのイベントが異なる独立したプロセス（直接またはサードパーティのプロセスを介して間接的にメッセージを交換しない）で発生した場合、2つのプロセスは同時実行されていると言われますが、これはどちらも真実ではありません。^[2]${\displaystyle a\to b}$${\displaystyle b\to a}$

プロセスの作成とその最初のイベントの間など、特定のシステム内のイベント間に他の因果関係がある場合、これらの関係も定義に追加されます。たとえば、Java、^[3] C、C++、Rustなどの一部のプログラミング言語では、ステートメントAによって書き込まれたメモリがステートメントBから参照可能である場合、つまり、ステートメントBが読み取りを開始する前にステートメントAが書き込みを完了する場合に、事前発生エッジが存在します。

すべての厳密な半順序と同様に、happen-before 関係は推移的、非反射的(そして空虚に非対称的) です。つまり、

• ${\displaystyle \forall a,b,c}$かつ ならば、である(推移性)。つまり、任意の 3 つのイベントについて、が の前に起こり、 がの前に起こった場合、 は の前に起こっていたに違いありません。${\displaystyle a\to b\;}$${\displaystyle b\to c\;}$${\displaystyle a\to c\;}$${\displaystyle a,b,c}$${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$${\displaystyle c}$${\displaystyle a}$${\displaystyle c}$
• ${\displaystyle \forall a,a\nrightarrow a}$(非反射性) これは、いかなるイベントもそれ自身より前には発生しないことを意味します。
• ${\displaystyle \forall a,b,}$ならば（非対称性）。これは、任意の2 つのイベントについて、 がより前に起こった場合、 はより前に起こることはできないことを意味します。${\displaystyle a\to b}$${\displaystyle b\nrightarrow a}$${\displaystyle a,b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$${\displaystyle a}$

非対称性の性質は、前述の性質から直接導かれることに注目しましょう。つまり、矛盾により、およびが存在すると仮定します。すると、推移性により、次のようになりますが、これは非反射性と矛盾します。 ${\displaystyle \forall a,b,}$${\displaystyle a\to b\;}$${\displaystyle b\to a}$${\displaystyle a\to a,}$

分散システムを構成するプロセスは、Lamport クロックやベクトル クロックなどの論理クロックを使用しない限り、以前に起こったことの関係を認識しません。これにより、相互排他性のためのアルゴリズムや、分散システムのデバッグや最適化などのタスク を設計できます。

• 競合状態
• Java メモリ モデル
• ランポートタイムスタンプ
• 論理クロック

• Goetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer , Joseph; Holmes, David; Lea, Doug (2006)。Java Concurrency in Practice。Addison Wesley。ISBN 0-321-34960-1。