Zegar wektor - Vector clock

Zegar wektor jest struktura danych używana dla określenia częściowego uporządkowania zdarzeń w systemie rozproszonym i wykrywanie przyczynowości naruszeń. Podobnie jak w znacznikach czasu Lamporta , komunikaty międzyprocesowe zawierają stan zegara logicznego procesu wysyłającego . Zegar wektorowy systemu N procesów to tablica /wektor N zegarów logicznych, jeden zegar na proces; w każdym procesie przechowywana jest lokalna kopia "największej możliwej wartości" globalnej tablicy zegarowej.

Oznaczmy jako zegar wektorowy utrzymywany przez proces i, aktualizacje zegara przebiegają w następujący sposób: ${\ Displaystyle VC_ {i}}$

Przykład systemu zegarów wektorowych. Zdarzenia w niebieskim obszarze są przyczynami prowadzącymi do zdarzenia B4, natomiast te w czerwonym obszarze są skutkami zdarzenia B4.

• Początkowo wszystkie zegary są zerowe.
• Za każdym razem, gdy proces doświadcza zdarzenia wewnętrznego, zwiększa swój własny zegar logiczny w wektorze o jeden. Na przykład po zdarzeniu w procesie i aktualizuje .${\ Displaystyle VC_ {i} [i] \ leftarrow VC_ {i} [i] + 1}$
• Za każdym razem, gdy proces wysyła wiadomość, zwiększa swój własny zegar logiczny w wektorze o jeden (jak w punkcie powyżej, ale nie dwa razy dla tego samego zdarzenia), a następnie wiadomość dołącza kopię swojego własnego wektora.
• Za każdym razem, gdy proces otrzymuje wiadomość, zwiększa swój własny zegar logiczny w wektorze o jeden i aktualizuje każdy element w swoim wektorze, biorąc maksimum wartości we własnym zegarze wektorowym i wartość w wektorze w odebranej wiadomości (dla każdy element). Na przykład, jeśli proces Pj otrzyma wiadomość m od Pi, aktualizuje się poprzez ustawienie .${\ Displaystyle VC_ {j} \ leftarrow max (VC_ {j} [k] + 1, VC_ {i} [k]), \ forall k}$

Historia

Bez użycia konkretnej nazwy „zegar wektorowy”, koncepcja zegara wektorowego została po raz pierwszy wspomniana w artykule Rivki Ladin i Barbary Liskov z 1986 roku, gdzie użyli terminu „wieloczęściowy znacznik czasu”. Cytując ze strony 31 gazety Liskov/Ladin:

Rozwiązujemy ten problem za pomocą wieloczęściowych znaczników czasu , gdzie dla każdej repliki jest jedna część. Tak więc, jeśli istnieje n replik, sygnaturą czasową t jest

t = <t1, …, tn>

gdzie każda część jest dodatnią liczbą całkowitą. Ponieważ zazwyczaj będzie niewielka liczba replik (np. 3 do 7), użycie takiego znacznika czasu jest praktyczne.

Termin „zegar wektorowy” został po raz pierwszy użyty niezależnie przez Colina Fidge i Friedemanna Mattern w 1988 roku.

Częściowe zamówienie nieruchomości

Zegary wektorowe pozwalają na częściowe uporządkowanie przyczynowo-skutkowe zdarzeń. Zdefiniowanie:

