Relógios lógicos de Lamport §

---

1. Objetivo Principal §

Os Relógios Lógicos de Lamport, propostos por Leslie Lamport em 1978, são um mecanismo para estabelecer uma ordem de eventos em um sistema distribuído.

O objetivo não é sincronizar os relógios físicos com o tempo real (como o UTC), mas sim garantir uma ordem lógica consistente que respeite a causalidade.

2. A Relação “Acontece Antes” () §

Lamport define uma relação de precedência temporal, chamada “acontece antes” (representada por ), com base em três regras:

1. No Mesmo Processo: Se os eventos e ocorrem no mesmo processo e ocorre antes de , então .
2. Troca de Mensagens: Se é o evento de envio de uma mensagem por um processo e é o evento de recebimento dessa mesma mensagem por outro processo, então .
3. Transitividade: Se e , então .

A função de relógio lógico atribui um timestamp a um evento . Para ser válido, o relógio deve obedecer à Condição do Relógio:

3. Regras de Sincronização (O Algoritmo) §

Para garantir que a Condição do Relógio seja sempre satisfeita, os processos no sistema seguem duas regras para atualizar seus relógios lógicos (contadores inteiros):

1. Eventos Internos/Envio: Antes de executar um evento (seja um evento interno ou o envio de uma mensagem), um processo incrementa seu relógio local: Ao enviar uma mensagem, ele anexa o timestamp .

2. Evento de Recebimento: Quando um processo recebe uma mensagem com o timestamp de , ele deve primeiro ajustar seu relógio local e depois incrementá-lo pelo evento de recebimento. A regra de atualização é:

Essa regra garante que o timestamp do evento de recebimento seja sempre maior que o timestamp do evento de envio.

4. Exemplo de Funcionamento §

O diagrama abaixo mostra três processos (P1, P2, P3) trocando mensagens e ajustando seus relógios lógicos.

sequenceDiagram
    participant P1
    participant P2
    participant P3

    Note over P1: C=0
    Note over P2: C=0
    Note over P3: C=0

    P1->>P2: Msg(T=1)
    Note over P1: Evento (C=1)
    Note over P2: Recebe(T=1). C = max(0, 1) + 1 = 2
    
    P2->>P3: Msg(T=3)
    Note over P2: Evento (C=3)
    Note over P3: Recebe(T=3). C = max(0, 3) + 1 = 4
    
    P3->>P2: Msg(T=5)
    Note over P3: Evento (C=5)
    Note over P2: Recebe(T=5). C = max(3, 5) + 1 = 6
    
    P2->>P2: Evento Interno (C=7)

5. Eventos Concorrentes §

Se e (lê-se: “a não acontece antes de b” e “b não acontece antes de a”), então os eventos e são considerados concorrentes.

Isso significa que não há uma relação causal entre eles. Seus timestamps lógicos e não têm uma ordem garantida; pode ser maior, menor ou igual a .

6. Aplicação: Ordenação Total §

Os relógios de Lamport fornecem apenas uma ordem parcial. Para muitas aplicações, como bancos de dados replicados, é necessária uma ordem total (determinística).

• Problema: Dois eventos concorrentes e podem ter o mesmo timestamp lógico ().
• Solução: Criar um timestamp total usando o ID do processo como critério de desempate.

Um evento no processo tem um timestamp total . A ordem total é definida da seguinte forma: se e somente se:

1. , OU
2. e (o ID do processo de é menor que o de ).

Isso garante que todas as mensagens em um multicast possam ser ordenadas de forma idêntica por todos os receptores.

7. Limitação Principal: Não Captura Causalidade §

A principal limitação dos relógios de Lamport é que o inverso da Condição do Relógio não é verdadeiro:

Ou seja, apenas porque um timestamp é menor que outro, não podemos concluir que o primeiro evento causou o segundo. Eles podem ser concorrentes.

Para capturar a causalidade de forma precisa (saber se apenas olhando os timestamps), são necessários os Relógios Lógicos Vetoriais.

Referências §

---