Relógios de Lamport
Relógios lógicos de Lamport são mecanismos usados em algoritmos de sincronização de relógio baseados na relação happens-before definida por Leslie Lamport.
Nesses algoritmos cada processo do sistema distribuído mantém um contador crescente e monotônico C (relógio lógico) e cada evento a possui uma marca temporal C(a) na qual todos os processos concordam. Dessa forma, os eventos estão sujeitos às seguintes propriedades derivadas da relação happens-before:
Ordenação total dos eventos se dá quando é possível definir a ordem de quaisquer dois eventos. De acordo com as propriedades dos contadores (timers) Lamport nenhum par de eventos terá uma mesma marcação temporal, pois basta ordenar os eventos de acordo com o tempo que eles ocorrem em seus processos e desfazer empates comparando uma propriedade arbitrária dos processos, como por exemplo, seu identificador. Quando este empate não é desfeito, uma ordenação parcial é obtida. Como em vários algoritmos distribuídos a ordenação total é necessária para evitar ambiguidades, o algoritmo de Lamport é bastante citado na literatura. Nos algoritmos de disputa a recursos compartilhados, apenas um processo pode usar um recurso por vez, então os processos devem sincronizar para evitar conflitos, dessa forma ordenação total é um requisito para esse algoritmo.
Os relógios de Lamport obedecem as seguintes regras:
Alguns algoritmos distribuídos podem fazer uso dos relógios de Lamport, tais quais:
Exclusão mútua
Em sistemas distribuídos onde há disputa de recursos normalmente há a implementação de regiões críticas. Quando um processo precisa acessar uma certa informação compartilhada, este primeiramente precisa acessar a região crítica e todos os processos devem concordar que este processo está nesta região, a fim de garantir que nenhum outro processo acessará o mesmo dado ao mesmo tempo Uma solução centralizada para o problema seria adotar um processo coordenador que seria responsável por receber solicitações para a região crítica e dar permissões de entrada para o processo solicitante quando possível. É fácil perceber que a solução garante exclusão mútua e é justa, porém o processo coordenador se torna um possível gargalo de performance e um ponto único de falha.
Multicast totalmente ordenado
O algoritmo de multicast totalmente ordenado também faz uso dos relógios de Lamport e da ordenação total. Ele se faz necessário quando precisamos garantir a mesma sequência de eventos em todos os processos do sistema, como por exemplo, em uma atualização de banco de dados replicado em diversas máquinas. Uma mensagem então só é de fato entregue à aplicação quando está na cabeça da fila e todas confirmações daquela mensagem foram recebidas. Ou seja, o processo garante que a marca temporal da mensagem entregue é menor que os contadores de outros processos. Além disso, desempates de marcas temporais de mensagens são feitos através de identificadores arbitrários dos processos, permitindo a ordenação total dos eventos.
