Erweiterte Lamportzeit

Die erweiterte Lamportzeit bzw. erweiterte Lamportuhr ist eine Erweiterung der von Leslie Lamport entwickelten Lamport-Uhr.

Für die Lamportzeit gilt Folgendes:

 $LC(a)=LC(b)\not \Rightarrow a=b$

Um diese Implikation zuzulassen, erweitert man den Zeitstempel der Lamport-Uhr um zusätzliche Informationen, die einer totalen Ordnung unterliegen. Im Rahmen der Lamport-Uhr wäre hier der Name des Prozesses möglich. Man definiert die Uhrenbedingung der erweiterten Lamportzeit wie folgt:

Sei A ein Prozess. Dann sei $LC_{E}(A,e)$ die erweiterte Lamportzeit des Prozesses A für ein Ereignis e, und es gilt:

 $LC_{E}(A,a)<LC_{E}(B,b)\Leftrightarrow LC(a)<LC(b)\lor (LC(a)=LC(b)\land A<B)$

Hierdurch erhalten alle Ereignisse einen eindeutigen Zeitstempel, der einer totalen Ordnung unterliegt. Die schwache Konsistenzbedingung bleibt erhalten, denn es gilt (in der Happened-Before Notation):

 $a\Rightarrow b\Longrightarrow LC(a)<LC(b)\Longrightarrow LC_{E}(A,a)<LC_{E}(B,b)$

Mit der erweiterten Lamportzeit gilt demnach die Implikation

 $LC(a)=LC(b)\Rightarrow a=b$

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.