PROBABILISTC CLOCK SYNCHRONIZATIONPROBABILISTC CLOCK SYNCHRONIZATION

André RibeiroClaudia CarvalhoNuno Paiva

b

a

be

mc

4

2

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

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

min

median delay

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) (1-1/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;

• Escolha de um timeout (maxp);

tempo realtempo do relógio1

tempo do relógio2

1- +

2

• 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 remotoP Q

D

(“time=?”)

(“time=”,T)

• 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+2D2)-min(1+)]

CQ(t) [T+min(1-), T+(2D+4D+2D2)-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 CP

Q(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 = 3min

D(1+2 )-min

min(1+)(1+2 )-min

min(1+2 + +2 2)-min

min+3 min-2 2-min

3min

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.

é a média de mensagens para estabelecer uma ligação entre dois processos.

)1(

2

m

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)+Nem 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

M

S

at rapport:e D-min

te

t

W

C(t)=HC(t)

C(t)=HC(t)+A(t)

treal

tmedido

kW

DmsDNA )1(

min)()1(

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.