• ${\ Displaystyle VC (x)}$oznacza zegar wektorowy zdarzenia i oznacza składnik tego zegara dla procesu .${\displaystyle x}$${\ Displaystyle VC (x) _ {z}}$${\displaystyle z}$
• ${\ Displaystyle VC (x) < VC (y) \ if \ forall z [VC (x) _ {z} \ leq VC (y) _ {z}] \ ziemi \ istnieje z '[VC (x) _ { z'}<WK(y)_{z'}]}$
  • W języku angielskim: jest mniejsze niż , wtedy i tylko wtedy, gdy jest mniejsze lub równe dla wszystkich wskaźników procesu , a przynajmniej jedna z tych zależności jest ściśle mniejsza (czyli ).${\ Displaystyle VC (x)}$${\ Displaystyle VC (y)}$${\ Displaystyle VC (x) _ {z}}$${\ Displaystyle VC (y) _ {z}}$${\displaystyle z}$${\ Displaystyle VC (x) _ {z'} < VC (y) _ {z'}}$
• ${\displaystyle x\do y\;}$oznacza, że ​​zdarzenie miało miejsce przed zdarzeniem . Jest definiowany jako: jeśli , to${\displaystyle x}$${\displaystyle y}$${\displaystyle x\do y\;}$${\ Displaystyle VC (x) < VC (y)}$

Nieruchomości:

• Antysymetria : jeśli , to ¬${\ Displaystyle VC (a) < VC (b)}$${\ Displaystyle (VC (b) < VC (a))}$
• Przechodniość : jeśli i , to ; lub, jeśli i , to${\ Displaystyle VC (a) < VC (b)}$${\ Displaystyle VC (b) < VC (c)}$${\ Displaystyle VC (a) < VC (c)}$${\displaystyle a\do b\;}$${\displaystyle b\do c\;}$${\displaystyle a\do c\;}$

Związek z innymi zamówieniami:

• Niech będzie rzeczywisty czas, w którym nastąpi zdarzenie . Jeśli , to${\ Displaystyle RT (x)}$${\displaystyle x}$${\ Displaystyle VC (a) < VC (b)}$${\ Displaystyle RT (a) < RT (b)}$
• Niech będzie sygnaturą czasową zdarzenia w Lamporcie . Jeśli , to${\ Displaystyle C (x)}$${\displaystyle x}$${\ Displaystyle VC (a) < VC (b)}$${\ Displaystyle C (a) < C (b)}$

Inne mechanizmy

• W 1999 roku Torres-Rojas i Ahamad opracowali zegary wiarygodności , mechanizm, który zajmuje mniej miejsca niż zegary wektorowe, ale w niektórych przypadkach całkowicie porządkuje zdarzenia, które są przyczynowo współbieżne.

• W 2005 roku Agargwal i Garg stworzyli Chain Clocks , system, który śledzi zależności przy użyciu wektorów o rozmiarze mniejszym niż liczba procesów i który automatycznie dostosowuje się do systemów z dynamiczną liczbą procesów.
• W 2008 roku Almeida i in. wprowadzono Zegary Drzewa Interwałowego . Mechanizm ten uogólnia zegary wektorowe i umożliwia działanie w środowiskach dynamicznych, gdy tożsamość i liczba procesów w obliczeniach nie są z góry znane.

• W 2019 roku Lum Ramabaja opracował Bloom Clocks , probabilistyczną strukturę danych, której złożoność przestrzenna nie zależy od liczby węzłów w systemie. Jeśli dwa zegary nie są porównywalne, zegar bloom zawsze może to wydedukować, tzn. nie są możliwe fałszywe negatywy. Jeśli dwa zegary są porównywalne, zegar Blooma może obliczyć pewność tego stwierdzenia, tj. może obliczyć współczynnik fałszywie dodatnich między porównywalnymi parami zegarów.

Zobacz też

• Sygnatury czasowe Lamport
• Zegary matrycowe
• Wektor wersji

Bibliografia

Zewnętrzne linki

• Dlaczego zegary logiczne są łatwe (porównuje historię przyczynową, zegary wektorowe i wektory wersji)
• Wyjaśnienie zegarów wektorowych
• Implementacja zegara wektorowego opartego na znaczniku czasu w Erlang
• Implementacja zegara wektorowego w Objective-C
• Implementacja zegara wektorowego w Erlang
• Dlaczego zegary wektorowe są trudne
• Dlaczego Cassandra nie potrzebuje zegarów wektorowych