URI - DECC - Santo Ângelo Tolerância a Falhas Difusão de Mensagens Broadcast confiável, atômico e causal

URI - DECC - Santo Ângelo URI - DECC - Santo Ângelo

Tolerância a Falhas

Difusão de Mensagens

Broadcast confiável, atômico e causal


Tolerância a Falhas – Sistemas Distribuídos

Difusão de Mensagens



Tipos de difusão broadcast

envio de mensagens a todos os nodos do sistema

multicast 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

Envolve o conceito de grupos

nodo pode falhar após ter iniciado broadcast,assim alguns nodos podem ter recebido amensagem e outros não



essa topologia só existe nomodelo lógico, no modelo físicopode não existir caminhos entrealguns nodos

nodo nãooperacional

Exemplos de Problemas



Propriedades na difusão

confiabilidade mensagem deve ser recebida por todos os nodos operacionais

ordenamento consistente 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

valem tanto para broadcast como multicast

ordenamento consistenteé diferente deordenamento temporal

mensagens sem relação causal poderiam serentregues em qualquer ordem



Primitivas de difusão

difusão confiável uma mensagem enviada é recebida em todos os nodos não

falhos na rede, mesmo na presença de falhas

difusão atômica 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



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


Broadcast confiável

protocolo de Schneiderprotocolo de Melliar-Smith



árvore lógica de difusão

não corresponde atopologia física

Broadcast



árvore lógica de difusãoBroadcast



Broadcast confiável

Exemplo: Schneider (84)

modela rede como um árvore árvore de disseminação de mensagens

árvore representa estrutura lógica

nodo raiz é o iniciador de um broadcast todos os nodos que difundem são raiz naquela difusão

árvore lógica não corresponde a topologia da rede física



Protocolo de Schneider

estrutura lógica sem relação com estrutura física da rede




á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



Schneider

Estratégia Básica:



Schneider

Estratégia Básica:

i não recebe ack de j;i assume: j não envioumens. para n e m;



SchneiderEstratégia Básica:



SchneiderEstratégia Básica:




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



Schneider



Schneider



Schneider



Schneider



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



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



Trans (Melliar-Smith) primitiva confiável baseada em broadcast não

confiável

Melliar-Smith, Mosere Agrawala (1990)



Trans

cada mi transporta:

identidade do transmissor e número de seqüência unívoco

acks e nacks na carona de mensagens difundidas



Trans

o receptor determina:

mensagens ele não precisa reconhecer

quais ele precisa retransmissão

quais ele deve retransmitir



Trans

– se o receptor Rdetermina que nãorecebeu m1 • pede retransmissão • qualquer nodo pode atender um pedido de retransmissão (não apenas o originador)

sem ordenação: mensagenspodem ser recebidas emcada nodo em uma ordemdiferente (no exemplo m1chegará em R após m2 )

R não recebeu m1R envia nackm1pedindoretransmissãom3 ackm2 nackm1



Exemplo TransA, B, C, D = mens a, b, c, d = acks, a, b, c, d = nacks

AA BaA Ba CbA Ba Cb DcA Ba Cb Dc EcdA Ba Cb Dc Ecd CbA Ba Cb Dc Ecd Cb Fec

Transm. de B reconhece A

Trans. de C reconhece B, não precisa reconhecer A

Trans. de E viu por Dc que não recebeu C

Algum nodo retransmite C(sem Novos acks)



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

Documents

URI - DECC - Santo Ângelo Tolerância a Falhas Difusão de Mensagens Broadcast confiável, atômico e causal