Sincronização de Relógios em Sistemas Distribuídos

Prévia do material em texto

A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 1 Hélio Crestana Guardia - 2011
Sincronização
 Sincronização entre processos é comumente necessária em 
SDs 
 Sincronização pode ocorrer baseada em tempo real ou apenas 
para prover a ordenação relativa de eventos
 Algoritmos de eleição permitem escolher um processo para 
coordenar atividades
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 2 Hélio Crestana Guardia - 2011
Sincronização
Exemplo de sincronização: make 
 Necessidade de compilação de arquivos determinada pelas 
datas de alterações das dependências
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 3 Hélio Crestana Guardia - 2011
Relógios físicos
 Monitoração da passagem do tempo em computadores é realizada por 
temporizadores
 Cristal de quartzo lapidado e usinado
 Mantido sob tensão, cristal oscila em frequência bem definida
 Registradores associados ao cristal:
 Contador
 Registrador de contenção 
 Oscilação do cristal gera decremento do valor do contador
 Ao zerar contador, interrução é gerada e valor do contador reiniciado a 
partir do registrador de contenção
 Na iniciação do sistema, data e hora são convertidas em número de ciclos 
de relógio após data conhecida
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 4 Hélio Crestana Guardia - 2011
Relógios físicos
 Sincronização dos processos locais pode ser garantida mesmo que 
relógio esteja fora de sincronismo com hora real
 Variação na frequência dos osciladores dificulta sincronização de 
relógios em diferentes computadores
 Sincronização pode requerer uso de relógios físicos externos
 Problemas:
 Como sincronizar temporizadores com relógios do mundo real?
 Como sincronizar relógios?
 Medição do tempo feita em função de eventos astronômicos
 Trânsito solar: posição do sol no ponto aparente mais alto no céu
 Dia solar: intervalo entre 2 trânsitos consecutivos
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 5 Hélio Crestana Guardia - 2011
Dia solar
 Período de rotação da Terra não é constante
 Desaceleração em função do atrito das marés e do arraste 
atmosférico
 Turbulências na profundidade da Terra também afetam rotação
 Comprimento do dia medido por valor médio para muitos dias
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 6 Hélio Crestana Guardia - 2011
Dia solar
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 7 Hélio Crestana Guardia - 2011
Relógio atômico
 Inventado em 1948
 Baseado no número de transições do átomo de césio 133
 1s = tempo para 9.192.631.770 transições, o que equivale ao 
segundo solar médio em 1948
 Atualmente, há vários relógios atômicos ativos
 Relógios informam periodicamente o número de oscilações 
ocorridas para que Bureau International de l'Heure (BIH) 
 Média dos valores determina hora atômica internacional 
(International Atomic Time – TAI)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 8 Hélio Crestana Guardia - 2011
Coordinated Universal Time: UTC
 Aumento do dia solar médio gera diferença com hora atômica
 Atualmente, 3 ms a menos que dia solar médio
 Sincronização: International Earth Rotation and Reference System (IERS) 
introduz segundos extras quando discrepância atinge 80 ms (*)
 Resultado: sistema de medição de tempo em segundos TAI constantes, em 
fase com movimento aparente do Sol
 Coordinated Universal Time – UTC (sigla nem em francês nem em inglês)
 Substitui Greenwich Mean Time, baseado em hora astronômica
 National Institute of Standard Time (Nist) usa estações de rádio de ondas 
curtas para propagar pulsos no início de cada segundo UTC
 Satélites em órbita terrestre também propagam sinal UTC
 Uso dos serviços requer conhecimento do posicionamento do gerador do 
sinal para considerar o atraso de propagação
(*) http://en.wikipedia.org/wiki/Leap_second
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 9 Hélio Crestana Guardia - 2011
Coordinated Universal Time: UTC
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 10 Hélio Crestana Guardia - 2011
Sistema de Posicionamento Global (GPS)
 Global Positioning System – GPS – permite determinar a localização 
