PROBABILISTC CLOCK SYNCHRONIZATION
Agenda:
•Notas introdutórias
•Pressupostos
•Tempo de um relógio remoto
•Tempo de um relógio remoto com
precisão especifica
•A concretização
•Conclusões
André Ribeiro
Claudia Carvalho
Nuno Paiva
Onde está o tempo exacto?
• GMT-Rotação da Terra
• TAI - Frequência de oscilações
atómicas (celsium-133)
• UTC – Universal Time
Coordinated
Mais info. http://www.gb.nrao.edu/~rfisher/Ephemerides/times.html
Porquê o tempo exacto?
• Quando ocorreu um evento
• Quanto tempo demorou
• Qual ocorreu primeiro
Tipos de relógios utilizados
• Relógios físicos
• Relógios lógicos
O que fazer para acertar o relógio?
• Equipamento dedicado:
– WWv
– GPS
– Linha telefónica
• Recursos existentes:
– Ligação em rede
• Acerto gradual vs Abrupto
Métodos de acerto
• Métodos de acerto:
– Push
– Pull
• Algoritmos por SW:
– Convergência
• C/média
• S/média
– Consistência
Porquê um método probabilistico
median delay
min
delay
Trabalhos anteriores
• Assume-se a existência de um limite máximo no
atraso (max) em que n relógios não se sincronizam
com uma precisão melhor do que (max-min) (11/n);
• Estimula-se um timeout (maxp) de forma a que o
processo não fique eternamente à espera de
resposta em que a melhor sincronização alcançada
é caracterizada como sendo 4(maxp-min);
Assunções em Relógios,
Processos e Comunicação
• Subentende-se que um relógio físico (HC) que
mostra o tempo (HC(t’)) em determinado tempo
real (t’), permanece correcto num tempo posterior
(t >t’), se se encontrar no intervalo[t,t’] com um
erro no máximo de (t-t’) em que  é a variação
máxima do relógio em relação ao tempo real:
(t-t’)- (t-t’) HC(t)-HC(t’)  (t-t’)+ (t-t’);
• Ignoram-se valores como 2 ;
• Quaisquer dois relógios podem variar entre si até
2;
2
-
tempo do
relógio1
1
tempo real
+
tempo do
relógio2
• Escolha de um timeout (maxp);
• Uma falha no relógio ocorre quando a clock
condition é violada:
– Crash (o relógio pára);
– Falhas no timing (o contador do relógio acelera ou
atrasa muito);
– Falhas Bizantinas (o contador apresenta valores errados
por alguns dos seus bits se encontrarem sempre com o
mesmo valor);
• Assume-se que entre a ocorrência de um timeout e
o pedido de interrupção não decorre nenhum
tempo.
Leitura de um relógio remoto
P
Q
(“time=”,T)
D
(“time=?”)
• Teorema: Se os relógios P e Q estão
correctos, o valor mostrado pelo relógio de
Q quando P recebe a mensagem (“time=”,T)
encontra-se no intervalo
[T+min(1-), T+2D(1+2)-min(1+)].
• Demonstração:
1. 2d = (min+)+(min+) = 2min++
min+ - Delay real aquando da mensagem (“time=?”)
min+ - Delay real aquando da mensagem (“time=”,T)
  0,   0
