Vector Orologi

Sruthi Sree Kumar
Sruthi Sree Kumar

Seguire

17 Maggio 2020 · 3 min a leggere

Come Lamport Orologio Vector Clock è anche un clock logico, che viene utilizzato per assegnare i timestamp per gli eventi in un sistema distribuito. Vector clock fornisce anche un ordinamento parziale degli eventi. Una delle carenze dell’orologio di Lamport è che non può identificare eventi simultanei correlati causalmente. Qui, invece di usare valori interi per il timestamp, usiamo un vettore di valori interi per rappresentare il timestamp. Se abbiamo N processi nel gruppo, ogni processo avrà un vettore con N elementi.

La regola per incrementare il timestamp per l’orologio vettoriale è anche simile all’orologio di Lamport con una piccola aggiunta ad esso. Gli eventi aggiornano il timestamp logico in base alle regole seguenti:

  1. Prima di eseguire un evento, il processo i incrementa l’elemento i-esimo del suo orologio vettoriale di 1
V = V + 1

2. Durante un evento di invio, il processo i incrementa l’elemento i-esimo del suo orologio vettoriale di 1 e invia il tempo (Vmsg) insieme al messaggio.

V = V + 1

3. Durante un evento di ricezione, il processo i incrementa l’elemento i-esimo del suo orologio vettoriale di 1. Per tutti gli altri processi, prende il massimo dell’elemento corrispondente nel messaggio in arrivo e il proprio vettore locale e lo imposta come elemento corrispondente nell’orologio locale stesso.

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

Possiamo usare i timestamp vettoriali per verificare se due eventi sono causalmente correlati o simultanei. Prima di ciò, vedremo come vengono confrontati due timestamp vettoriali.

Per due timestamp V1 e 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 

Due eventi con il vettore di timestamp V1 e V2 sono causalmente correlati, se

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

Due eventi con il vettore di timestamp V1 e V2 sono concorrenti, iff

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

Fig 1: Vector Clock

La figura mostra come il vettore di valori timestamp vengono incrementati per diversi tipi di eventi. Vediamo alcuni esempi di eventi simultanei ed eventi causalmente correlati.

Esempi per Causalmente eventi:

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

a -> b (1,0,0) < (2,0,0)

m -> k come (0,0,2) < (6,3,2)

Esempi per la concomitanza con altre manifestazioni:

Per gli eventi b e l abbiamo vettoriale timestamp (2,0,0) & (0,0,1), rispettivamente. Qui né b ≤ l né l ≤ b. Quindi, sono eventi simultanei. Allo stesso modo, d e j sono eventi simultanei.

Vector clock è anche un orologio logico che obbedisce alla causalità e garantisce l’ordine parziale degli eventi. Rispetto all’orologio di Lamport, può identificare gli eventi simultanei in modo efficiente poiché l’orologio vettoriale viene rappresentato utilizzando più spazio.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.