geográfica na Terra
 Malha com 29 satélites em órbita a aprox. 20.000 km
 Cada satélite tem até 4 relógios atômicos, calibrados periodicamente
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 11 Hélio Crestana Guardia - 2011
Cálculo da posição com GPS
 2 satélites: permitem calcular posição em espaço 
bidimensional
 3 satélites permitem calcular 3 dimensões: 
latitute, longitude, altitude
Aspectos:
 ∆r: desvio no relógio do receptor em relação ao 
satélite
 xr , yr , zr: coordenadas do receptor 
(desconhecidas)
 Ti: timestamp numa mensagem enviada do 
satélite i.
 ∆i = (Tnow − Ti ) + ∆r: atraso da mensagem 
recebida do satélite I
 Distância até satélite i: di= c × ∆i (c = vel. Luz)
 Distância real = di + c Δr 
 4 sats. permitem calcular xr, yr, zr e Δr 
di=x i−x r2 y i− y r2 z i− zr2
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 12 Hélio Crestana Guardia - 2011
Sincronização de relógios
 Havendo fonte de referência externa (WWV / UTC) numa máquina, demais 
podem sincronizar-se a partir dela
 Sem WWV, cada sistema monitora próprio horário e objetivo é manter todos 
com horário aproximado
Diversos algoritmos para sincronização. Aspectos gerais:
 Cada máquina mantém temporizador que gera H interrupções por segundo
 Contador (C) na máquina p é incrementado a cada interrupção: Cp(t), 
t=UTC time. 
 Quando hora UTC é t, relógio em p é Cp(t).
 Idealmente, para cada máquina p, Cp(t)=t, ou seja dC/dt=1
 C'p(t): frequência do relógio de p no tempo t
 C'p(t)-1: defasagem do relógio; denota magnitude da diferença entre a 
frequência do relógio de p e a frequência de um relógio perfeito
 Cp(t)-t: deslocamento em relação a um horário específico t
 Atualmente, chips geram erro ~10-5 
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 13 Hélio Crestana Guardia - 2011
1−ρ dC
dt
1ρ
Sincronização de relógios
 2 relógios nunca devem diferir em mais 
do que σ unidades de tempo
 Para funcionar corretamente, relógio 
deve manter taxa de deriva inferior a ρ :
 Para relógios que derivam em direções 
opostas em relação à UTC, passado 
tempo Δt defasagem pode ser de 2 ρ Δt 
 Para manter deriva máxima δ, 
sincronização deve ocorrer no mínimo a 
cada δ/2ρ segundos
 Algoritmos de sincronização diferem na 
forma de sincronização periódica
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 14 Hélio Crestana Guardia - 2011
Network Time Protocol (NTP)
 Protocolo de horário de rede
 Sincronização a partir de servidor de tempo, que utiliza relógio 
preciso ou recebe sinais WWV
 Cada máquina pergunta o horário do servidor a cada δ /(2ρ) 
segundos
 Problema: hora informada pelo servidor é recebida com atraso
 Requer cálculo preciso do tempo de comunicação (round trip 
delay), incluindo atrasos com tratamento de interrupções e 
processamento das mensagens
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 15 Hélio Crestana Guardia - 2011
Network Time Protocol
aΘ=T 3
T 2−T 1T 4−T 3
2
−T 4=
T 2−T 1T 3−T 4
2
bδ=
T 2−T 1T 4−T 3
2
 Pares de nós calculam deslocamentode seus relógios
 Estimativa do deslocamento (offset – Θ) de A em relação a B: (a)
 Estimativa do atraso (δ): (b)
 8 pares de valores (Θ,δ) são armazenados
 Menor valor de δ é considerado a melhor estimativa para o atraso e é usado no 
