5 - Coordenação pptx

Prévia do material em texto

5 - Coordenação
eduardo@dca.ufrn.br
2
No último 
Capítulo
1. Fundamentos
○ Modelo OSI
○ Middleware
○ Tipos de Comunicação
2. RPC
3. Comunicação Orientada à 
Mensagens
4. Comunicação Multicast
Neste Capítulo
1. Sincronização de Relógios
2. Relógios Lógicos
3. Relógios Vetoriais
4. Exclusão Mútua
5. Eleição de Líder
3
Sincronização de 
Relógios
4
Motivação
Sincronização de Relógios
● Relógios são essenciais em computação
○ Medir o tempo
○ Identificar ordem de eventos
■ transações em BD (mercado financeiro)
■ ordem de posts/mensagens em rede social 
● Em sistemas centralizados, o tempo é claro e único: uma chamada ao 
sistema retorna uma hora sempre igual ou crescente. 
● Em sistemas distribuídos, manter esse acordo é um grande desafio.
5
Sincronização de Relógios
● make
○ Usado para compilar apenas os arquivos alterados, com base nas marcas de tempo dos 
arquivos-fonte e objetos.
○ Compara os tempos de modificação dos arquivos: se o código-fonte é mais recente que o 
objeto, recompila; se não, ignora.
○ Em sistemas distribuídos, se os relógios não estão sincronizados, pode ocorrer que um 
arquivo-fonte alterado pareça ser mais antigo que o objeto, o que impede a recompilação 
necessária e gera executáveis incorretos.
6
É possível sincronizar todos os relógios de 
um Sistema Distribuído?
7
Relógios Físicos em Computadores
8
● 🕒 Temporizadores Internos (Cristais de Quartzo):
○ Computadores não têm relógios no sentido tradicional, mas sim temporizadores baseados em 
cristais de quartzo que vibram a frequências bem definidas.
○ Cada cristal está associado a um contador. A cada oscilação, o contador é decrementado. Ao 
chegar a zero, uma interrupção é gerada e o contador é recarregado — isso define o "tick" do 
relógio.
○ Ao iniciar o sistema, o tempo atual é configurado pelo usuário e armazenado na memória. A 
cada tick, o tempo armazenado é incrementado, mantendo o relógio de software atualizado.
● ✔ Em Computadores Isolados:
○ Pequenos desvios no relógio não causam problemas, pois todos os processos usam o 
mesmo tempo relativo.
Relógios Físicos 
9
● ⚠ Clock Skew:
○ Quando há múltiplos computadores, cada um com seu próprio cristal, os relógios 
inevitavelmente se dessincronizam com o tempo — esse desvio é chamado clock skew.
○ Com clock skew, programas que dependem de timestamps corretos entre máquinas podem 
falhar, como no exemplo do make.
● ⏱ Necessidade de Relógios Externos:
○ Em sistemas que exigem tempo real, o uso de relógios físicos externos é necessário. Mas 
isso traz dois problemas: como sincronizá-los com o mundo real, e entre si.
○ A referência global usada é o UTC 🌍 (Tempo Universal Coordenado), transmitido por rádios 
e satélites com precisões variadas, indo de milissegundos a dezenas de nanossegundos.
Algoritmos de Sincronização de Relógios
10
● Se uma máquina tem acesso ao UTC, o objetivo é sincronizar as outras com 
ela. Se nenhuma tem, tenta-se manter todas próximas entre si. Há muitos 
algoritmos propostos para isso.
● Todos os relógios se baseiam em osciladores harmônicos. Os mais precisos 
são os atômicos (baseados em césio-133); os comuns usam quartzo, que é 
estável, mas menos preciso.
Algoritmos de Sincronização de Relógios
11
● Ideia geral
○ O relógio de software é derivado do relógio de hardware: a cada interrupção gerada pelo 
temporizador (ex. 100 vezes por segundo), incrementa-se um contador.
○ Chamamos esse contador de Cₚ(t), o valor do relógio de software da máquina p no tempo t. 
○ O objetivo da sincronização é manter a diferença entre os relógios de qualquer par de 
máquinas menor que um limite π (precisão)
■ ∀t, ∀p, q: |Cp(t) − Cq(t)| ≤ π
○ Se o objetivo for manter a proximidade com o UTC, falamos de acurácia (α):
■ ∀t, ∀p: |Cₚ(t) − t| ≤ α
○ Se todos os relógios são precisos (internamente sincronizados), então são acurados dentro 
do dobro do erro permitido: π = 2α. Mas a precisão interna não garante acurácia em relação 
ao UTC.
○ Idealmente, todos os relógios mostrariam Cp(t) = t sempre, com α = π = 0. Mas, na prática, 
todos sofrem clock drift, ou seja, oscilações causadas por variações ambientais e 
imperfeições do cristal.
Algoritmos de Sincronização de Relógios
12
● O erro relativo aproximado dos temporizadores baseado em quartzo é 
10-6 segundos por segundo, ou 31.5 segundos por ano
Network Time Protocol
13
NTP
1ª abordagem para sincronização
Network Time Protocol
14
● Um método comum de 
sincronização é o cliente consultar 
um servidor de tempo (com UTC 
ou relógio preciso). 
● O desafio está em estimar o atraso 
da mensagem para corrigir o tempo 
de forma útil.
Network Time Protocol
15
● Funcionamento
1. Máquina cliente envia mensagem para o 
servidor de tempo perguntando pela 
hora atual
2. Servidor de tempo responde o mais 
rápido possível, com uma mensagem 
contendo a hora atual CUTC
3. O Cliente obtém uma resposta e ajusta 
seu relógio
● Problemas?
Network Time Protocol
16
● Funcionamento
1. Máquina cliente envia mensagem para o 
servidor de tempo perguntando pela 
hora atual
2. Servidor de tempo responde o mais 
rápido possível, com uma mensagem 
contendo a hora atual CUTC
3. O Cliente obtém uma resposta e ajusta 
seu relógio
● Problemas?
○ Atraso no envio das mensagens
○ O tempo pode retroceder abruptamente causando 
inconsistências
Problemas
17
1. Atraso no envio das mensagens
a. Solução: ajustar relógio considerando estimativa de 
atraso
i. Resultado pode ser melhorado usando histórico de 
média de atrasos
Problemas
18
1. Atraso no envio das mensagens
a. Solução: ajustar relógio considerando estimativa de 
atraso
i. Resultado pode ser melhorado usando histórico de 
média de atrasos
2. O tempo pode retroceder abruptamente 
causando inconsistências
a. Solução: corrigir a hora mudando o tempo 
gradativamente
i. Ex: se cada interrupção da máquina adiciona 10ms 
ao relógio 
1. Cliente pode somar 9ms por tick (em vez de 
10ms) para atrasar
2. Cliente pode somar 11ms por tick (em vez de 
10ms) para adiantar
19
latência latência
processamento
tempo total
NTP
1. Calcular a latência: 
tempo para transmissão 
de mensagem
2. Calcular o atraso de 
relógio
● Toda mensagem deve carregar o timestamp do remetente
○ Timestamp segundo o relógio local de cada máquina
○ Servidor envia timestamps x e y para Cliente
● Simplificação: as latências de ida e volta são iguais
● Cuidado: lembre-se que servidores tem relógios diferentes
○ Latência = [(x - a) + (b - y)] / 2 ⇒ incorreto
● Latência = tempo total - tempo de processamento
○ Latência = [(b - a) - (y - x)] / 2
20
● Atraso de relógio (Θ) ⇒ diferença entre relógios do cliente e do servidor
○ Ida: cliente envia em a, servidor recebe em x, atraso de relógio Θ
■ O relógio do cliente está atrasado por Θ
■ x = a + latência + Θ ⇒ Θ = x - a - latência
○ Volta: servidor envia em y, cliente recebe em b, Θ
■ O relógio do cliente está atrasado por Θ
■ b = y + latência - Θ ⇒ Θ = y - b + latência
○ 2Θ = x - a - latência + y - b + latência
○ Θ = (x - a + y - b) / 2 
NTP
1. Calcular a latência: 
tempo para transmissão 
de mensagem
2. Calcular o atraso de 
relógio
latência latência
tempo total
Θ
Simplificação todo o atraso ocorreu 
no envio do cliente para o servidor
21
● Latência = [(b - a) - (y - x)] / 2
○ Latência = [(18-9) - (9-4)]/2 
○ Latência = (9-5)/2 = 2
● Atraso de relógio: Θ = (x - a + y - b) / 2
○ Θ = (4 - 9 + 9 - 18) / 2 
○ Θ = (4 - 18) / 2 = -7
● Servidor está “7 segundos” atrasado em relação ao cliente
● Logo, o cliente precisa diminuir sua frequência até atrasar um total de 7 
segundos
NTP
1. Calcular a latência: 
tempo para transmissão 
de mensagem
2. Calcular o atraso de 
relógio
tempo total
1 2 3 4 5 6 7 8 9 10 11
 8 9 10 11 12 13 14 15 16 17 18 19
