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.

Marcas temporais

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:

1. Se a acontece antes de b no mesmo processo, então C(a) < C(b).
2. Se a e b representam, respectivamente, o envio e o recebimento de uma mensagem, então C(a) < C(b).
3. Sejam a e b eventos quaisquer, então C(a) ≠ C(b)

Ordenação parcial ou total

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.

Regras

Os relógios de Lamport obedecem as seguintes regras:

1. Um processo incrementa seu contador antes de cada evento daquele processo;
2. Quando um processo envia uma mensagem, esse inclui o valor de seu contador junto da mensagem;
3. No recebimento de uma mensagem, o processo atualiza seu contador para o valor maior entre o próprio valor e o valor do contador recebido na mensagem;

Algoritmos distribuídos

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.

Para contornar as desvantagens da versão centralizada do algoritmo, versões descentralizadas foram apresentadas. Lamport em 1978 apresentou uma primeira versão do algoritmo, e em 1981, Ricart e Agrawala o tornaram mais eficiente.

O algoritmo de Ricart e Agrawala faz uso da ordenação total dos eventos, portanto faz uso dos relógios de Lamport e funciona da seguinte forma:

• Quando um processo quer entrar na região crítica, ele cria uma mensagem contendo o nome da região crítica, o número de seu processo e valor de seu contador. E então envia essa mensagem para todos os outros processos participantes do sistema. Para isso assume-se que o envio das mensagens é confiável.
• Quando um processo recebe uma mensagem de requisição de entrada na região crítica, três ações podem ser tomadas de acordo com o estado da região crítica:
  • Se ele não está na região crítica nomeada na mensagem e também não que entrar na mesma, responde a mensagem com um OK.
  • Se ele já está na região crítica, ele não responde a mensagem. Ao invés disso, ele enfileira a requisição.
  • Se ele quer entrar na região crítica mas ainda não o fez, ele compara a marca temporal da mensagem recebida com a marca temporal da mensagem que ele enviou para todos. Se a mensagem recebida tiver a menor marca temporal, o processo responde com um OK, caso contrário, ele enfileira a requisição.
• Após enviar as requisições de entrada na região crítica para todos os outros processos, o processo espera as respostas dessas requisições. Uma vez que todas as permissões foram recebidas, o processo entra na região crítica.
• Ao sair da região crítica o processo envia OK para todos os processos que estão na sua fila de requisições e apaga essa fila.

Da mesma forma que o algoritmo centralizado citado acima, com o algoritmo descentralizado a exclusão mútua é garantida sem deadlock ou starvation. O número de mensagens trocadas por entrada na região crítica é 2(n-1), onde n é o número de processos no sistema. Além disso, não há ponto único de falha nessa solução.

Porém, o ponto único de falha agora foi substituído por n pontos de falha. Quando algum processo falha, ele para de responder às requisições. Essa falta de resposta pode ser interpretada como uma negação de permissão, bloqueando as entradas na região crítica por outros processos. Esse problema pode ser contornando adicionando respostas, inclusive de negação de permissão, a cada mensagem de requisição. Uma falha de entrega agora pode ser detectada por timeout.

Outro problema que acaba existindo com o uso do algoritmo distribuído é a necessidade de uma primitiva de comunicação em grupo. Cada processo agora precisa manter uma lista dos membros do grupo, percebendo entradas, saídas e falhas desses membros.

Dessa forma, na versão distribuída do algoritmo, todos os processos estão envolvidos em todas as decisões de entrada na região crítica. Comparando com o algoritmo centralizado e a suposição de gargalo, se um dos nós não suporta a carga é pouco provável que forçando a paralelização, fazendo com que todos os nós façam a mesma coisa, venha a existir a solução para esse gargalo.

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.

O algoritmo funciona da seguinte forma:

1. Um processo cria uma mensagem contendo sua marca temporal atual e então faz multicast para todos os outros processos do grupo.
2. Os contadores são atualizados no envio e recebimento das mensagens.
3. Quando uma mensagem é recebida, o processo a coloca em sua fila local de acordo com sua marca temporal e aguarda pela confirmação das mensagens enviadas.

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.

Ver também

• Relógios lógicos
• Relógios vetoriais

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