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