Zegary wektorowe

Sruthi Sree Kumar
Sruthi Sree Kumar

Obserwuj

może 17, 2020 * 3 min czytać

podobnie jak zegar Lamport, Vector Clock jest również zegarem logicznym, który służy do przypisywania znaczników czasu dla zdarzeń w systemie rozproszonym. Zegar wektorowy daje również częściową kolejność zdarzeń. Jedną z wad zegara Lamporta jest to, że nie może on identyfikować równoległych zdarzeń, które są powiązane przyczynowo. Tutaj, zamiast używać wartości całkowitych dla znacznika czasu, używamy wektora wartości całkowitych do reprezentowania znacznika czasu. Jeśli w grupie mamy N procesów, to każdy proces będzie miał wektor z N elementami.

reguła zwiększania znacznika czasu dla zegara wektorowego jest również podobna do zegara Lamporta z niewielkim dodatkiem do niego. Zdarzenia aktualizują logiczny znacznik czasu zgodnie z poniższymi zasadami:

  1. przed wykonaniem zdarzenia, proces i zwiększa i-ten element swojego zegara wektorowego o 1
V = V + 1

2. Podczas zdarzenia send proces i zwiększa i-ten element swojego zegara wektorowego o 1 i wysyła czas (Vmsg) wraz z Komunikatem.

V = V + 1

3. Podczas zdarzenia odbioru proces i zwiększa i-ten element swojego zegara wektorowego o 1. Dla wszystkich innych procesów przyjmuje maksimum odpowiedniego elementu w wiadomości przychodzącej i własnego wektora lokalnego i ustawia go jako odpowiedni element w samym zegarze lokalnym.

V = V + 1V = max(Vmsg, V) for j ≠ i

możemy użyć wektorowych znaczników czasu, aby sprawdzić, czy dwa zdarzenia są powiązane przyczynowo lub równoległe. Wcześniej zobaczymy, jak porównywane są dwa wektorowe znaczniki czasu.

dla dwóch podanych znaczników czasu V1 i V2,

V1 = V2 , iff V1 = V2, for all i = 1 to N (i.e, V1 and V2 are equal if and only if all the corresponding values in their vector matches)V1 ≤ V2 , iff V1 ≤ V2, for all i = 1 to N 

dwa zdarzenia z wektorowymi znacznikami czasu V1 i V2 są powiązane przyczynowo, jeśli

V1 < V2 , iff V1 ≤ V2 & there exists a j such that 1 ≤ j ≤ N & V1 < V2

dwa zdarzenia z wektorowymi znacznikami czasu V1 i V2 są równoczesne, iff

NOT (V1 ≤ V2 ) AND NOT (V2 ≤ V1 )

Rysunek 1: Zegar wektorowy

rysunek przedstawia sposób zwiększania wartości znacznika czasu wektorowego dla różnych typów zdarzeń. Zobaczmy kilka przykładów zdarzeń równoległych i zdarzeń związanych przyczynowo.

przykłady zdarzeń związanych przyczynowo:

a -> j as (1,0,0) < (2,2,0)

a – > B jak (1,0,0) < (2,0,0)

m – > K jak (0,0,2) < (6,3,2)

przykłady dla równoległych zdarzeń:

dla zdarzeń b i l mamy odpowiednio wektorowe znaczniki czasu (2,0,0) & (0,0,1). Tutaj ani b ≤ l, ani l ≤ b. stąd są to zdarzenia równoległe. Podobnie d I j są zdarzeniami równoległymi.

zegar wektorowy jest również zegarem logicznym, który przestrzega przyczynowości i zapewnia częściowy porządek zdarzeń. W porównaniu z zegarem Lamporta, może efektywnie identyfikować zdarzenia równoległe, ponieważ zegar wektorowy jest reprezentowany przy użyciu większej przestrzeni.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.