Sincronização de Relógios
Referências:
• Colouris et al: seção 10.3
• P. Jalote: seção 3.2
• Artigos:
– Cristian F., Probabilistic Clock Synchronization, Distributed Computing,
1989, 3: 146-158
– Arvid K., Probabilistic Clock Synchronization, Trans. on Parallel and
Distributed Systems, 474-487, May 94
© Markus Endler
1
Sincronização de Relógios
Cada processador (nó de um sistema distribuído) tem uma componente
chamada relógio.
Relógios em um S.D. podem:
– acusar horas diferentes entre sí (defasagem interna)
– acusar hora diferente da hora real externa (defasagem externa)
– ter velocidades diferentes (defasagem não ser constante)
Relógios sincronizados são necessários para uma série de aplicações:
– identificar atualidade de mensagens (uso de timestamps)
– aplicações de tempo real
– controle de versões
Enquanto algumas aplicações requerem apenas que relógios estejam
sincronizados entre sí, outras aplicações (de tempo real) requerem
também uma sincronização com o relógio real (hora global).
Nestas aplicações não basta identificar uma ordem parcial entre os
eventos ou impor uma ordem total arbitrária (consistente com a
causalidade), mas sim identificar o momento exato de ocorrência dos
eventos com relação à hora global.
© Markus Endler
2
Sincronização de Relógios
Existem dois tipos de sincronização: interna e externa
Sincronização Externa:
Objetivo: manter os valores dos relógios do sistema dentro de um limite
máximo de variação com relação à hora global (fonte externa).
Esta sincronização é necessária para executar ações em um ambiente
com requisitos rígidos de tempo (hard real-time).
Exemplo: A cada 2 segundos, o sistema deve processar um valor lido de
um sensor.
Sincronização Interna:
Objetivo: manter os valores lidos dos relógios dentro de um limite
máximo de defasagem com relação ao grupo de relógios
Esta sincronização é necessária para medir corretamente intervalos de
tempo no sistema.
Exemplo: para rejeitar mensagens com um timestamp muito antigo.
Note: Sincronização externa  sincronização interna
© Markus Endler
3
Principais Problemas
Comunicação:
 Qualquer protocolo de sincronização de relógios requer que relógios
consultem os valores dos demais relógios:
 mas a latência de comunicação pela rede precisa ser levada em
consideração
Falhas:
 Bizantinas (“relógios dual faced”)  neste caso, um relógio pode
fornecer valores distintos para diferentes processos.
 Partição da rede: subgrupo dos relógios não poderá ser sincronizado
 protocolo de sincronização deveria ignorar/descartar os valores dos
