Sistemas Distribuídos
Francisco Brasileiro
Aula 3: Princípios Básicos
As figuras que aparecem nesses slides são de Veríssimo&Rodrigues, reproduzidas com o
consentimento dos mesmos.
Notações formais
• É normalmente conveniente tratar com processos ao invés
de processadores
– Um sistema distribuído é composto por N processos que executam
em M processadores
– Processadores são conectados por canais de comunicação
• A evolução do sistema é modelada por uma sequência de
eventos eip
– Um evento modifica o estado do processo p
• A história H é uma seqüência de tuplas contendo um
evento eip e o estado de p após eip
• Uma execução (run) é um conjunto de histórias dos
processos que forma o sistema distribuído
Eventos
• Eventos podem ser locais ou podem ser
trocas de mensagem
• Eventos ordenados e concorrentes
Precedência [Lamport]
• Se a e b são eventos no mesmo processo e
a precede b, então a  b
• Se a é o envio da mensagem m e b é a
recepção da mensagem m, então a  b
• Se a  b e b  c, então a  c
Estado global
• Especificação
– Se no tempo t cada processo pi está no estado
Si e as mensagens em transito no canal cij que
liga pi a pj é S(cij), então o estado global é dado
por S = {S1, S2, ... Sn} U {S(cij), 1≤i,j≤n, i ≠j}
• Como computar S internamente?
– Troca de mensagens mudará o estado do
sistema!
– Há protocolos de snapshot que resolvem este
problema
Snapshots distribuídos
Tempo e relógios
• O que é o tempo real?
– Função monotônica contínua e crescente [Newtoniano]
• O que é 1 segundo?
– Divisor de um dia solar
– Relógios atômicos
• A linha do tempo
– timestamps
– duração de intervalos
• Relógios
O papel do tempo
• Gravar e observar a localização de eventos
na linha do tempo
– seqüênciamento de eventos que formam um
estado global
– medir a duração entre dois eventos
• Forçar o futuro posicionamento de eventos
na linha do tempo
– sincronização
Medindo tempo em sistemas
distribuídos
• Como medir durações distribuídas?
• Como reconciliar diferentes linhas do
tempo?
– Ex. qual o tempo de transmissão de uma
mensagem?
• Tempo global × tempo real
Relógios locais físicos
• O hardware (rf) implementa uma função
monotônica discreta e crescente que
mapeia o tempo real t em um tempo de
relógio rf(t)
• Imperfeições de relógios físicos
– Granularidade (g)
– Taxa de desvio (r)
Propriedades de um relógio físico
• Granularidade
– Relógios físicos avançam em ticks (tk)
• g = rf(tk+1) – rf(tk)
• Taxa de desvio
– Depende da qualidade do relógio e das
condições do ambiente (ex. temperatura)
• 0 ≤ 1-r ≤ (rf(tk+1) – rf(tk))/g ≤ 1+r
Para que serve um relógio local?
• Prover timestamps para eventos locais
• Medir durações locais
– Qual o erro causado pela taxa de desvio?
– r é tipicamente na ordem de 10-5
• Definir timeouts
• Medir durações de atraso round-trip
Relógios globais
• Um relógio global é construído através da
sincronização de relógios locais por um
protocolo de sincronização de relógio
– Cada processo p cria um relógio virtual (rvp) a
partir do seu relógio local (rfp)
– Os relógios virtuais são criados de forma a
estarem sincronizados
– São resincronizados de tempos em tempos
– NTP é o protocolo mais comum para isso
Propriedades de um relógio global
• Convergência (d): quão próximo os relógios estão
sincronizados logo após uma resincronização
• Precisão (p): quão próximos os relógios se
mantêm sincronizados entre si em qualquer tempo
• Exatidão (a): quão próximos os relógios estão
sincronizados em relação a uma linha de tempo
absoluta de referência
– Requer um dispositivo de sincronização externa
(ex. GPS) em algum lugar do sistema
• Taxa de desvio (r): é a taxa instantâneo de desvio
do relógio global
Propriedades de um relógio global
Eventos
• Eventos podem ser locais ou podem ser
trocas de mensagem
• Eventos ordenados e concorrentes
Precedência [Lamport]
• Se a e b são eventos no mesmo processo e
a precede b, então a  b
• Se a é o envio da mensagem m e b é a
recepção da mensagem m, então a  b
• Se a  b e b  c, então a  c
Estado global
• Especificação
– Se no tempo t cada processo pi está no estado
Si e as mensagens em transito no canal cij que
liga pi a pj é S(cij), então o estado global é dado
por S = {S1, S2, ... Sn} U {S(cij), 1≤i,j≤n, i ≠j}
• Como computar S internamente?
– Troca de mensagens mudará o estado do
sistema!
– Há protocolos de snapshot que resolvem este
problema
Snapshots distribuídos
Tempo e relógios
• O que é o tempo real?
– Função monotônica contínua e crescente [Newtoniano]
• O que é 1 segundo?
– Divisor de um dia solar
– Relógios atômicos
• A linha do tempo
– timestamps
– duração de intervalos
• Relógios
O papel do tempo
• Gravar e observar a localização de eventos
na linha do tempo
– seqüênciamento de eventos que formam um
estado global
– medir a duração entre dois eventos
• Forçar o futuro posicionamento de eventos
na linha do tempo
– sincronização
Medindo tempo em sistemas
distribuídos
• Como medir durações distribuídas?
• Como reconciliar diferentes linhas do
tempo?
– Ex. qual o tempo de transmissão de uma
mensagem?
• Tempo global × tempo real
Relógios locais físicos
• O hardware (rf) implementa uma função
monotônica discreta e crescente que
mapeia o tempo real t em um tempo de
relógio rf(t)
• Imperfeições de relógios físicos
– Granularidade (g)
– Taxa de desvio (r)
Propriedades de um relógio físico
• Granularidade
– Relógios físicos avançam em ticks (tk)
• g = rf(tk+1) – rf(tk)
• Taxa de desvio
– Depende da qualidade do relógio e das
condições do ambiente (ex. temperatura)
• 0 ≤ 1-r ≤ (rf(tk+1) – rf(tk))/g ≤ 1+r
Para que serve um relógio local?
• Prover timestamps para eventos locais
• Medir durações locais
– Qual o erro causado pela taxa de desvio?
– r é tipicamente na ordem de 10-5
• Definir timeouts
• Medir durações de atraso round-trip
Relógios globais
• Um relógio global é construído através da
sincronização de relógios locais por um
protocolo de sincronização de relógio
– Cada processo p cria um relógio virtual (rvp) a
partir do seu relógio local (rfp)
– Os relógios virtuais são criados de forma a
estarem sincronizados
– São resincronizados de tempos em tempos
– NTP é o protocolo mais comum para isso
Propriedades de um relógio global
• Convergência (d): quão próximo os relógios estão
sincronizados logo após uma resincronização
• Precisão (p): quão próximos os relógios se
mantêm sincronizados entre si em qualquer tempo
• Exatidão (a): quão próximos os relógios estão
sincronizados em relação a uma linha de tempo
absoluta de referência
– Requer um dispositivo de sincronização externa
(ex. GPS) em algum lugar do sistema
• Taxa de desvio (r): é a taxa instantâneo de desvio
do relógio global
Propriedades de um relógio global