Geschah-Bevor-Relation

Geschah-Bevor-Relation
Ursache und Wirkung, bzw. Vergangenheit und Zukunft, in einer Lamport-Uhr

Happened-Before (englisch für „passierte vor“) ist in der Informatik eine logische Beziehung zwischen zwei Zeitpunkten.

Die Happened-Before-Relation ist wichtig um die Kausalordnung von Ereignissen in asynchronen verteilten Systemen zu bestimmen. Sie wurde von Leslie Lamport formuliert. Die Happened-Before-Relation wird im Allgemeinen durch eine logische Uhr implementiert. Umgekehrt definiert die Happened-Before-Relation die Uhrenbedingung für diese logische Uhr.

Um die relative Zeit zwischen zwei auftretenden Ereignissen in einem verteilten System ohne eine globale Uhr herauszufinden, benutzt man die Happened-Before-Relation (→), die für Lamport-Uhren wie folgt definiert ist:

  • Auf demselben Prozess, a → b wenn die Zeit von a < der Zeit von b (die Zeit ist durch die lokale Uhr gegeben)
  • Wenn ein Prozess eine Nachricht zu einem anderen Prozess sendet, dann a → b wenn a der Sender ist und b der Empfänger.
  • Für drei Ereignisse a, b, c, wenn a → b und b → c, dann a → c (Transitivität).

Dabei wird der Wert der lokalen Uhr jeweils der Nachricht als Zeitstempel beigefügt.

Die Happend-Before-Relation nach Lamport liefert nur eine partielle Ordnung für die Ereignisse. Sie ist nicht ausreichend, wenn man nebenläufige Ereignisse betrachten will: die Nebenläufigkeit lässt sich an einer Lamport-Uhr nicht ablesen, denn a → b bedeutet, dass Zeit(a) < Zeit(b), aber Zeit(a) < Zeit(b) bedeutet nicht, dass a → b.

Um eine totale Ordnung von Ereignissen zu erhalten kann man z. B. Vektoruhren benutzen.


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Geschah-Bevor — Ursache und Wirkung, bzw. Vergangenheit und Zukunft, in einer Lamport Uhr Happened Before (englisch für „passierte vor“) ist in der Informatik eine logische Beziehung zwischen zwei Zeitpunkten. Die Happened Before Relation ist wichtig um die… …   Deutsch Wikipedia

  • Erkenntnistheorie — Erkenntnis und ihre theoretische Reflexion; Abbildung aus James Ayscough, A Short Account of the Eye and Nature of Vision (London, 1752), S. 30 Die Erkenntnistheorie oder Epistemologie ist ein fachübergreifendes Gebiet der Philosophie, welches… …   Deutsch Wikipedia

  • Freiburg (Breisgau) Hauptbahnhof — Freiburg (Breisgau) Hbf Blick von der Stadtbahnbrücke auf die Gleise und den heutigen Bahnhofskomplex Daten …   Deutsch Wikipedia

  • Sexueller Missbrauch in der römisch-katholischen Kirche — ist ein Phänomen, das seit Mitte der neunziger Jahre weltweit größere öffentliche Aufmerksamkeit erhalten hat. Die Sensibilisierung für das frühere Tabuthema hat viele Opfer ermutigt, 30 oder 40 Jahre nach den Vorfällen an die Öffentlichkeit zu… …   Deutsch Wikipedia

  • Altgriechische Aussprache — Die altgriechische Phonologie (griechisch Προφορά της κλασικής Αρχαίας Ελληνικής γλώσσας : proforá tis klasikís arxaías ellinikís glóssas) ist die Lehre von der Phonologie (bzw. Aussprache) des Altgriechischen. Dabei ist zunächst zu… …   Deutsch Wikipedia

  • Altgriechische Phonologie — Die altgriechische Phonologie (griechisch φωνολογία/προφορά της κλασικής Αρχαίας Ελληνικής γλώσσας, fonología/proforá tis klassikís Archéas Ellinikís glóssas, altgriechisch φωνολογία τῆς ἀρχαίας Ἐλλένικῆς γλώττης) ist die Lehre von der Phonologie …   Deutsch Wikipedia

  • Epistemologie — Bild dessen, was ich sehe. Welche Teile dieses Bildes gehören zu „mir“, welche zur „Außenwelt“, wie leiste ich die Zuordnung? Abbildung aus Ernst Mach, Die Analyse der Empfindungen (1900), S. 15. Die Erkenntnistheorie oder Epistemologie ist neben …   Deutsch Wikipedia

  • Epistemologisch — Bild dessen, was ich sehe. Welche Teile dieses Bildes gehören zu „mir“, welche zur „Außenwelt“, wie leiste ich die Zuordnung? Abbildung aus Ernst Mach, Die Analyse der Empfindungen (1900), S. 15. Die Erkenntnistheorie oder Epistemologie ist neben …   Deutsch Wikipedia

  • Erkenntnisgewinn — Bild dessen, was ich sehe. Welche Teile dieses Bildes gehören zu „mir“, welche zur „Außenwelt“, wie leiste ich die Zuordnung? Abbildung aus Ernst Mach, Die Analyse der Empfindungen (1900), S. 15. Die Erkenntnistheorie oder Epistemologie ist neben …   Deutsch Wikipedia

  • Erkenntnislehre — Bild dessen, was ich sehe. Welche Teile dieses Bildes gehören zu „mir“, welche zur „Außenwelt“, wie leiste ich die Zuordnung? Abbildung aus Ernst Mach, Die Analyse der Empfindungen (1900), S. 15. Die Erkenntnistheorie oder Epistemologie ist neben …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”