2.0    2d-2min
3.CQ(t)  [T+(min+)(1-), T+(min+)(1+)]
4.CQ(t)  [T+min(1-), T+(2d-min)(1+)]
CQ(t)  [T+(min+0)(1-), T+(min+2d-2min)(1+)]
CQ(t)  [T+min(1-), T+(2d-min)(1+)]
5.d  D(1+)
6.CQ(t)  [T+min(1-), T+2D(1+2)-min(1+)] c.q.d.
CQ(t)  [T+min(1-), T+(2d(1+)-min(1+)]
CQ(t)  [T+min(1-), T+2(D(1+))(1+)-min(1+)]
CQ(t)  [T+min(1-), T+2(D+D)(1+)-min(1+)]
CQ(t)  [T+min(1-), T+(2D+2D)(1+)-min(1+)]
CQ(t)  [T+min(1-), T+(2D+2D+2D+2D2)-min(1+)]
CQ(t)  [T+min(1-), T+(2D+4D+2D2)-min(1+)]
CQ(t)  [T+min(1-), T+2D(1+2+2)-min(1+)]
CQ(t)  [T+min(1-), T+2D(1+2)-min(1+)]
• Este teorema indica que P consegue determinar
um intervalo que contém o valor do relógio Q se
medir o round trip delay 2D. Esse valor pode ser
qualquer ponto nesse intervalo.
• P deve minimizar o erro máximo que comete ao
ler o relógio de Q, estimando CQ(t) através da
escolha da função CPQ(T,D) para ser o ponto
médio do intervalo.
7.CPQ(T,D)  T+D(1+2)-min
8.e = D(1+2)-min  Quanto mais pequeno for o round trip delay,
menor será o erro de P ao ler o relógio de Q
Leitura de um Relógio Remoto
com uma Precisão Específica
P terá de rejeitar todas as leituras cujo round trip
delay seja superior a 2U de forma a obter um erro
de leitura mínimo () em que
9. U = (1-2) (+min) 
Quanto mais próximo o U estiver de
min melhor é a precisão da leitura de P
Contudo, uma vez que na pior das situações o
timer de P pode-se encontrar com uma velocidade
1+, o timeout escolhido por P deve ser maior que
10.Umin = min(1+)
para assegurar que entre o envio da mensagem e a
sua recepção haja um delay real de pelo menos
min. Para obter a melhor precisão possível, o
timeout deve ser o mais próximo possível de Umin.
De acordo com a fórmula 8, a melhor precisão
possível é
11.emin = 3min
D(1+2 )-min
min(1+)(1+2 )-min
min(1+2 + +2 2)-min
min+3 min-2 2-min
3min
2  Variação relativa entre o relógio de P e o de Q
enquanto a mensagem (“time=”,T) “viaja” entre Q e P
  Erro de P no estabelecimento de um timeout
De forma a impedir que P fique eternamente a
tentar ler o relógio de Q, há que definir um valor
máximo de tentativas sucessivas de leitura (k) em
que
12.
2
m
(1   )
é a média de mensagens para estabelecer uma
ligação entre dois processos.
RELÓGIOS CONTINUAMENTE
AJUSTÁVEIS
• Para compensar o facto de a velocidade de um
relógio físico (HC), não ser ajustável, é
implementado um relógio lógico (C) em
software:
C(t)  HC(t)+A(t)
• Para evitar “saltos” no tempo, A deve ser uma
função contínua de tempo:
A(t) = m*HC(t)+N
em que, m = (M-L)/ e N = L-(1+m)*HC
 - parâmetro de amortização.
Protocolo de sincronização Master-slave
• O desvio máximo (es) entre um slave e um relógio
externo é: es = em + ms.
• Protocolo de sincronização em = ao protocolo ms.
• Como existe ligação dedicada, eem=D-min
• considerando d (round trip delay) < 10s e = 10-5

1) CM(t)  [T+min, T+2D-min]
2) e = D-min
O algoritmo
S
tmedido
M
e  t
at rapport:
e  D-min
C(t)=HC(t)
C(t)=HC(t)+A(t)
W

t
 ms  ( D  min)

DNA  (1   )
 (1   )kW 



treal
Características e melhoramentos
• DNA é variável.
– D ~= min => DNA grande
– D ~= U-min => DNA pequeno
• Se se escolher U ~= min => grande precisão´e muitas
mensagens
• Se se escolher U ~= atrazo maximo, bastam 2 mensagens.
Algoritmo Deterministico.
• São permitidas até k-1 tentativas falhadas
• Distribuição das mensagens de sincronização
• Se estimar ró estaticamente aumento o DNA
• Aumentar e diminuir U automaticamente.