Relógios vetoriais

Os Relógios vetoriais são mecanismos usados em algoritmos de sistemas distribuídos que se baseiam na ordenação de eventos. Diferentemente dos relógios de Lamport, os relógios vetoriais são capazes de decidir se há causalidade entre os eventos. Esses mecanismos se interessam na ordenação parcial dos eventos.

Exemplo de um sistema de relógios vetoriais

O algoritmo de relógios vetoriais foi desenvolvido independentemente por Colin Fidge e Friedemann Mattern em 1988.

Problema dos relógios de Lamport

Por usar inteiros simples como marcas de tempo, o algoritmo de Lamport acaba perdendo informações de vários ordenamentos válidos. Apesar de consistente, a relação definida no algoritmo de Lamport define apenas uma de várias ordenações possíveis dada uma certa computação distribuída. De acordo com Lamport, se a → b então C(b) > C(a), porém o contrário não é verdadeiro.

Problemas que se preocupam com o estado global do sistema muitas vezes precisam de todas as ordenações potenciais.

Os relógios vetoriais resolvem esse problema fazendo com que cada processo mantenha um array de contadores, sendo cada posição do array, um contador para cada processo no sistema.

Ordenação parcial

O algoritmo de relógios lógicos reconhece que os eventos de comunicação (envio e recebimento de mensagens) formam "fronteiras" que separam a possibilidade de concorrência entre eventos. Como alguns eventos só ocorrem como decorrência do recebimento de mensagens, pode-se notar o conceito de causa e efeito entre os eventos em um sistema distribuído

Na ordenação parcial, mensagens sem causalidade não são mais ordenadas, o que acaba sendo menos custoso que a ordenação total.

Regras

Para a comunicação entre os processos, os arrays de marcas temporais são mantidos da seguinte forma:

1. Todos os valores do array são iniciados com zero;
2. O contador local é incrementado em uma unidade antes de cada evento atômico;
3. Sempre que o processo se prepara para enviar uma mensagem, ele incrementa o valor no array correspondente ao seu relógio lógico em uma unidade e envia todo o array junto da mensagem;
4. No recebimento de uma mensagem, o processo atualiza o seu atual para o máximo entre os valores do array recebido na mensagem e os valores de seu array. Porém, o valor do contador correspondente ao emissor é incrementado em uma unidade caso seu valor local já não é maior que o recebido;
5. Os valores de um array de marcas temporais nunca são decrementados.

Para a comunicação síncrona, deve haver um troca dos arrays de marcas temporais durante o evento de comunicação, devido a natureza simétrica da comunicação síncrona. Caso contrário o algoritmo falha, pois espera que a comunicação tome um tempo finito.

Número variável de processos

Quando há um número variável de processos no sistema, os "arrays" de marcas temporais devem ser implementados como listas dinâmicas, sendo redimensionadas na entrada e saída de processos no sistema.

Ao comparar as marcas temporais, se nenhuma entrada existe para um determinado processo, deve-se considerar esse valor como zero para efeito de comparação.

Aplicações

• Inicialmente desenvolvido para checagem dinâmica de programas CSP (Communicating Sequential Proccess).
• Verificação de consistência de estados em sistemas distribuídos, funcionalidade importante para efeitos de checkpointing, recuperação de erros e rollback.

Ver também

• Relógios lógicos
• Relógios de Lamport

Referências gerais

• Tanenbaum, A.S.; Steen, M.V. 2002. Distributed Systems - Principles and Paradigms. Prentice Hall.
• Leslie Lamport (1978). «Time, clocks, and the ordering of events in a distributed system» (PDF). Communications of the ACM. 21 (7): 558–565. doi:10.1145/359545.359563 
• Colin J. Fidge (1988). «Timestamps in message-passing systems that preserve the partial ordering» (PDF). In: K. Raymond (Ed.). Proc. of the 11th Australian Computer Science Conference (ACSC'88). pp. 56–66. Consultado em 23 de fevereiro de 2019