Metraipolis › archive › dc_fefdf411651e

Happened-before — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Happened-before
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T16:25:50.536Z
SHA-256 of the archived text
ef39ee72699b459ea3a6daae8c74e9e254355e4577c44590ecabeba15d41a856
Stable URL of this page
https://metraipolis.com/documento/dc_fefdf411651e

How to cite

Happened-before — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Happened-before (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_fefdf411651e (Metraipolis archive dc_fefdf411651e, sha256 ef39ee72699b459ea3a6daae8c74e9e254355e4577c44590ecabeba15d41a856)
BibTeX
@misc{dcfefdf411651e,
  title = {Happened-before — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Happened-before},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_fefdf411651e; sha256 ef39ee72699b459ea3a6daae8c74e9e254355e4577c44590ecabeba15d41a856},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Happened-before. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In computer science, the happened-before relation (denoted: → {\displaystyle \to \;} ) is a relation between the result of two events, such that if one event should happen before another event, the result must reflect that, even if those events are in reality executed out of order (usually to optimize program flow). This involves ordering events based on the potential causal relationship of pairs of events in a concurrent system, especially asynchronous distributed systems. It was formulated by Leslie Lamport. The happened-before relation is formally defined as the least strict partial order on events such that: If events a {\displaystyle a\;} and b {\displaystyle b\;} occur on the same process, a → b {\displaystyle a\to b\;} if the occurrence of event a {\displaystyle a\;} preceded the occurrence of event b {\displaystyle b\;} . If event a {\displaystyle a\;} is the sending of a message and event b {\displaystyle b\;} is the reception of the message sent in event a {\displaystyle a\;} , a → b {\displaystyle a\to b\;} . If two events happen in different isolated processes (that do not exchange messages directly or indirectly via third-party processes), then the two processes are said to be concurrent, that is neither a → b {\displaystyle a\to b} nor b → a {\displaystyle b\to a} is true. If there are other causal relationships between events in a given system, such as between the creation of a process and its first event, these relationships are also added to the definition. For example, in some programming languages such as Java, C, C++ or Rust, a happens-before edge exists if memory written to by statement A is visible to statement B, that is, if statement A completes its write before statement B starts its read. Like all strict partial orders, the happened-before relation is transitive, irreflexive, (and, vacuously, asymmetric), i.e.: ∀ a , b , c {\displaystyle \forall a,b,c} , if a → b {\displaystyle a\to b\;} and b → c {\displaystyle b\to c\;} , then a → c {\displaystyle a\to c\;} (transitivity). This means that for any three events a , b , c {\displaystyle a,b,c} , if a {\displaystyle a} happened before b {\displaystyle b} , and b {\displaystyle b} happened before c {\displaystyle c} , then a {\displaystyle a} must have happened before c {\displaystyle c} . ∀ a , a ↛ a {\displaystyle \forall a,a\nrightarrow a} (irreflexivity). This means that no event can happen before itself. ∀ a , b , {\displaystyle \forall a,b,} if a → b {\displaystyle a\to b} then b ↛ a {\displaystyle b\nrightarrow a} (asymmetry). This means that for any two events a , b {\displaystyle a,b} , if a {\displaystyle a} happened before b {\displaystyle b} then b {\displaystyle b} cannot have happened before a {\displaystyle a} . Let us observe that the asymmetry property directly follows from the previous properties: by contradiction, let us suppose that ∀ a , b , {\displaystyle \forall a,b,} we have a → b {\displaystyle a\to b\;} and b → a {\displaystyle b\to a} . Then by tr

Tema degli esploratori: calcolo e infrastrutture (deposito sistematico; ricerca «distributed computing»).
Fonte: Wikipedia in inglese, voce «Happened-before» — https://en.wikipedia.org/wiki/Happened-before
Wikidata Q364138: «relation between the result of two events, such that if one event should happen before another event, the result must reflect that, even if those events are in reality executed out of order» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q364138
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Happened-before?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1361840589, consultata il 2026-10-15T16:01:29.619Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 69c448737c6558ca2ced3d695dee8769d435f993ccf35c13b5f84e314f11ecd8