# happens-before関係 ## 定義 happens-before 関係(→)は、分散システムのイベント集合上で、物理時間を使わずに「先に起きた」を定義する非反射的な半順序である。同一プロセス内の順序、メッセージの送信から受信への順序、およびそれらの推移閉包の最小の関係として定まる。→ で結ばれない 2 つのイベントは並行であり、互いに因果的に影響できない。 ## 主な特徴 - 半順序であり、分散システムでは 2 つのイベントのどちらが先かを言えないことがある。 - 物理クロックを必要としない。仕様はシステム内で観測できるイベントだけで書く。 - 一意に決まるのはこの半順序だけである。論理クロックによる全順序はこれを拡張したもので、一意ではない。 - 実際に送られたメッセージだけを考える。特殊相対論の時空図の順序に似るが、送りうるメッセージは考えない。 ## 横断的知見 (初出 ingest のため、複数ソースの突き合わせによる知見はまだない。) ## 未解決の問い - システム外の前後関係(電話など)を含む拡張関係 ⇝ をどう取り込むか。 ## 関連 - 概念: [[半順序]] / [[ID生成器と論理クロック]] / [[クロック同期と信頼性]] - source: [[@1978__CACM__Time Clocks and the Ordering of Events in a Distributed System]] ## 出典 - [[@1978__CACM__Time Clocks and the Ordering of Events in a Distributed System]](「The Partial Ordering」節による定義)