SD Relógio Lamport

Sistemas Distribuídos
Jorge Surian [e-mail] Sistemas Distribuídos: Sincronização

Relógios Físicos
 Hora atômica Internacional (International Atomic
Time) é baseada em relógios muito precisos (taxa de variação de 10 -13).
 Hora Coordenada Internacional (Universal
Coordinated Time – UCT) é o padrão para medição do tempo.
 É baseada na hora atômica, mas ocasionalmente é ajustada pela hora astronômia.
 'Broadcast' da hora é feito através de estações de rádio (WWV) e satélites (GPS).
 Computadores que recebem o sinal sincronizam os relógios.

2
2

Relógios Físicos
 Seja C o valor do relógio 'ideal' (hora UTC).
 Seja Cp o valor do relógio no computador p.
 Se t é o tempo no relógio em sincronia com a hora UTC, então temos o tempo em p dado por
Cp(t).
 Idealmente para todo p e para todo t, temos:
– Cp(t) = t → C'p(t) = dC/dt = 1.

 Clock skew (defasagem do relógio): denota a magnitude de diferença entre as frequências de dois relógios.

3
3

Relógios Físicos
 Seja x a taxa máxima de deriva (que especifica se um relógio está adiantado ou atrasado).

 Como fazer a sincronização periódica entre relógios? 4
4

Sincronização de Relógios
 Se existe um 'servidor de tempo' (receptor WWC ou relógio de precisão)
– Algoritmo proposto por Cristian (1989)
 Se não existe uma fonte que disponibilize a hora coordenada universal (UCT)
– Algoritmo de Berkeley
 Tempo exato não importa!!
– Relógios Lógicos → Algoritmo de Lamport e
– Relógios vetoriais

5
5

Algoritmos...
Relógio de Cristian (1989)
– Possibilidade de consultar servidores de tempo equipados com um receptor WWV ou um relógio de alta precisão.
– Problema: Atrasos de mensagens farão com que a hora fornecida seja desatualizada!
– Variações na estimativa do atraso entre as máquinas. 6
6

Algoritmos...
Relógio de Cristian (1989)

– Computador A consulta a hora no computador B.
– Computador B inclui na resposta o valor do seu relógio → T3.
– Computador A atualiza o seu relógio com o valor do relógio