Lamport timestamps

The Lamport clock ( after the American mathematician and computer scientist Leslie Lamport ) is a software component (or a protocol) for assigning unique time stamps of messages. It is therefore a logical clock that allows you to assign a partial causal order events in a distributed system due to their timestamp.

In this case, proceed as follows: Each process has a counter ( the clock ), which is in any event (especially when sending and receiving messages ) increased. In addition, the current state of the counter is appended to each message as a timestamp. Will now receive a message whose time stamp is greater than or equal to the current state of its own clock, then the clock is set to the value of the timestamp 1.

The routine for sending a message does so ( in pseudocode ) as follows:

Clock clock = 1; Timestamp = clock; send ( message, timestamp); The routine for receiving a message:

( Message, timestamp) = receive (); Clock = max ( timestamp, clock ) 1; To sort in retrospect all received messages ( n1, n2, etc.) according to their time stamp (C (n1 ), C ( n2 ), etc. ), then it is guaranteed that if the message had n1 n2 an impact on the message, the timestamp of n1 is less than the timestamp of n2. This corresponds to the weak consistency condition for watches:

This is also called the Happened -before relation by Lamport wrote:

However, Lamport clocks do not satisfy the strong consistency condition for watches. In particular, one can at the time stamps of a Lamport clock not see which events causally independent, that is, are concurrent. A solution to this problem offer something more complex vector clocks.

The algorithm Basic Timestamp Ordering uses the Lamport clock to synchronize distributed transactions.

497037
de