| http://dbpedia.org/ontology/abstract
|
In computer science, the happened-before r … In computer science, the happened-before relation (denoted: ) is a relation between the result of two events, such that if one event should happen before another event, the result must reflect that, even if those events are in reality executed out of order (usually to optimize program flow). This involves ordering events based on the potential causal relationship of pairs of events in a concurrent system, especially asynchronous distributed systems. It was formulated by Leslie Lamport. The happened-before relation is formally defined as the least strict partial order on events such that:
* If events and occur on the same process, if the occurrence of event preceded the occurrence of event .
* If event is the sending of a message and event is the reception of the message sent in event , . If two events happen in different isolated processes (that do not exchange messages directly or indirectly via third-party processes), then the two processes are said to be concurrent, that is neither nor is true. If there are other causal relationships between events in a given system, such as between the creation of a process and its first event, these relationships are also added to the definition.For example, in some programming languages such as Java, C, C++ or Rust, a happens-before edge exists if memory written to by statement A is visible to statement B, that is, if statement A completes its write before statement B starts its read. Like all strict partial orders, the happened-before relation is transitive, irreflexive and antisymmetric, i.e.:
* , if and , then (transitivity). This means that for any three events , if happened before , and happened before , then must have happened before .
* (irreflexivity). This means that no event can happen before itself.
* where , if then (antisymmetry). This means that for any two distinct events , if happened before then cannot have happened before . The processes that make up a distributed system have no knowledge of the happened-before relation unless they use a logical clock, like a Lamport clock or a vector clock. This allows one to design algorithms for mutual exclusion, and tasks like debugging or optimising distributed systems.bugging or optimising distributed systems.
, En informatique, la relation arrivé-avant … En informatique, la relation arrivé-avant (anglais happened-before), notée , est un ordre partiel (relation binaire irréflexive, antisymétrique et transitive) sur les événements basé sur la causalité de deux événements dans un système distribué asynchrone. Elle est introduite par Leslie Lamport en 1978. La relation arrivé-avant est définie ainsi:
* Si les événements et surviennent dans le même processus, si l'occurrence de précède l'occurrence de .
* Si l’événement est l'émission d'un message et l’événement est la réception de ce même message, alors .
* Transitivité: soient trois événements , , et , si et , alors . Deux événements et tels que , et sont dits indépendants. Cette notion de temps logique est fondamentale dans les systèmes distribués asynchrones car, contrairement aux systèmes synchrones, ils ne disposent pas d'une horloge centrale. La relation arrivé-avant permet de donner aux événements du système une structure de treillis. Les processus d'un système peuvent obtenir des informations sur cette relation en utilisant des horloges de différents types :
* horloge logique (ou horloge de Lamport) ;
* horloge vectorielle ;
* horloge matricielle. De nombreux algorithmes reposent sur ces horloges. Leurs principales applications sont l'exclusion mutuelle, le débogage et l'optimisation de systèmes distribués et la tolérance aux défaillances.stribués et la tolérance aux défaillances.
, Het algoritme van Lamport is een door Lesl … Het algoritme van Lamport is een door Leslie Lamport bedachte oplossing om klokken van verschillende computers volgens exact dezelfde frequentie te laten lopen. Dit is van belang om in een gedistribueerd systeem de processen op de verschillende machines met elkaar te communiceren aan de hand van boodschappen. Het op elkaar afstemmen van de klokken is onmogelijk met klokken die werken op kwartskristallen. Lamport loste dit op door een logische klok te gebruiken. Hij bedacht de eerste versie van dit systeem in 1978. de eerste versie van dit systeem in 1978.
, Happened-Before (englisch für „passierte v … Happened-Before (englisch für „passierte vorher“) 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:
* Wenn auf demselben Prozess a vor b stattfindet, dann a → b .
* Wenn ein Prozess eine Nachricht zu einem anderen Prozess sendet, dann a → b wenn a der Sender und b der Empfänger ist.
* 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 eine strikte 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. Zwar ist eine Lamport-Uhr so aufgebaut, dass a → b Zeit(a) < Zeit(b) gilt. Die Umkehrung Zeit(a) < Zeit(b) a → b gilt jedoch nicht (bzw. nur auf demselben Prozess). Um eine totale Ordnung von Ereignissen zu erhalten, kann man z. B. Vektoruhren benutzen.lten, kann man z. B. Vektoruhren benutzen.
, В інформатиці, відношення відношення happe … В інформатиці, відношення відношення happened-before (англ. happened-before — «сталося раніше») (позначається: ) - це відношення між результатом двох подій, таким чином, що якщо одна подія повинна відбутися до іншої події, результат повинен відображати це, навіть якщо ці події насправді виконуються поза порядком (як правило, для оптимізації потоку програми). Це включає впорядкування подій на основі потенційного причинно-наслідкового зв’язку пар подій у паралельній системі, особливо розподілених систем . Його сформулював Леслі Лампорт . Спеціально для Java відносини " раніше" - це гарантія того, що пам'ять, записана в оператор A, є видимою для оператора B, тобто те, що A завершує його запис до того, як твердження B розпочне його читання. [1] [Архівовано 6 січня 2020 у Wayback Machine.] Ставлення happened-before формально визначається як найменш суворий частковий порядок подій:
* Якщо події і відбуваються в одному і тому ж процесі, якщо поява події передує виникнення події .
* Якщо подія це відправлення повідомлень та подія - це прийом повідомлень, відправлених у разі , . Якщо між подіями в даній системі існують інші причинно-наслідкові зв’язки, наприклад, між створенням процесу та його першою подією, ці зв'язки також додаються до визначення. Як і всі суворі часткові порядки, відносини, що відбулися раніше, є транзитивними, нерефлексивними та антисиметричними, тобто:
* , якщо і , потім (транзитивність). Це означає, що для будь-яких трьох подій , якщо сталося раніше , і сталося раніше , потім повинно відбуватися раніше .
* (нерефлексивність). Це означає, що жодна подія не може відбутися перед собою.
* де , якщо потім (антисиметрія). Це означає, що для будь-яких двох різних подій , якщо сталося раніше потім не могло статися раніше . Процеси, що складають розподілену систему, не знають відношення, що сталося раніше, якщо вони не використовують логічний годинник, наприклад, годинник Лампорт або векторний годинник . Це дозволяє розробляти алгоритми взаємного виключення та такі завдання, як налагодження чи оптимізація розподілених систем.дження чи оптимізація розподілених систем.
|
| rdfs:comment |
Happened-Before (englisch für „passierte v … Happened-Before (englisch für „passierte vorher“) 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. Dabei wird der Wert der lokalen Uhr jeweils der Nachricht als Zeitstempel beigefügt.s der Nachricht als Zeitstempel beigefügt.
, Het algoritme van Lamport is een door Lesl … Het algoritme van Lamport is een door Leslie Lamport bedachte oplossing om klokken van verschillende computers volgens exact dezelfde frequentie te laten lopen. Dit is van belang om in een gedistribueerd systeem de processen op de verschillende machines met elkaar te communiceren aan de hand van boodschappen. Het op elkaar afstemmen van de klokken is onmogelijk met klokken die werken op kwartskristallen. Lamport loste dit op door een logische klok te gebruiken. Hij bedacht de eerste versie van dit systeem in 1978. de eerste versie van dit systeem in 1978.
, En informatique, la relation arrivé-avant … En informatique, la relation arrivé-avant (anglais happened-before), notée , est un ordre partiel (relation binaire irréflexive, antisymétrique et transitive) sur les événements basé sur la causalité de deux événements dans un système distribué asynchrone. Elle est introduite par Leslie Lamport en 1978. La relation arrivé-avant est définie ainsi: Deux événements et tels que , et sont dits indépendants. Les processus d'un système peuvent obtenir des informations sur cette relation en utilisant des horloges de différents types :ilisant des horloges de différents types :
, В інформатиці, відношення відношення happe … В інформатиці, відношення відношення happened-before (англ. happened-before — «сталося раніше») (позначається: ) - це відношення між результатом двох подій, таким чином, що якщо одна подія повинна відбутися до іншої події, результат повинен відображати це, навіть якщо ці події насправді виконуються поза порядком (як правило, для оптимізації потоку програми). Це включає впорядкування подій на основі потенційного причинно-наслідкового зв’язку пар подій у паралельній системі, особливо розподілених систем . Його сформулював Леслі Лампорт . Спеціально для Java відносини " раніше" - це гарантія того, що пам'ять, записана в оператор A, є видимою для оператора B, тобто те, що A завершує його запис до того, як твердження B розпочне його читання. [1] [Архівовано 6 січня 2020 у Wayback Machine.]рхівовано 6 січня 2020 у Wayback Machine.]
, In computer science, the happened-before r … In computer science, the happened-before relation (denoted: ) is a relation between the result of two events, such that if one event should happen before another event, the result must reflect that, even if those events are in reality executed out of order (usually to optimize program flow). This involves ordering events based on the potential causal relationship of pairs of events in a concurrent system, especially asynchronous distributed systems. It was formulated by Leslie Lamport. The happened-before relation is formally defined as the least strict partial order on events such that: strict partial order on events such that:
|