cálculo do deslocamento
 Tempo, contudo, não pode ser ajustado negativamente
 Servidores são organizados em estratos
 Servidor com relógio de referência é estrato 1 (relógio opera no estrato 0)
 Quando nó A contata B, A só ajustará seu relógio se seu estrato for maior que o de B`
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 16 Hélio Crestana Guardia - 2011
Algoritmo de Berkeley
 Em algoritmos como NTP, servidor de tempo é passivo
 Berkeley Unix, servidor de tempo (daemon) é ativo e consulta 
outras máquinas para perguntar qual é a hora marcada
 Horário médio é calculado e propagado para outras máquinas
 Hora no daemon de tempo deve ser ajustada periodicamente 
pelo operador
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 17 Hélio Crestana Guardia - 2011
Algoritmo de Berkeley
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 18 Hélio Crestana Guardia - 2011
Sincronização de relógios em redes sem fio
Redes de sensores sem fio: 
 Nós com restrições de recursos
 Roteamento por múltiplos saltos é caro
 Importante otimizar algoritmos para economia de energia
Ex: Sincronização em broadcast de referência (reference broadcast 
syncronization – RBS)
 Sincronização dos relógios na rede apenas
 Abordagem semelhente à de Berkeley
 Apenas receptores sincronizam
 Remetente transmite mensagem de referência em broadcast, que permite a 
receptores ajustarem seus relógios
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 19 Hélio Crestana Guardia - 2011
Sincronização de relógios com RBS
 Nó transmite em broadcast mensagem de referência m
 Cada receptor p registra hora Tp,m em que recebeu m
 Tp,m obtida a partir de relógio clocal de p 
 Hora calculada em função do deslocamento da hora de um nó 
em relação aos demais
 Deslocamento: 
[ p , q ]=
∑
k=1
M
T p ,k−T q ,k 
M
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 20 Hélio Crestana Guardia - 2011
Componentes do atraso com RBS
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 21 Hélio Crestana Guardia - 2011
Relógios lógicos
 Para muitas aplicações sincronização de relógios requer apenas que nós 
concordem com hora atual, que pode estar desvinculada da hora real
 Relógios definidos como relógios lógicos
 Noção de ordenação dos eventos é relevante
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 22 Hélio Crestana Guardia - 2011
Relógios lógicos de Lamport
 Para sincronizar relógios, Lamport definiu uma relação 
denominada “aconteceu antes” - happened-before relation 
If a and b are two events in the same process, and a comes before b, then a → b
If a is the sending of a message, and b is the receipt of that message, then a → b 
If a → b and b → c, then a → c (operação transitiva)
Se dois eventos, x e y, acontecem em processos diferentes, que não trocam mensagens, 
(nem idiretamente via terceiros), então x → y não é verdadeira, mas y → x também 
não é. 
Eventos nesse caso, são concorrentes.
Note: This introduces a partial ordering of events in a system with concurrently 
operating processes.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 23 Hélio Crestana Guardia - 2011
Relógios lógicos de Lamport
 Necessidade: noção de tempo em que, para cada evento a, seja possível 
designar um valor de tempo C(a) com o qual todos os processos concordam
 Propriedades:
 Timestamp C(e) associado a cada evento, satisfazendo as sequintes 
propriedades:
 P1: se a e b são 2 eventos num mesmo processo e a→b, então C(a) < C(b). 
 P2: se a corresponde ao envio de uma mensagem e b ao recebimento dessa 
mensagen, também C(a) < C(b)
 Relógios devem sempre ser ajustados de maneira positiva
 Problema: como associar timestamps se não há processos globais?
 Cada mensagem transporta tempo de envio conforme relógio do remetente
 Quando mensagem chega e o relógio do receptor mostra tempo inferior ao 
envio, receptor adianta relógio para uma unidade a mais que envio
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 24 Hélio Crestana Guardia - 2011
Relógios lógicos de Lamport
Cada processo Pi mantém um contador local Ci, ajustado de 
acordo com as seguintes regas:
 Para quaisquer eventos sucessivos em Pi, Ci é incrementado 
em 1.
 Cada vez que uma mensagem m é enviada por processo Pi, 
mensagem recebe timestamp ts(m) = Ci
 Quando uma mensagem m é recebida por um processo Pi, Pi 
ajusta o contador local Cj para max {Cj,ts(m)}
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 25 Hélio Crestana Guardia - 2011
Relógios lógicos de Lamport
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 26 Hélio Crestana Guardia - 2011
Relógios lógicos de Lamport no middleware
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 27 Hélio Crestana Guardia - 2011
Ex Lamport: multicast ordenado
Cenário: BD replicado em vários sites
 Consultas: respondidas do site mais próximo
 Atualizações: realizadas em todas as cópias
Exemplo de operação:
 Atualização 1: depósito $ 100
 Atualização 2: cálculo 1% juros
Problema potencial: operações em ordem distinta nas cópias = inconsistência
 Situação requer multicast totalmente ordenado: todas as mensagens são 
entreguem em ordem para cada receptor (cópia)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 28 Hélio Crestana Guardia - 2011
Multicast totalmente ordenado
 Uso de relógio lógico de Lamport
 Envio de mensagens em multicast; cópia é entregue também à origem 
 Todas as mensagens são entreguem em ordem para cada receptor (cópia)
 Mensagens contêm timestamp do remetente
 Mensagens recebidas são colocadas em fila local ordenada por timestamps
 Receptor envia mensagens multicast de reconhecimento aos outros 
processos
 Mensagens só podem ser entregues à aplicação quando estão no início da 
fila e já tiverem sido confirmadas por todos os outros processos.
 Cada processo tem a mesma cópia da fila e mensagens são entregues na 
mesma ordem
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 29 Hélio Crestana Guardia - 2011
Ex. problema na atualização de cópias
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 30 Hélio Crestana Guardia - 2011
Relógios vetoriais
 Relógios lógicos de Lamport: se evento a 
aconteceu antes de b, C(a) < C(b)
 Entretanto, C(a) < C(b) não garante que a 
ocorreu antes de b
 Relógios de Lamport não capturam 
causalidade
 Evento a: m1 é recebida em T = 16; Evento 
b: m2 é enviada em T =20.
 We cannot conclude that a causally 
precedes b.
Causality is the relationship between an event (the cause) and a second event (the effect), where the second event is 
understood as a consequence of the first. Though the causes and effects are typically related to changes or events, 
candidates include objects, processes, properties, variables, facts, and states of affairs. (http://en.wikipedia.org/wiki/Causality)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 31 Hélio Crestana Guardia - 2011
Relógios vetoriais
 Causalidadespodem ser capturadas com Relógios Vetoriais: VC
 VC(a) designado a um evento a indica que: se VC(a) < VC(b), para um 
evento b, então evento a precede (por causalidade) evento b
 Cada processo Pi tem um relógio vetorial Vci[1..n]
 VCi[i] = relógio local de Pi, incrementado antes de cada novo evento local
 VCi[j] indica o número de eventos que processo Pi sabe que ocorreram no 
processo Pj (ou seja, o tempo local em Pj)
 Quando Pi envia uma mensagem m a j : 
– VCi[i] = VCi[i] +1
– ts(m) = VCi[i] 
– VCi é enviado junto com m; demais valores em VCi (!VCi[i]) indicam eventos 
que ocorreram antes de m 
 Ao receber mensagem, recipiente Pj sabe timestamps de Pi e atualiza VCj:
(1) VCj[k] = max{VCj[k], ts(m)[k]}, para todo k
(2) VCj[j] é incrementado em 1.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 32 Hélio Crestana Guardia - 2011
Relógios vetoriais
 Para ts(a), ts(a)[i]-1 indica o número de eventos processados em Pi que 
precedem a por causalidade
 Relógios vetoriais permitem envio multicast ordenado
 Mensagem só é entregue se todas as precedentes já foram recebidas
 Pj retarda entrega de m até que:
 ts(m)[i] = VCj[i]+1
 ts(m)[k] ≤ VCj[k], para k = i.
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 33 Hélio Crestana Guardia - 2011
Relógios vetoriais
 Entrega de m* (1,1,0) recebida em P2 (0,0,0) é retardada até que m(1,0,0) tenha sido 
recebida.
 m* (x,1,y) indica que m* foi gerada como evento 1 em P1
 m* (x,1,y) indica que evento x=1 já tinha ocorrido quando m* foi gerada
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 34 Hélio Crestana Guardia - 2011
Exclusão mútua
 Questão: concorrência a colaboração entre vários processos em SDs 
 Como prover exclusão mútua?
– Via servidor centralizado
– Usando algoritmo completamente descentralizado, com sistema peer-to-
peer
– Através de algoritmo distribuído, sem topologia específico
– Com solução completamente distribuída, usando um anel lógico
 Abordagens podem ser baseadas na passagem de tokens (fichas) ou em 
permissões
 Mecanismo de tokens garante uso disciplinado do recurso mas pode 
envolver procedimento complexo em caso de perda do token. 
 Questões: inanição, deadlocks, recuperações, escalabilidade, ...
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 35 Hélio Crestana Guardia - 2011
Exclusão mútua
Algoritmo centralizado
 Um processo é eleito como coordenador
 Processos que querem acessar recurso compartilhado enviam mensagem de 
requisição ao coordenador
 Se nenhum outro processo estiver usando recurso, coordenador devolve 
resposta com permissão
 Quando recurso está em uso, permissão é negada. Coordenador abstém-se 
de responder ou envia resposta negativa
 Quando recurso é liberado, coordenador envia mensagem de liberação a 
primeiro processo bloqueado
 Concessões ocorrem na mesma ordem das requisições
 Coordenador é ponto de falha único e pode ser gargalo para desepenho
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 36 Hélio Crestana Guardia - 2011
Exclusão mútua: algoritmo centralizado
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 37 Hélio Crestana Guardia - 2011
Exclusão mútua: algoritmo descentralizado
 Princípio: cada recurso é replicado n vezes e cada cópia possui seu 
coordenador
 Acesso requer votação majoritária, com resposta de m > n/2 
coordenadores
 Coordenador também informa ao requisitante quando não der 
permissão para acessar recurso porque já a concedeu a outro processo
 Falha de coordenador pode ser recuperada rapidamente, mas perde-se 
informações sobre permissões concedidas
 Quando permissão é negada (processo não consegue maioria), 
requisitante desiste depois de um tempo e volta a tentar novamente
 Problemas: 
– Com competição é elevada, é possível que nenhum processo obtenha 
maioria necessária
– Ao recuperar-se de falha, coordenador perde informações sobre 
concessões anteriores e pode conceder permissão a outro solicitante
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 38 Hélio Crestana Guardia - 2011
Exclusão mútua: algoritmo descentralizado
Robustez do sistema
 p = probabilidade de que um coordenador se reinicie num intervalo ∆t
 Acesso com exclusão mútua requer m > n/2 confirmações de coordenadores
 Probabilidade de que k nós reiniciem:
 Para falha, 2m – n (???) coordenadores devem reiniciar: 
Para p=0.001, n=32, m=0.75n, pv <10−40
P [violação ]= ∑
k=2m−n
n
[mk ] pk 1− pm−k
P [k ]=[mk ] pk 1− p m−k
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 39 Hélio Crestana Guardia - 2011
Exclusão mútua: algoritmo distribuído
Ricart e Agrawala
Baseado na ordenação total de todos os eventos no sistema
Ordenação pode ser obtida com algoritmo de Lamport
Processo que quer usar recurso monta mensagem com nome do recurso, 
número de processo e instante atual
Mensagem é enviada a todos os processos, incluindo o próprio (envio deve ser 
confiável)
Ao receber mensagem, processo:
 Envia mensagem de OK se não estiver usando o recurso e não quiser acessá-lo
 Se estiver usando o recurso, não responde e coloca pedido numa fila
 Se receptor espera pelo recurso, compara timestamps da sua requisição e da 
recebida. Se recebida for mais antiga, responde OK; senão insere pedido na fila
Concessões são enviadas apenas quando processo que recebeu requisição não 
está interessado no uso do recurso, ou 
Receptor está esperando pelo uso do recurso mas tem menor prioridade de uso 
que o requisitante (identificada pelos timestamps das requisições)
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 40 Hélio Crestana Guardia - 2011
Exclusão mútua: algoritmo distribuído
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 41 Hélio Crestana Guardia - 2011
Exclusão mútua: token ring
 Criação de anel lógico entre os processos
 Posições no anel podem ser alocadas em ordem numérica de 
endereços de rede ou ourtras formas
 Ordem não é relevante mas processos precisam conhecer 
sucessores no anel lógico
 Processo 0 recebe ficha (token) na iniciação do anel; ficha é 
passada entre os nós e dá direto de uso do recurso
 Processo que não quer usar recurso apeans repassa a ficha
 Não é permitido usar o recurso imediatamente após uso
 Necessidade de recomposição do anel em caso de falha
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 42 Hélio Crestana Guardia - 2011
Exclusão mútua: token ring
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 43 Hélio Crestana Guardia - 2011
Comparação de algoritmos de exclusão mútua
 Descentralizado: k = número de tentativas de concessão de m servidores
 Distribuído: (n-1) pedidos + (n-1) concessões
 Token ring: token pode, eventualmente, circular por tempos indeterminados 
(∞) sem que alguém esteja interessado
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 44 Hélio Crestana Guardia - 2011
Posicionamento Global de Nós
 Informações de localização podem ser úteis em algoritmos distribuídos: 
roteamento, multicasting, posicionamento de dados, buscas, etc.
 Dificuldade para localização de nós cresce com aumento do número de nós 
 Redes de sobreposição geométrica permitem determinar posições geográficas de nós 
em espaço m-dimensional
 Distância entre nós nesse espaço reflete métrica de desempenho
 Ex: distância pode corresponder a latência entre nós: tempo para mensagem irde 
um nó a outro e vice-versa
 Aplicações incluem: localização de melhor réplica da dados, roteamento baseado 
em posição, multicast, etc. 
 Posicionamento num espaço m-dimensional requer medições de distância a m+1 
outros nós em estejam em posições conhecidas
 De maneira semelhante ao GPS, nó P pode calcular suas coordenadas (Xp, Yp) 
resolvendo três equações com duas incógnitas
 di corresponde a medir a latência entre P e nó em (Xi,Yi)
 Latência requer reposicionamento diferente ao longo do tempo
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 45 Hélio Crestana Guardia - 2011
Posicionamento Global de Nós
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 46 Hélio Crestana Guardia - 2011
Posicionamento Global de Nós
 Medições podem variar e cálculos de posições pelas posições de outros nós 
podem incluir erros e imprecisões
 Ex.: distância R ↔ P != R ↔ Q + Q ↔ P
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 47 Hélio Crestana Guardia - 2011
Algoritmos de eleição
 Algoritmos distribuídos comumente requerem que um processo aja como 
coordenador, iniciador ou que desempenhe papel especial
 Em alguns sistemas, coordenador é escolhido manualmente, como no caso 
de servidores de arquivo
 Escolha manual corresponde a solução centralizada, com único ponto de 
falha
 Em geral, não importa qual nó desempenhará papel especial
 Algoritmos de eleição comumente selecionam processo baseando-se em 
atributo, como nos identificadores
 Escolha dinâmica do coordenador é desafio
 Como resultado da eleição, todos os processos devem concordar em quem é 
o novo coordenador
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 48 Hélio Crestana Guardia - 2011
Algoritmo Bully (do valentão)
 Cada processo possui um identificador, que caracteriza seu “peso”
 Processo com maior peso (prioritário) deve ser escolhido coordenador
 Qualquer processo pode iniciar uma eleição caso detecte a ausência do 
coordenador
 Para iniciar eleição, processo p que detecta falha envia mensagem a todos 
os processos com identificadores mais altos que o seu
 Se nenhum processo responder, p passa a ser o novo coordenador
 Se algum processo com identificador maior responder, este assume o 
controle da eleição e, eventualmente, a coordenação
 Ao receber mensagem de eleição, processo envia mensagem de confirmação 
(OK) ao remetente para indicar que está vivo e assumirá o poder
 Novo coordenador inicia atividades enviando notificação aos demais, 
dizendo que asumiu o poder
 Quando processo que estava inativo é reativado, convoca eleições. Se for o 
mais prioritário, assume o poder
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 49 Hélio Crestana Guardia - 2011
Eleição com algoritmo Bully
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 50 Hélio Crestana Guardia - 2011
Eleição com algoritmo de anel
 Processos são organizados em um anel lógico e cada nó conhece seu 
sucessor
 Nós estão física ou logicamente ordenados
 Processo com maior prioridade deve ser eleito coordenador
 Qualquer processo pode iniciar eleição, enviando mensagem para seu 
sucessor
 Cada nó, incluindo o inicial, inclui seu identificador na mensagem de 
eleição
 Se sucessor não está ativo, mensagem é passada ao próximo na lista. 
 Algorimto prossegue até que mensagem circule e chegue ao candidato que 
iniciou a eleição
 Novo coordenador é identificado e mensagem circula novamente, indicando 
quem é o novo coordenador quais são os processos ativos
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 51 Hélio Crestana Guardia - 2011
Eleição com algoritmo de anel
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 52 Hélio Crestana Guardia - 2011
Eleições em ambiente sem fio
 Eleições geralmente consideram que troca de mensagem é confiável e que 
topologia da rede não muda
 Premissas não são verdadeiras em redes móveis ad hoc
Possível abordagem para redes (de sensores) sem fio:
 Qualquer nó da rede, denominado fonte (source), pode iniciar eleição, enviando 
mensagem de ELEIÇÃO aos vizinhos imediatos (nós que estão ao seu alcance)
 Ao receber mensagem de eleição pela primeira vez, nó associa remetente como seu 
pai (Q) e envia mensagem de ELEIÇÃO a todos os vizinhos imediatos, exceto pai.
 Ao receber mensagem de ELEIÇÃO de outro nó, que não o pai, nó apenas envia 
mensagem de confirmação de recebimento
 Cada nó (R) espera confirmações dos demais para quem enviou notificação. Ao 
receber todas, envia confirmação ao pai (Q). 
 Ao reportar ao pai, nó informa estado dos recursos locais, como tempo de vida útil 
da bateria e outras capacidades
 Cada nó reporta ao pai uma indicação do nó que tem a melhor capacidade
 No final, nó fonte (source) propaga informação do líder em broadcast para demais
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 53 Hélio Crestana Guardia - 2011
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 54 Hélio Crestana Guardia - 2011
Eleições em sistemas de grande escala
 Há situações em que vários nós devem ser selecionados
 Ex: seleção de superpeers (superpares) em redes peer-to-peer
 Aspectos
 Nós normais devem ter baixa latência no acesso a superpares
 Superpares devem estar distribuídos uniformemente pela rede overlay
 Deve haver uma porção definida de superpares em relação ao total de nós
 Cada superpar não deve servir mais do que um número fixo de nós normais
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 55 Hélio Crestana Guardia - 2011
Eleições em sistemas de grande escala
 Para sistemas baseados em DHT:
 Reservar fração do espaço de identificadores para superpares: primeiros k bits 
[log2(N)]
 Para N nós, em média 2k−mN superpares 
(ex.: k=3, m=8, SP=2-5N=N/32=256/32=16)
 Superpar responsável por chave p: p AND 11···1100···00
 Para sistemas baseados em Gossiping:
 Posicionamento dos superpares uniformemente em espaço m-dimensional
 Fichas (N) são distribuídas aleatoriamente entre os nós
 Presença de ficha faz demais de “afastarem” da região
 Se todas as fichas exercem a mesma força de repulsão, disseminação ocorre de 
maneira distribuída na rede
 Se perceber que o conjunto de forças agindo sobre um nó excede um limite 
(threshold), ficha é movida na direção das forças resultantes
 Ao manter ficha por determinado tempo, nó é promovido a superpar
A. S. Tanenbaum, M. Van Steen. Sistemas Distribuídos: Princípios e paradigmas – Cap 6: Sincronização / 56 Hélio Crestana Guardia - 2011
Eleições em sistemas de grande escala
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56