Vektorklokker

Sruthi Sree Kumar
Sruthi Sree Kumar

Følg

17. Mai 2020 * 3 min lese

Som Lamports Klokke Er Vector Clock også en logisk klokke, som brukes til å tildele tidsstempler for hendelser i et distribuert system. Vector klokke gir også en delvis bestilling av hendelsene. En av manglene I Lamports klokke er at Den ikke kan identifisere samtidige hendelser som er årsakssammenheng. Her, i stedet for å bruke heltallsverdier for tidsstempelet, bruker vi en vektor av heltallsverdier for å representere tidsstempelet. Hvis Vi Har n prosesser i gruppen, vil hver prosess ha en vektor Med n elementer.

regelen for å øke tidsstempelet for vektorklokken er også lik Lamports klokke med et lite tillegg til det. Hendelsene oppdaterer det logiske tidsstempelet i henhold til reglene nedenfor:

  1. før du utfører en hendelse, øker prosessen i det i-elementet i vektorklokken ved 1
V = V + 1

2. Under en send-hendelse øker prosessen i-elementet i vektorklokken med 1 og sender tiden (Vmsg) sammen med meldingen.

V = V + 1

3. Under en mottakshendelse øker prosessen i det i-elementet i vektorklokken med 1. For alle andre prosesser tar det maksimalt det tilsvarende elementet i den innkommende meldingen og sin egen lokale vektor og setter den som tilsvarende element i den lokale klokken selv.

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

vi kan bruke vektortidsstemplene til å verifisere om to hendelser er enten årsakssammenheng eller samtidig. Før det vil vi se hvordan to vektor tidsstempler sammenlignes.

For to gitte tidsstempler V1 og 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 

To hendelser Med vektor tidsstempler V1 og V2 er årsakssammenheng, hvis

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

To hendelser Med vektor tidsstempler V1 og V2 er samtidige, iff

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

Fig 1: Vektorklokke

figuren viser hvordan vektortidsstempelverdiene økes for ulike typer hendelser. La oss se noen eksempler på samtidige hendelser og årsakssammenheng.

Eksempler På Årsakssammenheng:

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

a – > b as (1,0,0) < (2,0,0)

m – > k as (0,0,2) < (6,3,2)

Eksempler på Samtidige hendelser:

for hendelsene b og l har vi vektortidsstempler (2,0,0) & (0,0,1) henholdsvis. Her er verken b ≤ l eller l ≤ b. derfor er de samtidige hendelser. På samme måte er d og j samtidige hendelser.

Vector clock Er også en logisk klokke som adlyder kausalitet og sikrer delvis rekkefølge av hendelser. Sammenlignet Med Lamports klokke, kan den identifisere samtidige hendelser effektivt som Vektorklokke er representert ved hjelp av mer plass.

Legg igjen en kommentar

Din e-postadresse vil ikke bli publisert.