Relógio vetorial - Vector clock

Um relógio vetorial é uma estrutura de dados usada para determinar a ordem parcial de eventos em um sistema distribuído e detectar violações de causalidade . Assim como nos carimbos de data / hora Lamport , as mensagens entre processos contêm o estado do relógio lógico do processo de envio . Um relógio vetorial de um sistema de N processos é uma matriz / vetor de N relógios lógicos, um relógio por processo; uma cópia local dos "maiores valores possíveis" do array de relógio global é mantida em cada processo.

Denote como o relógio vetorial mantido pelo processo i, as atualizações do relógio procedem da seguinte forma: ${\ displaystyle VC_ {i}}$

Exemplo de um sistema de relógios vetoriais. Os eventos na região azul são as causas que levam ao evento B4, enquanto os da região vermelha são os efeitos do evento B4.

• Inicialmente, todos os relógios são zero.
• Cada vez que um processo experimenta um evento interno, ele incrementa seu próprio relógio lógico no vetor em um. Por exemplo, após um evento no processo i, ele se atualiza .${\ displaystyle VC_ {i} [i] \ leftarrow VC_ {i} [i] +1}$
• Cada vez que um processo envia uma mensagem, ele incrementa seu próprio relógio lógico no vetor em um (como no marcador acima, mas não duas vezes para o mesmo evento) e, em seguida, a mensagem carrega uma cópia de seu próprio vetor.
• Cada vez que um processo recebe uma mensagem, ele incrementa seu próprio relógio lógico no vetor em um e atualiza cada elemento em seu vetor, tomando o máximo do valor em seu próprio relógio vetorial e o valor do vetor na mensagem recebida (para cada elemento). Por exemplo, se o processo Pj receber uma mensagem m de Pi, ele será atualizado por configuração .${\ displaystyle VC_ {j} \ leftarrow max (VC_ {j} [k] + 1, VC_ {i} [k]), \ forall k}$

História

Sem usar o nome específico "relógio vetorial", o conceito de relógio vetorial foi mencionado pela primeira vez em um artigo de 1986 por Rivka Ladin e Barbara Liskov, onde eles usam o termo "timestamp multipart". Para citar a página 31 do artigo Liskov / Ladin:

Resolvemos esse problema usando carimbos de data / hora com várias partes , onde há uma parte para cada réplica. Assim, se houver n réplicas, um carimbo de data / hora t é

t = <t1, …, tn>

onde cada parte é um número inteiro positivo. Como normalmente haverá um pequeno número de réplicas (por exemplo, de 3 a 7), usar esse carimbo de data / hora é prático.

O termo "relógio vetorial" foi usado pela primeira vez de forma independente por Colin Fidge e Friedemann Mattern em 1988.

Propriedade de pedido parcial

Os relógios vetoriais permitem a ordenação causal parcial dos eventos. Definindo o seguinte:

• ${\ displaystyle VC (x)}$denota o relógio vetorial do evento e denota o componente desse relógio para o processo .${\ displaystyle x}$${\ displaystyle VC (x) _ {z}}$${\ displaystyle z}$
• ${\ displaystyle VC (x) <VC (y) \ iff \ forall z [VC (x) _ {z} \ leq VC (y) _ {z}] \ land \ exists z '[VC (x) _ { z '} <VC (y) _ {z'}]}$
  • Em inglês: é menor que , se e somente se for menor ou igual a para todos os índices de processo , e pelo menos uma dessas relações é estritamente menor (ou seja, ).${\ 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 \ a y \;}$denota que o evento aconteceu antes do evento . É definido como: se , então${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle x \ a y \;}$${\ displaystyle VC (x) <VC (y)}$

Propriedades:

• Antissimetria : se , então ¬${\ displaystyle VC (a) <VC (b)}$${\ displaystyle (VC (b) <VC (a))}$
• Transitividade : se e , então ; ou, se e , então${\ displaystyle VC (a) <VC (b)}$${\ displaystyle VC (b) <VC (c)}$${\ displaystyle VC (a) <VC (c)}$${\ displaystyle a \ to b \;}$${\ displaystyle b \ to c \;}$${\ displaystyle a \ to c \;}$

Relação com outras encomendas:

• Deixe ser o tempo real quando o evento ocorre. Se então${\ displaystyle RT (x)}$${\ displaystyle x}$${\ displaystyle VC (a) <VC (b)}$${\ displaystyle RT (a) <RT (b)}$
• Deixe ser o carimbo de data / hora do evento de Lamport . Se então${\ displaystyle C (x)}$${\ displaystyle x}$${\ displaystyle VC (a) <VC (b)}$${\ displaystyle C (a) <C (b)}$

Outros mecanismos

• Em 1999, Torres-Rojas e Ahamad desenvolveram os Relógios Plausíveis , um mecanismo que ocupa menos espaço do que os relógios vetoriais, mas que, em alguns casos, irá ordenar totalmente eventos que são causalmente simultâneos.

• Em 2005, Agargwal e Garg criaram o Chain Clocks , sistema que rastreia dependências por meio de vetores de tamanho menor que o número de processos e que se adapta automaticamente a sistemas com número dinâmico de processos.
• Em 2008, Almeida et al. introduziu Interval Tree Clocks . Esse mecanismo generaliza Vector Clocks e permite a operação em ambientes dinâmicos quando as identidades e o número de processos na computação não são conhecidos com antecedência.

• Em 2019, Lum Ramabaja desenvolveu Bloom Clocks , uma estrutura de dados probabilística cuja complexidade espacial não depende do número de nós em um sistema. Se dois relógios não forem comparáveis, o relógio bloom pode sempre deduzi-lo, ou seja, falsos negativos não são possíveis. Se dois relógios são comparáveis, o relógio bloom pode calcular a confiança dessa afirmação, ou seja, pode calcular a taxa de falsos positivos entre pares de relógios comparáveis.

Veja também

• Carimbos de data / hora Lamport
• Relógios matriciais
• Vetor de versão

Referências

links externos

• Por que os relógios lógicos são fáceis (compara histórias causais, relógios vetoriais e vetores de versão)
• Explicação dos relógios vetoriais
• Implementação de relógio vetorial com base em carimbo de data / hora em Erlang
• Implementação do relógio vetorial em Objective-C
• Implementação do relógio vetorial em Erlang
• Por que os relógios vetoriais são difíceis
• Por que Cassandra não precisa de relógios vetoriais