Algoritmo de Berkeley §

---

1. O que é o Algoritmo de Berkeley? §

O Algoritmo de Berkeley é um método de sincronização de relógios físicos para sistemas distribuídos.

Sua principal característica é que ele é usado em sistemas que não possuem uma fonte de tempo externa de alta precisão (como um servidor NTP Estrato 1, GPS ou relógio atômico).

É considerado um algoritmo democrático ou colaborativo.

2. Objetivo §

O objetivo do Algoritmo de Berkeley não é descobrir o tempo real (UTC) exato. Em vez disso, seu objetivo é garantir a sincronização interna: fazer com que todos os relógios das máquinas na rede concordem em um horário comum, que é calculado como a média dos horários de todas as máquinas.

3. Funcionamento (Etapas do Ciclo) §

O algoritmo é centralizado em um coordenador (ou “mestre temporário”) que é eleito periodicamente. O processo de sincronização ocorre em ciclos:

Passo 1: Solicitação §

O coordenador envia uma mensagem para todas as outras máquinas (“escravos”), solicitando seus respectivos horários locais.

Passo 2: Resposta e Cálculo de Atraso §

Cada máquina responde ao coordenador com seu horário. O coordenador mede o tempo de ida e volta da mensagem (RTT - Round-Trip Time) para cada máquina, permitindo-lhe estimar o atraso da rede (similar ao NTP ou Cristian).

Passo 3: Cálculo do Tempo Médio §

O coordenador coleta todos os horários. Ele ajusta cada horário recebido com base no atraso de rede estimado () para ter uma estimativa de todos os relógios em um ponto de referência comum.

Em seguida, ele calcula a média aritmética de todos esses horários ajustados (incluindo o seu próprio):

Onde é o tempo local reportado pela máquina , é o atraso de rede estimado para , e é o número total de máquinas.

Passo 4: Distribuição do Ajuste (Offset) §

O coordenador não envia o tempo médio final para as máquinas. Em vez disso, ele calcula a diferença (offset) que cada máquina deve aplicar para chegar a essa média.

Ele então envia esse valor (que pode ser positivo ou negativo) para a máquina .

Passo 5: Sincronização Gradual (Slew) §

Para evitar saltos no tempo (especialmente retrocessos, que causam inconsistências), cada máquina aplica seu ajuste de forma gradual (slew). Ela acelera ou desacelera seu relógio levemente até que ele se alinhe com o tempo médio calculado.

4. Fluxograma do Processo §

O diagrama abaixo ilustra o ciclo de sincronização coordenado pelo mestre.

sequenceDiagram
    participant Coordenador
    participant No A
    participant No B
    participant No C

    Coordenador->>No A: 1. Qual seu horário?
    Coordenador->>No B: 1. Qual seu horário?
    Coordenador->>No C: 1. Qual seu horário?

    No A-->>Coordenador: 2. Resposta (com $T_A$)
    No B-->>Coordenador: 2. Resposta (com $T_B$)
    No C-->>Coordenador: 2. Resposta (com $T_C$)

    activate Coordenador
    Note over Coordenador: 3. Calcula atrasos ($d_i$) e $T_{medio}$
    deactivate Coordenador

    Coordenador->>No A: 4. Envia $\text{ajuste}_A$
    Coordenador->>No B: 4. Envia $\text{ajuste}_B$
    Coordenador->>No C: 4. Envia $\text{ajuste}_C$

    activate No A
    Note over No A: 5. Aplica ajuste (slew)
    deactivate No A
    activate No B
    Note over No B: 5. Aplica ajuste (slew)
    deactivate No B
    activate No C
    Note over No C: 5. Aplica ajuste (slew)
    deactivate No C

5. Características Principais (Berkeley vs. NTP) §

A principal diferença em relação a protocolos como o NTP é a fonte da verdade:

• NTP: Busca sincronizar clientes com um tempo externo e autoritativo (UTC).
• Berkeley: Cria um tempo de consenso interno (a média), pois não há fonte externa.

Característica	Detalhe
Fonte de Tempo	Nenhuma (autônomo).
Estrutura	Colaborativa / Democrática.
Função do Servidor	Coordenador temporário que coleta, calcula a média e distribui os ajustes.
Objetivo	Sincronização Interna: Alinhar relógios entre si.

Referências §

---