Tolerância a Falhas
Difusão de Mensagens
Broadcast confiável, atômico e
causal
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos

Difusão de Mensagens
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Tipos de difusão

broadcast


multicast


envio de mensagens a todos os nodos do sistema
Envolve o conceito de grupos
envio de mensagens a alguns nodos do sistema
infraestrutura de rede


podem ser baseados em broadcast não confiável
ou em comunicação ponto a ponto

sensível a falhas de nodo e comunicação
nodo pode falhar após ter iniciado broadcast,
assim alguns nodos podem ter recebido a
mensagem e outros não
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Exemplos de Problemas
nodo não
operacional
essa topologia só existe no
modelo lógico, no modelo físico
pode não existir caminhos entre
alguns nodos
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Propriedades na difusão
valem tanto para broadcast como multicast

confiabilidade


ordenamento consistente


mensagem deve ser recebida por todos os nodos operacionais
ordenamento consistente
é diferente de
ordenamento temporal
diferentes mensagens enviadas para nodos diferentes são
entregues na mesma ordem em todos os nodos
preservação de causalidade

a ordem na qual mensagens são entregues é consistente com a
relação causal de envio das mensagens
mensagens sem relação causal poderiam ser
entregues em qualquer ordem
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Primitivas de difusão

difusão confiável


difusão atômica


uma mensagem enviada é recebida em todos os nodos não
falhos na rede, mesmo na presença de falhas
suporta difusão confiável e ordenação
difusão causal


assegura ordenação causal
cada primitiva tem sua aplicação



mensagens isoladas: difusão confiável
banco de dados: difusão atômica
uma mensagem depende de outra: difusão causal
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Comentários

problemas com nomenclatura


estamos usando nomenclatura do Jalote
existem problemas


principalmente em relação a atomicidade, que em banco de
dados tem outro significado
problemas com particionamento

hipótese usual:

falhas não particionam a rede

mas em computação móvel particionamento é comum
URI - DECC - Santo Ângelo
Broadcast confiável
protocolo de Schneider
protocolo de Melliar-Smith
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
árvore lógica de difusão
Broadcast
não corresponde a
topologia física
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Broadcast
árvore lógica de difusão
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Broadcast confiável

Exemplo: Schneider (84)

modela rede como um árvore

árvore de disseminação de mensagens


nodo raiz é o iniciador de um broadcast


árvore representa estrutura lógica
todos os nodos que difundem são raiz naquela difusão
árvore lógica não corresponde a topologia da rede
física
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Protocolo de Schneider
estrutura lógica sem relação com estrutura física da rede
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Protocolo de Schneider

árvore


estática, pré-definida e conhecida por todos os nós
do sistema
estratégia de broadcast

raiz inicia broadcast



envia mensagem para todos os seus sucessores
nodo i recebe mensagem e repassa para todos os
seus sucessores
sucessores respondem ACK para i
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Schneider
Estratégia Básica:
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Schneider
Estratégia Básica:
i não recebe ack de j;
i assume: j não enviou
mens. para n e m;
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Schneider
Estratégia Básica:
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Schneider
Estratégia Básica:
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Protocolo de Schneider

quando a raiz falha:


falhas na raiz são detectadas por seus filhos
algum nodo (que recebeu a mensagem) assume
função de raiz


mais de um nodo pode assumir função da raiz (sem
problema)
para facilitar detecção de falha:


raiz informa broadcast concluído com sucesso (recebeu ack
de todos os sucessores)
na falta de aviso, nodo sucessor assume falha na raiz
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Schneider
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Schneider
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Schneider
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Schneider
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos

Protocolo de Melliar-Smith
Trans protocol

Melliar-Smith, Moser e Agrawala 1990

acks positivos e negativos (acks e nacks) na carona
de mensagens difundidas


piggyback (levar nos ombros)
primitiva confiável baseada em broadcast não
confiável


ex meio físico: Ethernet
ex: protocolo broadcast não confiável em comunicação ponto
a ponto
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Trans protocol

cada mensagem transporta:




identidade do transmissor
número de seqüência unívoco
acks e nacks
receptor:




a partir de acks e nacks determina
que mensagens ele não precisa reconhecer com ack
que mensagens ele precisa pedir retransmissão
que mensagens ele precisa retransmitir
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Trans (Melliar-Smith)

Melliar-Smith, Moser
e Agrawala (1990)
primitiva confiável baseada em broadcast não
confiável
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Trans

cada mi
transporta:

identidade do
transmissor e
número de
seqüência
unívoco

acks e nacks na
carona de
mensagens
difundidas
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Trans

o receptor
determina:

mensagens ele
não precisa
reconhecer

quais ele precisa
retransmissão

quais ele deve
retransmitir
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Trans
sem ordenação: mensagens
podem ser recebidas em
cada nodo em uma ordem
diferente (no exemplo m1
chegará em R após m2 )
– se o receptor R
determina que não
recebeu m1
• pede retransmissão
• qualquer nodo pode
atender um pedido de
retransmissão (não
apenas o originador)
R não recebeu m1
R envia nackm1
pedindo
retransmissão
m3 ackm2 nackm1
URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Exemplo Trans
A, B, C, D = mens a, b, c, d = acks, a, b, c, d = nacks
A
Transm. de B reconhece A
 A Ba
Trans. de C reconhece B, não precisa reconhecer A
 A Ba Cb
 A Ba Cb Dc
Trans. de E viu por Dc que não recebeu C
 A Ba Cb Dc Ecd
Algum nodo retransmite C(sem
 A Ba Cb Dc Ecd Cb
Novos acks)
 A Ba Cb Dc Ecd Cb Fec

URI - DECC - Santo Ângelo
Tolerância a Falhas – Sistemas Distribuídos
Comentários

retransmissão


qualquer nodo pode atender um pedido de retransmissão (não
apenas o originador)
múltiplos acks

várias mensagem podem confirmar (ack) o recebimento de uma
dada mensagem

mensagens dummy

sem ordenação

mensagens podem ser recebidas em cada nodo em uma ordem
diferente
URI - DECC - Santo Ângelo