Relogio logicos

Relógios Lógicos

November 27, 2009

Sumário

Relação Happened-Before

Relógios de Lamport

Relógios Vectoriais

Eventos
Nem sempre é necessário ter relógios sincronizados: Muitas vezes, é suficiente estabelecer uma ordem entre eventos. Um evento é a ocorrência duma acção executada por um processo: Ao longo da sua execução, um processo pode executar uma dada acção múltiplas vezes, a cada uma dessas ocorrências corresponde um evento. Assim, a execução dum processo Pi consiste numa sequência de eventos: ei0 , ei1 , ei2 , . . .

Relação Happened-Before (1/2)

Eventos num sistema distribuído podem ser ordenados usando a relação happened-before, proposta por Lamport, denotada → e definida como se segue:
HB1 se e e e são eventos que ocorrem no mesmo processo por aquela ordem, então: e → e ; HB2 se e é a transmissão duma mensagem e e a recepção dessa mensagem, então e → e ; HB3 se e → e e e → e , então e → e .

Relação Happened-Before (2/2) p1 p p
2

a

b m1 e c d m2 f

3

A relação happened-before é uma relação parcial: ¬ (a → e) ∧ ¬ (e → a) Eventos como a e e dizem-se concorrentes: a||e. A relação → captura o fluxo de informação entre eventos: indica potencial causalidade entre eventos; atenção a canais de comunicação externos/ocultos.

Lamport Clocks and Timestamps (1/3)

Além da relação →, Lamport propôs: o uso dum relógio lógico por processo, conhecido por Lamport clock ; a associação de timestamps geradas por esse relógio, Lamport timestamps, a cada evento.

A relação entre a relação → e Lamport timestamps é: e → e ⇒ L(e) < L(e )

Relógios Físicos e a Relação HB
P1 0 6 12 18 24 30 36 42 48 54 60 P2 0 8 16 24 32 40 48 56 64 72 80 (a) P3 0 10 20 30 40 50 60 70 80 90 100 P1 0 6 m1 12 18 24 30 P2 adjusts 36 its clock 42 48 m4 70 76 P1 adjusts its clock P2 0 8 16 24 32 40 48 61 69 77 85 (b) P3 0 10 20 30 40 50 60 70 80 90 100

m1

m2

m2

m3

m3

m4

Relógios físicos não sincronizados não podem ser usados para gerar