Vector Clocks

Sruthi Sree Kumar
Sruthi Sree Kumar

Siga

17 de Maio de 2020 · 3 min de leitura

Como Lamport do Relógio, Vetor de Relógio também é um relógio lógico, que é usado para atribuir carimbos de data / hora para eventos em um sistema distribuído. O relógio vetorial também dá uma ordenação parcial dos eventos. Uma das deficiências do relógio de Lamport é que ele não pode identificar eventos concomitantes que são causalmente relacionados. Aqui, em vez de usar valores inteiros para o timestamp, usamos um vetor de valores inteiros para representar o timestamp. Se temos processos N no grupo, então cada processo terá um vetor com elementos N.

a regra para aumentar o tempo para o relógio vetorial também é semelhante ao relógio de Lamport com uma pequena adição a ele. Os eventos atualizam a data lógica de acordo com as regras abaixo:

  1. Antes de executar um evento, o processo i aumenta o elemento i-ésimo do seu relógio Vetor por 1
V = V + 1

2. Durante um evento de envio, o processo i aumenta o elemento i-ésimo do seu relógio vetor em 1 e envia o tempo(Vmsg) juntamente com a mensagem.

V = V + 1

3. Durante um evento de recepção, o processo i aumenta o elemento i-ésimo do seu relógio vetor em 1. Para todos os outros processos, ele pega o máximo do elemento correspondente na mensagem recebida e seu próprio vetor local e define-o como o elemento correspondente no próprio relógio local.

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

podemos usar os tempos de vetor para verificar se dois eventos são causalmente relacionados ou concomitantes. Antes disso, veremos como duas datas vetoriais são comparadas.

Para dois carimbos de data / hora 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 

Dois eventos com vetor de carimbos de data / hora V1 e V2 são causalmente relacionadas, se

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

Dois eventos com vetor de carimbos de data / hora V1 e V2 são simultâneos, o iff

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

Fig 1: Vetor Relógio

A figura mostra como o vetor de carimbo de data / hora valores são incrementados para diferentes tipos de eventos. Vejamos alguns exemplos de eventos simultâneos e relacionados causalmente.

Exemplos para Causalmente relacionadas com os eventos:

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

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

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

Exemplos de eventos Simultâneos:

Para os eventos b e l temos vetor de carimbos de data / hora (2,0,0) & (0,0,1), respectivamente. Aqui, nem b ≤ l nem l ≤ B. Portanto, eles são eventos concorrentes. Da mesma forma, d E j são eventos concomitantes.

relógio vetorial é também um relógio lógico que obedece à causalidade e garante a ordem parcial dos eventos. Em comparação com o relógio de Lamport, ele pode identificar eventos concorrentes eficientemente como relógio vetorial é representado usando mais espaço.

Deixe uma resposta

O seu endereço de email não será publicado.