In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, the happened-before relation

Binary relation

In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...

 (denoted: ) is a means of ordering

Partially ordered set

In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...

 events based on the potential causal relationship of pairs of events in a concurrent system, especially asynchronous

Asynchronous communication

In telecommunications, asynchronous communication is transmission of data without the use of an external clock signal, where data can be transmitted intermittently rather than in a steady stream. Any timing required to recover data from the communication symbols is encoded within the symbols...

 distributed systems. It was formulated by Leslie Lamport

Leslie Lamport

Leslie Lamport is an American computer scientist. A graduate of the Bronx High School of Science, he received a B.S. in mathematics from the Massachusetts Institute of Technology in 1960, and M.A. and Ph.D. degrees in mathematics from Brandeis University, respectively in 1963 and 1972...

.

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 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.

Like all strict partial orders, the happened-before relation is transitive

Transitive relation

In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....

, irreflexive and antisymmetric

Antisymmetric relation

In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in Xor, equivalently,In mathematical notation, this is:\forall a, b \in X,\ R \and R \; \Rightarrow \; a = bor, equivalently,...

, i.e.:

• , if and , then (transitivity) ;
• (irreflexivity) ;
• if then (antisymmetry).

The processes that make up a distributed system have no knowledge of the happened-before relation unless they use a logical clock

Logical clock

A logical clock is a mechanism for capturing chronological and causal relationships in a distributed system.Logical clock algorithms of note are:* Lamport timestamps, which are monotonically increasing software counters....

, like a Lamport clock or a vector clock. This allows to design algorithms for mutual exclusion

Mutual exclusion

Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...

and tasks like debugging or optimising distributed systems.