Gerenciamento de Grupo na Plataforma ISIS

Apresentado por Antônio Carlos Theóphilo Costa Júnior

Roteiro

• Trabalho Relacionado• Algoritmo de Gerenc. de Grupo ISIS

– Aspectos Gerais– Características– Vantagens

• Código• Características

Trabalho Relacionado

• Algoritmo Transis

• Vantagens

– Solução Elegante– Geral

• Desvantagens

– Requer multicast em cada membro

– Depende do suporte dado pelo algoritmo Trans

Algoritmo ISIS

• Proposto por Aleta Ricciardi e Kenneth Birman para realizar o Gerenciamento de Grupos na Plataforma ISIS.

• Projetado para ambientes de comunicação ponto-a-ponto.

• Vantagens:– Mais eficiente em ambientes aonde o multicast é

implementado com mensagens ponto-a-ponto;– Pode ser usado em ambientes sem multicast.

Algoritmo ISIS

• Características Gerais– Paranóico– Unidirecional (one-way)– Fofoqueiro (gossipy)– Supõe canais ponto-a-ponto confiáveis e FIFO– Descarta mensagens de processos considerados

faltosos

Algoritmo ISIS

• Conceitos

– Coordenador– Participante– Reconfiguração

Variáveis Utilizadas

L = Visão atual do grupo

version = Versão de L

change = Última mudança proposta a L

rank = Nível do coordenador q propôs a mudança

faulty = Lista de processos suspeitos

remoteState[1..M] = Estados dos participantes

remoteState[i].L = Visão do grupo por i

remoteState[i].version = Versão da visão

remoteState[i].rank = Nível do coordenador q implantou a visão

remoteState[i].change = Mudança proposta por i

Abreviaçõessend(dest, action, params)

send(dest, action, params, faulty)

action(sender, params)

{código ... }

action(sender, params, remFaulty)

faulty = faulty U remFaulty

{código ... }

Abreviações

distribute(action; params)

returnAction(sender; params)

{código ... }

para cada p em {L - faulty}

send(p, action, params) //time-out de T segundos

returnAction(sender, params)

{código ... }

para cada p em {L - faulty} que não respondeu

faulty = faulty U {p}

Operação Normal - Coordenador

normalCoordinator() {

while (true) {

espere até a ocorrência de uma mudança na visão do grupo

distribute(COORD_UDDATE; change, version + 1)

CU_ACK(sender, version)

version++

realiza as mudanças em L descritas em change

distribute(CU_COMMIT)

CC_ACK(sender)

}

}

Operação Normal - Participante

normalParticipant() {

while(true) {

espere por uma msg do coordenador

COORD_UPDATE(coordinator; chg, vrs):

change = chg

next_version = vrs

rank = rank(coordinator)

send(coordenador; CU_ACK)

CU_COMMIT(coordinator):

realizar a mudança descrita em change para L

version = next_version

change = {}

send(coordinator; CC_ACK)

}

}

Reconfiguração – Coordenador (1)

reconfigureCoordinator() {

myState = (L, version, rank, {})

distribute(INTERROGATE; myState)

INT_RESPONSE(sender; rState)

remoteState[sender] = rState

ahead = {p | p in L and remoteState[p].version > version}

current = {p | p in L and remoteState[p].version = version}

...

Reconfiguração – Coordenador (2) ...

if (ahead != {})

//existe uma visao mais atualizada comitada

//deve-se propo-la else if (para todo p em current remoteState[p].change = {}) //não existem mudancas comitadas else if (existe um valor p/ remoteState[p].change!={} em current)

//uma proposta foi feita. Ela pode ter sido comitada.

//Deve ser proposta else

//existem propostas competindo para uma mudanca. A

proposta proposta pelo reconfigurador com o menor rank

e’ a unica q pode ter sido comitada ...

Reconfiguração – Coordenador (3)

distribute(REORD_UPDATE; change, nextVersion)

RU_ACK(sender)

atualize L com change

coordinator = self

change = futureProposal

executar o normalCoordinator

}

Detalhamento (1)

//existe uma visao mais atualizada comitada

//deve-se propo-la

if(ahead != {})

change = remotestate[p].L para um p em ahead

nextVersion = version + 1

futureProposal = remoteState[p].change para um p em ahead tal que remoteState[p].rank seja minimo

Detalhamento (2)

//não existem mudancas comitadas

else if(remoteState[p].change = {} p/ qq p em current)

change = faulty //pelo menos o antigo coordenador

nextVersion = version +1

futureProposal = faulty

Detalhamento (3)

//uma proposta foi feita. Ela pode ter sido comitada.

//Deve ser proposta

else if(existe um unico valor != {} de

remoteState[p].change para um p em current)

change = remoteState[p].change para um p em current

tal que change != {}

nextVersion = version +1

futureProposal = faulty

Detalhamento (4)

//existem propostas competindo para uma mudanca. A proposta proposta pelo reconfigurador com o menor rank e’ a unica q pode ter sido comitada

else()

change = remoteState[p].change para um p em current

tal que remoteState[p].rank seja minimo

nextVersion = version +1

futureProposal = faulty

Reconfiguração – Participante (1)reconfigureParticipant() {

espere por uma msg INTERROGATE

INTERROGATE(sender; sdrL, sdrVersion, sdrRank, sdrChange)

if(rank(self)>sdrRank)

crash()

if(version<sdrVersion)

L = sdrL

version = sdrVersion

rank = sdrRank

change = {}

send(sender, INT_RESPONSE; L, version, rank, change)

espere T segundos por REORD_UPDATE

REORD_UPDATE(sender; nextChange, nextVersion)

se não tiver havido resposta

adicione sender a faulty e saia do procedimento

Reconfiguração – Participante (2)

...

change = nextChange

rank = rankSender

send(sender; RU_ACK)

espere T segundos por REORD_COMMIT

REORD_COMMIT

se não tiver havido resposta

adicione sender a faulty e saia do procedimento

se nextVersion > version

realize em L a mudança descrita em change

version = nextVersion

coordinator = sender

send(coordinator, RC_ACK)

}

Características (1)coord p2p1 r

update(x+1)

update(x+2)

commit(x+1)

commit(x+2)

r falhou

interrogate

• Um reconfigurador vê no máximo uma visão comitada de versão x+1

Características (2)

• Reconfiguradores competindo para instalar versões conflitantes

p p1 p2 p3 r

commit(x+1)

p falhou

r falhou interrogate/

update/

commit

update(x+2)

crash()

Resumo

• Vantagens– Algoritmo ideal para ambientes de comunicação em

grupo sem suporte nativo a multicast– Útil em ambientes de grupo sem multicast– Consistência mantida mesmo na presença simultânea de

múltiplos coordenadores

• Desvantagens – Complexidade– Paranóia

FIM

Críticas/Dúvidas