Happened-before
Happened-before is a logical relationship between two points in time in computer science .
The happened-before-relation is important to determine the causal order of events in asynchronous distributed systems . It was formulated by Leslie Lamport . The happened-before relation is generally implemented by a logical clock . Conversely, the happened -before-relation defines the clock condition for this logical clock.
In order to find out the relative time between two occurring events in a distributed system without a global clock, the happened-before relation (→) is used, which is defined for Lamport clocks as follows:
- On the same process, a → b if the time of a <the time of b (the time is given by the local clock)
- If a process sends a message to another process, then a → b if a is the sender and b is the recipient.
- For three events a, b, c, if a → b and b → c, then a → c ( transitivity ).
The value of the local clock is added to the message as a time stamp .
The Happend-Before relation according to Lamport only provides a strict partial order for the events. It is not sufficient if one wants to consider concurrent events: Concurrency cannot be read off on a Lamport clock, because a → b means that time (a) <time (b), but time (a) <time (b ) does not mean that a → b.
To get a total order of events, one can e.g. B. Use vector clocks .
Individual evidence
- ↑ Lamport, Leslie (1978). "Time, Clocks and the Ordering of Events in a Distributed System" , Communications of the ACM , 21 (7), 558-565.