Algoritmo de Cristian §

---

1. O que é o Algoritmo de Cristian? §

O Algoritmo de Cristian é um método de sincronização de relógios em sistemas distribuídos. Ele permite que um computador cliente ajuste seu relógio local para que corresponda ao de um servidor de tempo confiável, levando em consideração o atraso (latência) da rede.

Foi proposto por Flaviu Cristian em 1989 e é considerado um predecessor de protocolos mais complexos, como o NTP (Network Time Protocol).

2. Mecânica de Funcionamento §

O algoritmo utiliza uma troca de mensagens simples entre o cliente e o servidor para estimar o tempo correto.

O fluxo básico envolve quatro marcações de tempo (timestamps):

1. O Cliente marca seu tempo local e envia um pedido ao servidor.
2. O Servidor recebe o pedido, consulta seu relógio (tempo ) e envia uma resposta contendo .
3. O Cliente recebe a resposta e marca seu tempo local de chegada .

sequenceDiagram
    participant Cliente
    participant Servidor de Tempo

    activate Cliente
    Cliente->>Servidor de Tempo: 1. Pedido de tempo
    Note over Cliente: Marca tempo de envio $t_1$
    deactivate Cliente

    activate Servidor de Tempo
    Servidor de Tempo->>Servidor de Tempo: 2. Consulta relógio (obtém $T_s$)
    Servidor de Tempo-->>Cliente: 3. Resposta (envia $T_s$)
    deactivate Servidor de Tempo

    activate Cliente
    Note over Cliente: Marca tempo de chegada $t_4$
    deactivate Cliente

3. O Cálculo do Ajuste §

A premissa central do algoritmo é que o atraso da rede é simétrico, ou seja, o tempo de ida é igual ao tempo de volta.

3.1. Tempo Total de Viagem (RTT) §

Primeiro, o cliente calcula o tempo total de ida e volta da mensagem (Round-Trip Time):

3.2. Atraso de Ida/Volta (Estimado) §

Assumindo a simetria, o tempo de atraso em um único sentido (seja da ida ou da volta) é estimado como metade do RTT:

3.3. Cálculo do Offset (Desvio) §

O objetivo é descobrir qual era a hora do servidor no exato momento . O cliente estima isso pegando a hora que o servidor enviou () e somando o tempo que a resposta demorou para voltar ():

O offset (o quanto o relógio do cliente está errado) é a diferença entre essa hora real estimada e a hora local do cliente ():

Substituindo as fórmulas, temos a equação completa do offset:

O cliente, então, ajusta seu relógio local somando esse offset calculado.

4. Exemplo de Cálculo §

Dados os seguintes tempos:

• Tempo de envio ():
• Tempo do servidor ():
• Tempo de recebimento ():

1. Cálculo do RTT:

2. Cálculo do Atraso:

3. Cálculo do Offset:

Resultado: O offset é , indicando que o relógio do cliente está perfeitamente sincronizado.

5. Principal Limitação §

A maior fraqueza do Algoritmo de Cristian é a sua suposição de latência simétrica.

Em redes reais, o caminho de ida pode ser muito mais congestionado (e lento) que o caminho de volta, ou vice-versa. Quando a latência é assimétrica, o cálculo de torna-se impreciso, introduzindo um erro no cálculo do offset.

Referências §

---