Arrivé-avant | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

In computer science, the happened-before relation (denoted: ) 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 and occur on the same process, if the occurrence of event preceded the occurrence of event . If event is the sending of a message and event is the reception of the message sent in event , . 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 nor 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.: if and , then (transitivity). This means that for any three events , if happened before , and happened before , then must have happened before . (irreflexivity). This means that no event can happen before itself. if then (asymmetry). This means that for any two events , if happened before then cannot have happened before . Let us observe that the asymmetry property directly follows from from the previous properties: by contradiction, let us suppose that we have and .

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (2)

Horloge logique

A logical clock is a mechanism for capturing chronological and causal relationships in a distributed system. Often, distributed systems may have no physically synchronous global clock. In many applications (such as distributed GNU make), if two processes never interact, the lack of synchronization is unobservable and in these applications it is enough for the processes to agree on the event ordering (i.e., logical clock) rather than the wall-clock time.

Arrivé-avant

En informatique, la relation arrivé-avant (anglais happened-before), notée , est un ordre partiel (relation binaire irréflexive, asymétrique et transitive) sur les événements basé sur la causalité de deux événements dans un système distribué asynchrone. Elle est introduite par Leslie Lamport en 1978. La relation arrivé-avant est définie ainsi: Si les événements et surviennent dans le même processus, si l'occurrence de précède l'occurrence de . Si l’événement est l'émission d'un message et l’événement est la réception de ce même message, alors .