difusao

Tolerncia a FalhasDifuso de MensagensBroadcast confivel, atmico e causal

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Difuso de Mensagens

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Tipos de difusobroadcastenvio de mensagens a todos os nodos do sistema

multicastenvio de mensagens a alguns nodos do sistema

infraestrutura de redepodem ser baseados em broadcast no confivelou em comunicao ponto a pontosensvel a falhas de nodo e comunicaoEnvolve o conceito de gruposnodo pode falhar aps ter iniciado broadcast,assim alguns nodos podem ter recebido amensagem e outros no

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

essa topologia s existe nomodelo lgico, no modelo fsicopode no existir caminhos entrealguns nodosnodo nooperacionalExemplos de Problemas

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Propriedades na difuso

confiabilidademensagem deve ser recebida por todos os nodos operacionais

ordenamento consistentediferentes mensagens enviadas para nodos diferentes so entregues na mesma ordem em todos os nodos

preservao de causalidadea ordem na qual mensagens so entregues consistente com a relao causal de envio das mensagensvalem tanto para broadcast como multicastordenamento consistente diferente deordenamento temporalmensagens sem relao causal poderiam serentregues em qualquer ordem

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Primitivas de difuso

difuso confiveluma mensagem enviada recebida em todos os nodos no falhos na rede, mesmo na presena de falhas

difuso atmicasuporta difuso confivel e ordenao

difuso causalassegura ordenao causalcada primitiva tem sua aplicaomensagens isoladas: difuso confivelbanco de dados: difuso atmicauma mensagem depende de outra: difuso causal

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Comentrios

problemas com nomenclaturaestamos usando nomenclatura do Jaloteexistem problemasprincipalmente em relao a atomicidade, que em banco de dados tem outro significado

problemas com particionamentohiptese usual:falhas no particionam a redemas em computao mvel particionamento comum

URI - DECC - Santo ngelo

Broadcast confivel

protocolo de Schneider protocolo de Melliar-Smith

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

rvore lgica de difusono corresponde atopologia fsicaBroadcast

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

rvore lgica de difusoBroadcast

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Broadcast confivel

Exemplo: Schneider (84)

modela rede como um rvorervore de disseminao de mensagensrvore representa estrutura lgicanodo raiz o iniciador de um broadcasttodos os nodos que difundem so raiz naquela difusorvore lgica no corresponde a topologia da rede fsica

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Protocolo de Schneiderestrutura lgica sem relao com estrutura fsica da rede

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Protocolo de Schneider

rvoreesttica, pr-definida e conhecida por todos os ns do sistema

estratgia de broadcastraiz inicia broadcastenvia mensagem para todos os seus sucessoresnodo i recebe mensagem e repassa para todos os seus sucessoressucessores respondem ACK para i

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

SchneiderEstratgia Bsica:

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

SchneiderEstratgia Bsica:i no recebe ack de j;i assume: j no envioumens. para n e m;

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

SchneiderEstratgia Bsica:

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

SchneiderEstratgia Bsica:

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Protocolo de Schneider

quando a raiz falha:falhas na raiz so detectadas por seus filhosalgum nodo (que recebeu a mensagem) assume funo de raizmais de um nodo pode assumir funo da raiz (sem problema)para facilitar deteco de falha:raiz informa broadcast concludo com sucesso (recebeu ack de todos os sucessores)na falta de aviso, nodo sucessor assume falha na raiz

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Schneider

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Schneider

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Schneider

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Schneider

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Protocolo de Melliar-SmithTrans protocolMelliar-Smith, Moser e Agrawala 1990

acks positivos e negativos (acks e nacks) na carona de mensagens difundidaspiggyback (levar nos ombros)

primitiva confivel baseada em broadcast no confivelex meio fsico: Ethernetex: protocolo broadcast no confivel em comunicao ponto a ponto

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Trans protocol

cada mensagem transporta:identidade do transmissornmero de seqncia unvocoacks e nacks

receptor:a partir de acks e nacks determinaque mensagens ele no precisa reconhecer com ackque mensagens ele precisa pedir retransmissoque mensagens ele precisa retransmitir

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Trans (Melliar-Smith)primitiva confivel baseada em broadcast no confivelMelliar-Smith, Mosere Agrawala (1990)

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Trans

cada mi transporta:

identidade do transmissor e nmero de seqncia unvoco

acks e nacks na carona de mensagens difundidas

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Trans

o receptor determina:

mensagens ele no precisa reconhecer

quais ele precisa retransmisso

quais ele deve retransmitir

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Trans se o receptor Rdetermina que norecebeu m1 pede retransmisso qualquer nodo pode atender um pedido de retransmisso (no apenas o originador)sem ordenao: mensagenspodem ser recebidas emcada nodo em uma ordemdiferente (no exemplo m1chegar em R aps m2 )R no recebeu m1R envia nackm1pedindoretransmissom3 ackm2 nackm1

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

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 FecTransm. de B reconhece ATrans. de C reconhece B, no precisa reconhecer ATrans. de E viu por Dc que no recebeu CAlgum nodo retransmite C(sem Novos acks)

URI - DECC - Santo ngelo

Tolerncia a Falhas Sistemas Distribudos

Comentrios

retransmissoqualquer nodo pode atender um pedido de retransmisso (no apenas o originador)

mltiplos acksvrias mensagem podem confirmar (ack) o recebimento de uma dada mensagem

mensagens dummy

sem ordenaomensagens podem ser recebidas em cada nodo em uma ordem diferente

URI - DECC - Santo ngelo