relógios com falhas
© Markus Endler
4
Modelo de Sistema para Sincronização de Relógios
Modelagem
• assume-se que todo nó da rede tem um recurso de HW (o relógio),
que é controlado por um processo
• se o relógio falha, é como se o processo controlador tivesse falhado
• todos os processos estão interligados por canais de comunicação
• relógios apresentam os valores de forma contínua
Notação:
• seja Ci(t) o valor retornado pelo processo do relógio no nó i quando
se faz uma consulta no instante real (global) t
• seja ci(T) o instante na hora real em que o processo no nó i atinge o
valor T
© Markus Endler
5
Definição do Problema
Relógios estão sincronizados se os seus valores estão próximos
uns dos outros e também estão próximos a hora real (global).
Relógios podem estar corretos ou apresentar um defeito.
Suposição:
Para cada relógio correto i,
 o valor mostrado Ci é próximo ao da hora real e
 executa com uma velocidade próxima à do relógio real (a
defasagem é limitada por uma constante).
A suposição em termos concretos:
(S1)
| dCi / dt - 1 | < 
Obs:  para um relógio de quartz é geralmente da ordem de 0.00001
Obs: Não se faz qualquer suposição sobre os relógios defeituosos;
estes podem ter um comportamento qualquer.
© Markus Endler
6
Definição do Problema
Outras suposições:
(a) comunicação é segura: que mensagens não são corrompidas
(b) comunicação é confiável: mensagens nunca são perdidas
(c) que existe um limite máximo de transmissão das mensagens
(assumido por alguns protocolos)
Uma sincronização de relógios deve satisfazer dois requisitos básicos:
(R1) a cada instante t, todos os valores dos relógios precisam estar
próximos:
| Ci(t) - Cj(t)|   para processos i,j
(R2) existe um limite  para a correção no valor Ci a cada re-sincronização
em tsynch:
| Ci(tsynch)new - Ci(tsynch)old |  
© Markus Endler
7
Protocolos de Sincronização
O objetivo de qualquer protocolo de sincronização é satisfazer os
requisitos R1 e R2.
Note que:
• por (S1) a velocidade é próxima à do relógio real e usando-se (R1)
obtém-se que todos os relógios não se distanciam significativamente
da hora real  se houverem re-sincronizações
• que R2 é necessário para evitar uma solução trivial: re-sincronizar
atribuindo um valor default (p.exemplo  i Ci(tsynch) := 0)
Existem duas classes de protocolos de sincronização:
Determinísticos: sempre conseguem sincronização com precisão
garantida
satisfazem os requisitos (R1) e (R2) , mas usam fortemente suposições
sobre limites de tempo para troca de mensagens; assumem nº máximo de
relógios com defeito
Estocásticos/Probabilísticos: sincronização com certa probabilidade
não fazem suposições sobre limites de tempo de troca de mensagens, nem
sobre nº de relógios com defeito, mas garantem precisão somente com
certa probabilidade
© Markus Endler
8
Sincronização Determinística de Relógios
Dentre os vários protocolos determinísticos propostos, veremos um a seguir:
A suposição sobre limite máximo (max) para transmissão de mensagem é usada
para detectar a ausência de mensagens (p.ex.: um relógio defeituoso pode
simplesmente não enviar mensagem).
Idéia básica:
• cada processo j envia um pedido de leitura do valor dos demais n -1 relógios e
recebe n-1 valores (Ci,  i  j)
• em seguida ajusta seu relógio usando Cj =  Ci / n
Dado que relógios podem apresentar
i
defeitos (bizantinos), esta abordagem só
funciona se as seguintes duas condições forem satisfeitas:
(C1) Quaisquer dois relógios corretos i, j produzem valores aproximadamente
iguais, Ci(t) e Cj(t)
(C2) Se Ci é um relógio correto, então todos os relógios corretos recebem
valores próximos ao valor Ci
Condições C1 e C2 são parecidas com as condições de consistência interativa e
mostram que sincronizacão determinística apresenta muitas similaridades com o
problema do consenso distribuído.
Resultados teóricos: qualquer que seja o protocolo, não pode se garantir uma
diferença entre os Ci's menor que (max - min)(1 - 1/n)
qualquer solução deterministica só funciona se o número de relógios com defeito
m < n/3, onde n é o número total de relógios
9
© Markus Endler
Um protocolo determinístico
O protocolo de Lundelius-Welch & Lynch funciona em rodadas:
• funciona se o nº de relógios defeituosos é menor do que n/3
• requer n2 mensagens para uma rodada de sincronização
• o ajuste  feito na re-sincronização é independente de n
• assume que diferença entre velocidades é limitada |dCi /dt - 1 | < 
• o relógio de hardware H(t) nunca é alterado, mas o processo controlador C
corrige o valor a ser apresentado ajustando uma função CORR, isto é, Ci(t) =
Hi(t) + CORR(t)
• todos os relógios se encontram incialmente aproximadamente sincronizados,
isto é, |ci(T0) - cj(T0)|   para i,j e onde T0 é o instante inicial
• o tempo de transmissão de uma mensagem está no intervalo
[µ -, µ + ] com µ e  fixos e para os quais vale µ > 
evento TIMER: quando um processo ativa um timer para instante T, então, em ci(T)
é recebida uma mensagem TIMER
evento START: o protocolo é iniciado através de uma mensagem START, que é
recebida por todo processo i em em ci (T0)
© Markus Endler
10
Um protocolo determinístico
A sincronização periódica funciona em rodadas, sendo que cada rodada é iniciada
quando o relógio local ci atinge um valor (Ti = T0 + i *T)
Neste momento:
• o processo manda uma mensagem para todos os demais processos contendo Ti
• espera um tempo Y até receber todas mensagens de processos nesta rodada, e
armazena no vetor ARR o momento do recebimento de cada mensagem de Cj
• descarta os m maiores e os m menores valores em ARR
• corrige o valor CORR usando o valor mediano dos valores restantes em ARR
Obs: O tempo de espera é Y = (1 + ) * (+ µ + ) Justificativa:
• quando o relógio local do processo i marcar Ti, o de outro processo k alcançará
este valor dentro de um limite de tempo máximo de 
• processo i com certeza receberá o broadcast de Ti vindo de k em um tempo real
máximo de + µ + , dado que o tempo de transmissão máximo é µ + 
• como relógios lógicos podem se defasar de uma taxa de no máximo , o tempo
de espera pela mensagem de k, medido pelo relógio de i, no máximo será
(1 + ) * (+ µ + )
© Markus Endler
11
O Algoritmo
O algoritmo tem 3 etapas (por rodada):
• antes do relógio local acusar Ti (isto é, receber um evento TIME
R) processo recolhe mensagenes de outros
• em Ti faz um broadcast para todos os outros processos e durant
e um período de tempo Y= (1 + ) * (+ µ + )) recolhe mensage
ns dos outros processos contendo cj(Ti), para ij
• após o termino de Y, faz o ajuste em seu relógio, removendo os
valores mais altos e mais baixos recebidos e pegando o valor m
ediano.
© Markus Endler
12
O Algorítmo para cada processo
loop
receive(M);
if M = (m,k) then ARR[k] = NOW();
elsif (M = START or M = TIMER) and NOT myturn then
myturn:= true
T:= NOW();
broadcast(T)
set_timer (T + (1 + ) * (+ µ + ))
else M = TIMER and myturn then
myturn := false;
AV:= middle (rem_high( rem_low(ARR,m),m)
ADJ := T + µ - AV
CORR := CORR + ADJ
set_timer (T +  T);
clear (ARR);
endif
endloop
Obs: NOW() fornece o valor de Ci,
rem_low, rem_high descartam os m menores e maiores valores respectivamente
middle obtém o valor mediano ( média)
© Markus Endler
13
Análise do Algorítmo
Funcionamento para o caso de um único relógio remoto q:
Seja AV o instante do recebimento da mensagem M=(Ti, q) no
processo p.
Como q enviou a mensagem no instante local Ti e a transmissão
de M em média dura µ, esta chegará em p em cq (Ti + µ)
Portanto a defasagem entre Cp e Cq é
Ti + µ - AV.
Logo, p precisa ajustar o seu relógio para o valor que ele julga
ser o de q, ou seja:
CORR = CORR + T + µ - AV,
onde T corresponde ao mesmo Ti da mensagem recebida M.
No algorítmo, o AV permite um ajuste segundo vários relógios
simultaneamente.
© Markus Endler
14
Análise do Algorítmo
Argumentos informais sobre a satisfação das condições (R1) e (R2):
Dado que os m valores menores e os m valores maiores de ARR são
descartados, e que temos N > 3* m,
 existe pelo menos um relógio q correto que terá mandado o mesmo valor
Ti para todos os demais exatamente em cq(Ti ) e os demais valores
estarão próximos a este valor correto
Isto garante (mostrado formalmente por Lundelius-Welch & Lynch,88)
que
AV = middle (rem_high (rem_low(ARR,m),m)
em todos os relógios corretos não irá diferir muito.
Assim, após a re-sincronizacão todos os relógios corretos terão valores
próximos.
Se N < 3 * m, não haveria como garantir que pelo menos um relógio
correto teria o seu valor em rem_high(ARR,m) rem_low(ARR,m)
© Markus Endler
15
Análise do Algorítmo
Os parâmetros µ,  e  geralmente são intrínsecos do sistema. No entanto o
parâmetro T tem uma influência sobreO sistema deve ser ajustado da
seguinte maneira:
A sincronização inicial dos relógios deve ser a melhor possível e  
Existe um limite inferior operacional para T, que deve garantir que:
• o instante local do agendamento do próximo broadcast deve ser maior do que o
novo valor do relógio local após um ajuste: Cp (tsynch(i))new < Ti + T
• a mensagem de um relógio correto q na rodada i deve chegar em p após este
ter feito o ajuste do seu relógio para a rodada anterior: cp (tsynch(i)) < cp (AVi+1)
Além disto, T precisa ser pequeno para garantir (R1) e (R2). Isto leva a seguinte
inequação, que precisa estar satisfeita por T e .
T  / 4 -  /(+ µ + ) - 2 - µ - 2
Para T fixo, tem-se
• 4 + 4 T
• ADJ  (1 +  ) (  + ) + µ
© Markus Endler
16
Sincronização Probabilística de Relógios
Ao contrário de algorítmos determinísticos, algorítmos probabilísticos:
• não assumem qualquer limite sobre tempos de transmissão de mensagens
• podem gerar uma sincronização melhor (  menor).
• no entanto, só garantem sincronização com uma certa probabilidade.
A seguir discutiremos o algorítmo proposto por Cristian1, que assume a inexistência
de relógios "dual-faced", ou seja, funciona apenas para relógios com defeitos
não-bizantinos. O principal objetivo é o de permitir a sincronização
independente de tempos de transmissão.
A idéia principal:
Estimar o valor de outros relógios a partir do conhecimento do tempo
necessário para completar uma interação tipo Request-Reply (round-trip delay)
e da marca de tempo enviada pelo relógio remoto.
Assume-se que existe um tempo mínimo de transmissão de uma mensagem, min,
que pode ser estimado para cada software de sistema S.O e para cada meio de
transmissão.
1) Cristian F., Probabilistic Clock Synchronization, Distributed Computing, 1989, 3: 146-158
2) Arvid K., Probabilistic Clock Synchronization, Trans. on Parallel and Distributed Systems,
474-487, May 94.
© Markus Endler
17
O Algorítmo
Time?
Ci
Cj
N= Ci(send(M)
Para obter o valor de um relógio remoto Ci, um processo Cj faz:
• envia uma mensagem Time? para Ci e marca o instante de envio
SND
• espera uma resposta de Ci, contendo Ci(send(M))
• seja AV =Cj (received(N))
• calcula D= (AV- SND)/2; se for muito grande, descarta N e
recomeça
• senão escolhe um valor T representando a estimativa de
Ci(recvd(N))
• efetua a correção: ADJ = T - AV
© Markus Endler
18
O Algorítmo
Sejam:
• 2D = round-trip delay medido por Cj;
• 2d= round-trip delay real (relógio global)
• t = instante real do evento receive(N) em Cj
Então:
• segundo relógio Ci, o evento recvd(N)@Cj deve ter ocorrido após T + min*(1-)
• o tempo real máximo de transmissão da resposta é 2d - min, e segundo o
relógio Ci este é: (2d - min)*(1 + ).
• Como 2d  2D*(1 + ), o valor máximo de Ci no momento de ocorrência de
recvd(N) é:
T + 2*D *(1+)*(1+) - min* (1+).
• desprezando a 2ª potência de , tem-se que o valor de Ci no momento t (
recvd(N)@j ) está no intervalo:
[T + min*(1-), T + 2*D*(1+2) - min*(1+)]
(Y)
Portanto Cj adota o valor mediano neste intervalo como estimativa T , ou seja:
T = T + D(1 +2) - min* (1+)
© Markus Endler
19
Erro
Dado que se escolheu o valor mediano no intervalo Y, o erro máximo possível é
e= D*(1+2*) - min.
(E)
Este erro pode ser visto como a precisão com a qual um relógio Cj consegue
estimar a sua defasagem com relação ao relógio Ci.
O quanto menor o round-trip delay D (que é mensurável por Cj), menor será a
precisão da estimativa.
Em particular, suponha que Cj precisa estimar o valor de Ci com precisão , então
revertendo a equação do erro, obtém se que Cj precisa descartar todas as
mensagens com round-trip delay > 2*U onde:
U = (1 - 2) * ( + min)
Ou seja, para que o relógio Cj consiga estimar o valor de Ci com uma precisão , é
possivel que o mesmo tenha que fazer várias tentativas, até que o round-trip
delay seja adequado.
Como tempos de transmisão de mensagens são arbitrários, não há garantia
nenhuma que um round-trip delay suficientemente pequeno será alcançado em
um número finito de tentativas.
Obs: Quando se consegue uma estimativa, sabe-se exatamente qual é a precisão.
Além disto, é possível ajustar a precisão às características do sistema físico.
© Markus Endler
20
Precisão
Pode-se deduzir a precisão melhor possível que pode ser obtida com este algoritmo:
Dado que min é o tempo de transmissão mínimo, tem-se que U > min. Segundo o
relógio Cj, esta é Umin = min * (1 +  )
Substituindo Umin na equação (E), obtém-se:
emin = min * (1 + ) * (1 + 2* ) - min
desprezando-se a 2ª potência em tem-se que o menor erro (precisão) possível é:
emin = 3 *  * min
A maioria dos algorítmos probabilísticos de sincronização de relógios:
• se baseiam na leitura do valor de um relógio por um outro e de estimativas
baseadas no round-trip delay.
• não requerem uma coordenação entre os relógios como no caso dos protocolos
determinísticos (pode ocorrer em pares, de forma assíncrona)
Protocolos probabilísticos podem ser facilmente estendidos para sincronização
externa. Basta que um dos relógio (o mestre) tenha como valor a hora real
(UTC)1 Periodicamente, então os demais relógios (escravos) leem o valor deste
mestre para efeito de ajuste do valor local.
UTC = Universal Coordinated Time
© Markus Endler
21
O Algoritmo de Berkeley
Adaptação do protocolo de Cristian, desenvolvido para BSD Unix [Gusella & Zatti,
1989]
•
um relógio (mestre) periodicamente consulta o valor de outros relógios a serem
sincronizados (escravos), que enviam os seus valores
•
o mestre estima o valor destes relógios (usando informação sobre round-trip
delay) e faz a média seletiva destes valores com o seu próprio valor
•
o mestre retorna para cada escravo um valor de ajuste individual (>0 ou <0) para
cada relógio (assim, evita-se a imprecisão causada pelo tempo da transmissão
da resposta)
•
esta média seletiva (“fault-tolerant average”) inclui apenas os valores de relógios
com valores próximos, contanto que o número destes relógios seja  K
 assim, descarta-se relógios com valores ou velocidades muito distintas
(relógios com defeito)
•
a precisão do protocolo depende do round-trip delay maximo aceito para a
interação mestre-escravo
•
Caso o relógio tenha falha fail-stop, outro relógio “correto” pode assumir o papel
de mestre.
© Markus Endler
22
Network Time Protocol
Enquanto o algorítmo de Berkeley é adequado para LANs e intranets, o NTP visa
prover um “Serviço de Tempo” para sincronização de relógios na Internet.
Sub-rede de Sincronização:
Stratum 2
Stratum 3
Precisão crescente
Stratum 1
NTP consiste de uma hierarquia lógica de servidores de tempo, na qual:
•
servidores primários têm uma fonte externa de tempo (relógio de rádio
provendo UTC)
•
servidores de uma camada N são fonte de sincronização para servidores da
camada N+1, e os hosts dos usuários são as folhas da árvore
•
a sub-rede de sincronização pode se reconfigurar (p.ex. se um servidor falha)
•
servidores podem se sincronizar de 2 modos: multicast, RPC e simétrico
•
servidores mais altos na hierarquia têm relógios mais precisos do que os
abaixo
© Markus Endler
23
NTP: Modos de Sincronização
Multicast:
•
deve ser usado em LANs de alta velocidade
•
periodicamente um servidor primário difunde o seu tempo para certo conjunto de
servidores, que ajustam os seus relógios assumindo delay pequeno de
transmissão
•
com este modo não se consegue alta precisão na sincronização (pode ser
suficiente!)
Chamada a Procedimento (RPC):
•
sincronização através de invocação ponto-a-ponto tipo Request-reply
•
valor recebido da consulta e estimativa do round-trip delay são usados para
ajustar o próprio relógio (como em [Cristian89])
•
adequado para servidores NTP em redes distintas; garante alta precisão
Simétrico:
•
usado para sincronização entre servidores de tempo (baixo stratum), que requer
altíssima precisão
•
servidores trocam mensagens e mantém registros dos valores
medidos/ajustados ao longo do tempo (associação) para melhorar cada vez mais
a precisão
© Markus Endler
24
NTP: O protocolo
Troca de mensagens em todos os modos usa o UDP (não-confiável).
Nos modos RPC e simétrico servidores trocam pares de mensagens, e cada
mensagem carrega os timestamps de eventos de tempo recentes.
t2
Seridor B
M
Seridor A
t1
t3
N = (t3,t2,t1)
Sejam TM eTN tempos reais
de transmissão de M e N.
t4
Se  é o offset real do relógio em B relativo ao relógio em A então
t2= t1 + TM +  e t4 = t3 + TN - 
Ao receber uma mensagem NTP, o servidor registra o momento de chegada (t4), e
usando os tempos recebidos na mensagem, calcula:
•
offset o (estimativa da diferença entre os relógios)
o = (t4 - t3 + t2 - t1)/2
•
delay d (tempo total de transmissão das duas mensagens)
d = TM + TN = (t4 - t3) + (t2 - t1)
Assim, obtém-se que  = o + (TN + TM)/2, ou o - d/2    o + d/2, delay d indica a
precisão da estimativa o.
© Markus Endler
25
NTP: O protocolo
Servidores NTP usam um algoritmo para seleção de pares (o, d) obtidos em
interações sucessivas (e recentes) com cada outro servidor.
A partir destes pares calculam a qualidade da estimativa como uma variável
estatística (dispersão de filtragem). Uma alta dispersão de filtragem indica uma
baixa confiabilidade da estimativa.
Cada servidor NTP mantém armazenados os 8 pares (o, d) mais recentes, e
estimativa de offset o correspondente ao menor valor d é selecionado.
Além disto cada servidor interage com vários outros servidores, e executa um
algoritmo de seleção de fonte de sincronização:
•
mantém registrada a precisão obtida na interação com cada outro servidor
•
difunde os dados sobre dispersão de filtragem para os demais servidores,
(permitindo que cada servidor possa calcular a sua dispersão de sincronismo
com relação ao servidor raiz)
•
eventualmente escolhe novo servidor de referência para a sincronização, que é
–
um servidor do stratus imediatamente anterior e
–
aquele que apresenta uma menor disperão de sincronismo com a raiz
O NTP consegue uma precisão da ordem de 10-2 s na Internet e 10-3 s em LANs.
© Markus Endler
26