Sincronização de Relógios

© Markus Endler 1

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 2


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 3


Existem dois tipos de sincronização: interna e externaSincronizaçã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 4

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 5

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 6

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 7

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)| paraprocessos 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 8

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

garantidasatisfazem 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 probabilidadenã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 9

Sincronização Determinística de RelógiosDentre 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 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

i

© Markus Endler 10

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 11

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 12

O Algoritmo

O algoritmo tem 3 etapas (por rodada):• antes do relógio local acusar Ti (isto é, receber um evento

TIMER) processo recolhe mensagenes de outros• em Ti faz um broadcast para todos os outros processos e

durante um período de tempo Y= (1 + ) * (+ µ + )) recolhe mensagens dos outros processos contendo cj(Ti), para ij

• 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 mediano.

© Markus Endler 13

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:= trueT:= 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 + µ - AVCORR := CORR + ADJset_timer (T + T);clear (ARR);

endifendloop

Obs: NOW() fornece o valor de Ci, rem_low, rem_high descartam os m menores e maiores valores respectivamentemiddle obtém o valor mediano ( média)

© Markus Endler 14

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 15


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 16


Os parâmetros µ, e geralmente são intrínsecos do sistema. No entanto o parâmetro Ttem uma influência sobreO 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 17

Sincronização Probabilística de Relógios

1) Cristian F., Probabilistic Clock Synchronization, Distributed Computing, 1989, 3: 146-1582) Arvid K., Probabilistic Clock Synchronization, Trans. on Parallel and Distributed Systems,

474-487, May 94.

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 Cristian , 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

© Markus Endler 18

O Algorítmo

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

Cj CiTime?

N= Ci(send(M)

© Markus Endler 19

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 20

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 21

PrecisãoPode-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) Periodicamente, então os demais relógios (escravos) leem o valor deste mestre para efeito de ajuste do valor local.

1

UTC = Universal Coordinated Time

© Markus Endler 22

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 23

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:

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

Stratum 1

Stratum 2

Stratum 3

Precisão crescente

© Markus Endler 24

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 25

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.

Seridor B

Seridor A

M N = (t3,t2,t1)

t4t1

t2 t3

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.

Sejam TM eTN tempos reais de

transmissão de M e N.

© Markus Endler 26

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.

Documents

Sincronização de Relógios