latência latência
Network Time Protocol
22
Nem todos os relógios são igualmente confiáveis.
➡ Um servidor não deve ajustar seu tempo com 
base em um relógio menos confiável.🔁 Regra de ajuste:
● Um nó só ajusta seu relógio se seu stratum 
for maior que o do servidor consultado.
● Após ajuste, o cliente assume stratum = 
servidor + 1.
Stratum O que representa
0 Não é um servidor NTP, mas sim um 
relógio de referência (ex: GPS, relógio 
atômico). Ele não fala NTP diretamente.
1 Um servidor NTP diretamente conectado 
a um stratum-0 (ou seja, ele tem acesso 
a UTC, GPS, etc.). É o servidor NTP 
mais confiável.
2+ Servidores sincronizados com servidores 
de nível mais baixo.
... Cada sincronização adiciona +1
🏷 Níveis de confiança (stratum):
Relógios Lógicos
23
A ordem dos fatores altera o resultado!
Relógios Lógicos
● Proposto por Leslie Lamport
● Objetivo: estabelecer a ordem de eventos 
independentemente da hora real
● Embora a sincronização de relógios seja 
possível, não precisa ser absoluta:
○ É necessário sincronizar processos que não interagem 
entre si? Não!
24
Relógios Lógicos de Lamport
● Relação acontece antes
○ Se a e b são eventos do mesmo processo e a acontece antes de b, então: a → b
○ Se a é o envio de uma mensagem e b é o seu recebimento, então: a → b 
○ Se a → b, e b → c, então a → c (propriedade transitiva)
○ Se x e y acontecem em processos diferentes que não trocam mensagens, então x → y e y → 
x são falsas!
■ Esses processos são ditos concorrentes
○ Tempos são medidos em função: se a → b, C(a)que os relógios lógicos sejam ajustados!
● A relação acontece-antes só pode ser 
estabelecida para eventos ligados pelo 
envio de mensagens (ou eventos que 
ocorrem no mesmo nó)
○ Relógios lógicos não mantêm o histórico de 
interações
Relógios Lógicos
46
P3 não tem como 
relacionar seu 
relógio com o de P1
● Gerar a ordem total exige comunicação 
frequente e impõe restrições sobre o que 
se pode executar em cada instante
○ Mas, quando há interação é essencial manter 
a ordem (relação causal)
○ Eventos não relacionados podem ser tratados 
em qualquer ordem
Ordem total x ordem causal
47
Relógios Lógicos 
Vetoriais
48
Relógios Lógicos Vetoriais
49
● Tenta solucionar problemas de causalidade apresentados nos relógios de 
Lamport através do uso de relógios vetoriais
● Cada nó mantém um vetor de contadores com sua visão mais recente do 
relógio de cada outro nó
● Cada processo Pi mantém um vetori com as seguintes propriedades:
1. Quando Pi executa, vetori[i] é incrementado
2. Quando Pi envia uma mensagem, ele inclui nela vetori
3. Quando Pi recebe uma mensagem de Pj:
a. atualiza seu vetor: vetori[k] = max(vetori[k], msgj[k]), ∀k≠i
b. incrementa vetori[k]
Relógios Lógicos Vetoriais
50
● vetori[k] indica quantos eventos i sabe que aconteceram em k
○ São os eventos de Pk que já alcançaram i (relação causal)
A
A:0
B:0
C:0
B
A:0
B:0
C:0
C
A:0
B:0
C:0
A:0
B:0
C:1
A:0
B:1
C:1
A:0
B:2
C:1
A:1
B:2
C:1
A:0
B:0
C:2
A:2
B:2
C:2
A:3
B:2
C:2
A:3
B:3
C:2
A:3
B:4
C:3
A:3
B:4
C:2
1. Quando Pi executa, vetori[i] é incrementado
2. Quando Pi envia uma mensagem, ele inclui nela vetori
3. Quando Pi recebe uma mensagem de Pj:
a. atualiza seu vetor: vetori[k] = max(vetori[k], msgj[k]), 
∀k≠i
b. incrementa vetori[k]
Relógios Lógicos Vetoriais
51
● Ao se comparar dois eventos a e b, compara-se todos os valores contidos 
em seus timestamps
○ Se todos os valores de a são menores ou iguais aos respectivos valores de b, a precede b
■ a causou b, ou seja, b é um efeito de a
○ Se alguns valores são maiores e outros menores ou iguais, não se pode ordenar os dois 
eventos
■ não existe relação causal entre a e b
Relógios Lógicos Vetoriais
52
A
A:0
B:0
C:0
B
A:0
B:0
C:0
C
A:0
B:0
C:0
A:0
B:0
C:1
A:0
B:1
C:1
A:0
B:2
C:1
A:1
B:2
C:1
A:0
B:3
C:1
A:0
B:3
C:2
A:2
B:2
C:1
A:2
B:4
C:1
A:0
B:3
C:3
A:3
B:3
C:3
A:2
B:5
C:1
A:2
B:5
C:4
A:2
B:5
C:5
A:4
B:5
C:5
Relógios Lógicos Vetoriais
53
A
A:0
B:0
C:0
B
A:0
B:0
C:0
C
A:0
B:0
C:0
A:0
B:0
C:1
A:0
B:1
C:1
A:0
B:2
C:1
A:1
B:2
C:1
A:0
B:3
C:1
A:0
B:3
C:2
A:2
B:2
C:1
A:2
B:4
C:1
A:0
B:3
C:3
A:3
B:3
C:3
A:2
B:5
C:1
A:2
B:5
C:4
A:2
B:5
C:5
A:4
B:5
C:5
Causas
Efeitos
independentes
independente
Multicasting com ordenação causal
54
● Todas as mensagens são enviadas por multicast
○ O valor de vetori[i] só é incrementado no envio de mensagens
○ Uma mensagem m de Pi é mantida na fila de entrega de Pj até que
■ tsm[i] = vetorj[i] + 1
● a msg é a próxima que Pj espera de Pi
● Ex: se a última mensagem que Pj viu de Pi foi 3, então Pj não pode entregar a 
mensagem 5 para a aplicação
■ ∀k≠i, tsm[k]a ficha circulará bastante, 
consumindo rede, sem necessidade
+ Se processos acessam recurso com frequência a ficha circulará de forma justificada 
- os processos estão de fato sincronizando entre si para acessar recursos compartilhados
67
Algoritmo descentralizado
● Evolução do centralizado: replica o coordenador
○ coord-1, coord-2, …, coord-n
● Requisitante precisa receber maioria de votos de coordenadores: m > n/2
○ m: quantidade de votos
○ n: quantidade de réplicas
● Quem não tem maioria tenta novamente depois de um tempo aleatório
68
Algoritmo descentralizado
69
1
C1 C2 C3 C4 C5
n = 5 (réplicas)
m1 > n / 2 ?
m1 = 5 (votos)
5 > 2,5
(permitido!)
Algoritmo descentralizado
70
1
C1 C2 C3 C4 C5
2
n = 5 (réplicas)
m1 > n / 2 ?
m1 = 3 (votos)
3 > 2,5
(permitido!)
n = 5 (réplicas)
m2 > n / 2 ?
m2 = 3 (votos)
2 n / 2 ?
m1 = 2 (votos)
2 n / 2 ?
m2 = 2 (votos)
2 n / 2 ?
m3 = 1 (votos)
1 450K)
○ computar o hash de 450K blocos seria demorado?
Prova de Trabalho
● A blockchain do Bitcoin possui aprox 900K blocos… 
○ computar o hash de 900K blocos seria demorado? Não!
○ alterar o bloco de número 450K requer modificar apenas os blocos depois dele (i.e., >450K)
○ computar o hash de 450K blocos seria demorado? Não!
● Solução: prova de trabalho
○ desafio: encontrar um nonce para que o hash do bloco inicie com uma quantidade específica de zeros (dificuldade)
Prova de Trabalho
● Solução: prova de trabalho
○ desafio: encontrar um nonce para que o hash do bloco inicie com uma quantidade específica 
de zeros (dificuldade)
Implementando nossa própria Blockchain
Implementação própria dos aspectos básicos da blockchain, para fins educativos.
https://github.com/eduardolfalcao/edublockchain 
https://github.com/eduardolfalcao/edublockchain
Mineração
● Minerar é procurar por um nonce válido, e quem minera é 
um minerador :)
● Por que minerar?
○ O minerador vencedor é recompensado com Bitcoins
■ Coinbase transaction é a primeira transação do bloco
https://www.blockchain.com/btc/block/00000000000000000002bf0deae39e8fe443fadae6c5505885be487f843d896aMineração
● Minerar é procurar por um nonce válido, e quem minera é 
um minerador :)
● Por que minerar?
○ O minerador vencedor é recompensado com Bitcoins
■ Coinbase transaction é a primeira transação do bloco
● Recompensa
○ Início do Bitcoin: 50 BTC
○ A cada 4 anos esse número cai pela metade
■ em 2019 era aproximadamente 12.5 BTC
■ hoje é aproximadamente 3.2 BTC
○ Essa PG não permitirá mais de 21M de BTC
https://www.blockchain.com/btc/block/00000000000000000002bf0deae39e8fe443fadae6c5505885be487f843d896a
https://www.blockchain.com/explorer/blocks/btc/0
Mineração
● Recompensa
○ Início do Bitcoin: 50 BTC
○ A cada 4 anos esse número cai pela metade
■ em 2019 era aproximadamente 12.5 BTC
■ hoje é aproximadamente 3.2 BTC
○ Essa PG não permitirá mais de 21M de BTC
● Taxa de mineração
○ 10 a 30 minutos, próx 1 a 3 blocos ⇒ $0.22
○ 60 minutos, próx 3 blocos ⇒ $0.16
● Pool de transações: [1]
https://www.blockchain.com/explorer/blocks/btc/0
https://en.bitcoin.it/wiki/Transaction_fees
https://www.blockchain.com/explorer/pt/explorer/mempool/btc
Consenso
● Não existe um líder que coordena a blockchain
● Mas existe uma regra: a maior cadeia é a blockchain principal
● Maior esforço computacional ⇒ maior cadeia
○ consenso = prova de trabalho
Consenso
● Ao minerar um bloco, um nó deve enviar o bloco (transações + nonce) para 
outros mineradores 
● Após verificar a validade do bloco, o minerador receptor adiciona o bloco na 
blockchain, e dissemina via broadcast
Ataque de gasto duplo (51%)
Fazendas de Mineração
Bitcoin consumes more energy than Switzerland
https://www.theverge.com/2019/7/4/20682109/bitcoin-energy-consumption-annual-calculation-cambridge-index-cbeci-country-comparison
Prova de participação 
98
● Como funciona: O próximo validador (ou “líder”) é escolhido com base na 
quantidade de tokens que possui em stake. Quanto mais stake, maior a 
chance de ser escolhido.
● Sem custo computacional: Não há resolução de problemas pesados. A 
seleção é “quase gratuita” do ponto de vista computacional.
● Consequências e desafios:
○ Baixo custo para agir mal: 
■ Um validador malicioso pode tentar criar blocos inválidos sem grande custo energético.
■ Como é barato propor blocos em múltiplas cadeias simultaneamente, pode haver 
incentivos para validar forks (o que é perigoso para o consenso).
○ Soluções propostas:
■ Penalidades (slashing) para quem tenta fraudar ou valida blocos conflitantes.
■ Checkpoints e finalizações para impedir múltiplas visões da verdade.
Em Resumo
● Sem relógio global: Cada máquina tem seu próprio relógio — necessidade de 
sincronização.
● Sincronização de relógios: Baseada em troca de mensagens + compensação 
de atrasos de comunicação.
● Relógios Lógicos (Lamport): Garantem ordenação de eventos → C(a)