Zegar wektorowy – Wikipedia

A Zegar wektorowy to urządzenie oprogramowania wprowadzone niezależnie w 1988 roku przez Colin Fidge ^{[[[ Pierwszy ]} Et Friedemann Mattern ^{[[[ 2 ]} W celu podania każdego procesu rozproszonych informacji asynchronicznych na temat związku przyczynowego przybyła awangard.

Każdy proces P ma cały wektor zwany pieczęć w którym każdy składnik stempluje [i] jest oszacowaniem przez P wartości zegara lamport procesu i. W szczególności Estampille [P] jest dokładnie zegar P. Jest aktualizowany zgodnie z następującymi zasadami:

• Wewnętrzne zdarzenie powoduje wzrost drukowania [P];
• Przed wysłaniem wiadomości Stamp [P] rośnie, a wiadomość jest wysyłana z nową wartością znaczków;
• Po otrzymaniu wiadomości każdy komponent j ≠ p znacznika przyjmuje maksymalną wartość (znacz [j] wiadomości, pieczęć [j] prąd). Następnie stempla [p] jest zwiększana.

Aby porównać dwa logiczne zegary, mówi się, że c ≺ c ‘( Znaczek C poprzedza pieczęć C ‘ ) Jeśli i tylko wtedy, gdy weryfikowane są następujące dwa warunki:

• ∀ i, c [i] ≤ c ‘[i] ( Każde datowanie witryny znaczków C jest mniejsze lub równe odpowiednim datowaniu w C ‘ ),
• ∃ I Tel That C [i] Jest co najmniej jeden ściśle niższy randki ).

Jeśli C ⊀ C ‘i C’ ⊀ C, to C ∥ C ‘(dwa zegary nie są porównywalne).

Zegary wektorowe całkowicie wychwytują związek →: Dla dwóch zdarzeń A i B, A → B Si i tylko wtedy, gdy znaczek A jest niższy niż w B. Z drugiej strony A i B są niezależne, jeśli i tylko wtedy, gdy ich znaczki nie są porównywalne.

Zegary wektorowe dają bardziej precyzyjne informacje niż logiczne zegary dla wyższych kosztów pamięci. Są one stosowane w algorytmach wzajemnego wykluczenia, debugowania i optymalizacji.

Chociaż możliwe jest całkowite określenie relacji → za pomocą zegarów wektorowych, czasami konieczne jest użycie bardziej skomplikowanych urządzeń: zegarów macierzy.

Lub 3 procesy, P1, P2, P3. Każdy ma swój znaczek, każdy złożony z trzech liczb lub dat, trzy odpowiadające każdemu procesowi:

• Estampille P1: [0 (data dla p1), 0 (dla p2), 0 (dla p3)]
• Stamp P2: [0, 0, 0]
• P3 Stamp: [0, 0, 0]

Wyobraź sobie, że istnieje wewnętrzne wydarzenie w P1. Znaczki stają się:

• Estampille P1: [1, 0, 0]
• Stamp P2: [0, 0, 0]
• P3 Stamp: [0, 0, 0]

Teraz wyobraź sobie, że P1 wysyła wiadomość do P3. W serialu znaczki stają się:

• Estampille P1: [2, 0, 0]
• Stamp P2: [0, 0, 0]
• P3 Stamp: [0, 0, 0]

Wiadomość będzie nosi jako znaczek [2, 0, 0], który odpowiada znaczku P1 podczas programu.

Po przyjęciu znaczki stają się:

• Estampille P1: [2, 0, 0]
• Stamp P2: [0, 0, 0]
• P3 Stamp: [2, 0, 1]

Na znaczku P3 data P3 rośnie po otrzymaniu wiadomości, ponieważ przyjęcie jest zdarzeniem, podczas gdy data P1 jest aktualizowana o 2, w zależności od maksimum między istniejącą datą a datą.

W tym przykładzie można powiedzieć, że znaczek P1 poprzedza pieczęć P3, ponieważ wszystkie daty pierwszego są odpowiednio mniejsze lub równe drugie, i że istnieje co najmniej jeden z ściśle niższych: P3.

(FR) Logiczne zegary i znaczki