Francais | English | Espanõl

From Wikipedia, the free encyclopedia

The happened-before relation (denoted: <math>\to</math>) is a means of ordering events based on the causal relationship of two events in asynchronous distributed systems. It was formulated by Leslie Lamport.

The happened-before relation is formally defined as:

• If events <math>a \;</math> and <math>b \;</math> occur on the same process, <math>a \to b</math> if the occurrence of event <math>a \;</math> preceded the occurrence of event <math>b \;</math>.
• If event <math>a \;</math> is the sending of a message and event <math>b \;</math> is the reception of the message sent in event <math>a \;</math>, <math>a \to b</math>.
• Transitivity property: for three events <math>a \;</math>, <math>b \;</math>, and <math>c \;</math>, if <math>a \to b</math> and <math>b \to c</math>, then <math>a \to c</math>.

Unlike vector clocks, the happened-before relation is not reflexive or symmetric and, therefore, can only ensure the partial ordering of events. Specifically, <math>a \to b</math> implies <math>time(a) < time(b) \;</math> but <math>time(a) < time(b) \;</math> does not imply <math>a \to b</math>. In order to formulate total ordering of events, an algorithm such as vector clocks must be used.

The happened-before relationship is used in time stamping messages (Lamport timestamps) and in building logical clocks (Lamport clocks).de:Happened-Before nl:Algoritme van Lamport