Lamport clock

from Wikipedia, the free encyclopedia

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

The procedure is as follows: Every process has a counter (the clock ) that is incremented with every event (especially when sending and receiving messages). In addition, the current status of the counter is attached to each message as a time stamp. If a message is received with a time stamp that is greater than or equal to the current status of your own clock, the clock is set to the value of the time stamp + 1.

Example of the use of a Lamport clock

The routine for sending a message looks like this (in pseudocode ): 

Uhr = Uhr+1;
Zeitstempel = Uhr;
sende(Nachricht, Zeitstempel);

The routine for receiving a message: 

(Nachricht, Zeitstempel) = empfange();
Uhr = max(Zeitstempel, Uhr)+1;

If you sort all received messages ( n1 , n2 etc.) after their time stamp ( C (n1) , C (n2) etc.), then it is guaranteed that if the message n1 had an influence on the message n2 , the Time stamp of n1 is less than the time stamp of n2 . This corresponds to the weak consistency condition for clocks :

Where for Happened Before - relation is to Lamport.

However, Lamport watches do not meet the strict consistency requirement for watches. In particular, it is not possible to read from the time stamps of a Lamport watch which events are causally independent , that is, concurrently . The somewhat more elaborate vector clocks offer a solution to this problem .

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

See also

literature

  • Leslie Lamport: Time, clocks, and the ordering of events in a distributed system . In: Communications of the ACM . tape 21 , no. July 7 , 1978, ISSN  0001-0782 , pp. 558-565 , doi : 10.1145 / 359545.359563 (English, microsoft.com [PDF; 855 kB ; accessed on August 1, 2008]).