Gerenciamento de Grupo na Plataforma ISIS Roteiro Trabalho

Roteiro
Gerenciamento de Grupo na
Plataforma ISIS
• Trabalho Relacionado
• Algoritmo de Gerenc. de Grupo ISIS
– Aspectos Gerais
– Características
– Vantagens
• Código
• Características
Apresentado por Antônio Carlos Theóphilo Costa Júnior
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 pontoa-ponto.
• Vantagens:
– Mais eficiente em ambientes aonde o multicast é
implementado com mensagens ponto-a-ponto;
– Pode ser usado em ambientes sem multicast.
1
Algoritmo ISIS
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
Variáveis Utilizadas
• Conceitos
– Coordenador
– Participante
– Reconfiguração
Abreviações
send(dest, action, params)
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
send(dest, action, params, faulty)
action(sender, params)
{código ... }
action(sender, params, remFaulty)
faulty = faulty U remFaulty
{código ... }
remoteState[i].change = Mudança proposta por i
2
Abreviações
Operação Normal - Coordenador
distribute(action; params)
returnAction(sender; params)
normalCoordinator() {
while (true) {
{código ... }
espere até a ocorrência de uma mudança na visão do grupo
distribute(COORD_UDDATE; change, version + 1)
para cada p em {L - faulty}
send(p, action, params)
CU_ACK(sender, version)
//time-out de T segundos
version++
realiza as mudanças em L descritas em change
returnAction(sender, params)
distribute(CU_COMMIT)
{código ... }
CC_ACK(sender)
para cada p em {L - faulty} que não respondeu
}
faulty = faulty U {p}
}
Operação Normal - Participante
Reconfiguração – Coordenador (1)
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
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}
...
change = {}
send(coordinator; CC_ACK)
}
}
3
Reconfiguração – Coordenador (2)
Reconfiguração – Coordenador (3)
...
if (ahead != {})
//existe uma visao mais atualizada comitada
//deve-se propo-la
else if (para todo p em current remoteState[p].change = {})
distribute(REORD_UPDATE; change, nextVersion)
//não existem mudancas comitadas
RU_ACK(sender)
else if (existe um valor p/ remoteState[p].change!={} em current)
atualize L com change
//uma proposta foi feita. Ela pode ter
sido comitada.
coordinator = self
//Deve ser proposta
change = futureProposal
else
executar o normalCoordinator
//existem propostas competindo para uma mudanca. A
}
proposta proposta pelo reconfigurador com o menor rank
e’ a unica q pode ter sido comitada
...
Detalhamento (1)
Detalhamento (2)
//existe uma visao mais atualizada comitada
//não existem mudancas comitadas
//deve-se propo-la
else if(remoteState[p].change = {} p/ qq p em current)
if(ahead != {})
change = faulty //pelo menos o antigo coordenador
change = remotestate[p].L para um p em ahead
nextVersion = version +1
nextVersion = version + 1
futureProposal = faulty
futureProposal = remoteState[p].change para um p
em ahead tal que remoteState[p].rank seja minimo
4
Detalhamento (3)
//uma proposta foi feita. Ela pode ter
Detalhamento (4)
sido comitada.
//existem propostas competindo para uma mudanca. A
proposta proposta pelo reconfigurador com o menor rank
e’ a unica q pode ter sido comitada
//Deve ser proposta
else if(existe um unico valor != {} de
else()
remoteState[p].change para um p em current)
change = remoteState[p].change para um p em current
change = remoteState[p].change para um p em current
tal que remoteState[p].rank seja minimo
tal que change != {}
nextVersion = version +1
nextVersion = version +1
futureProposal = faulty
futureProposal = faulty
Reconfiguração – Participante (1)
Reconfiguração – Participante (2)
reconfigureParticipant() {
espere por uma msg INTERROGATE
...
INTERROGATE(sender; sdrL, sdrVersion, sdrRank, sdrChange)
change = nextChange
if(rank(self)>sdrRank)
rank = rankSender
crash()
send(sender; RU_ACK)
if(version<sdrVersion)
espere T segundos por REORD_COMMIT
L = sdrL
REORD_COMMIT
version = sdrVersion
se não tiver havido resposta
rank = sdrRank
adicione sender a faulty e saia do procedimento
change = {}
se nextVersion > version
send(sender, INT_RESPONSE; L, version, rank, change)
realize em L a mudança descrita em change
espere T segundos por REORD_UPDATE
version = nextVersion
REORD_UPDATE(sender; nextChange, nextVersion)
coordinator = sender
se não tiver havido resposta
adicione sender a faulty e saia do procedimento
send(coordinator, RC_ACK)
}
5
Características (1)
coord
p1
Características (2)
p2
r
p
update(x+1)
• Um reconfigurador vê no máximo
uma visão comitada de versão
x+1
p1
p2
p3
r
commit(x+1)
• Reconfiguradores competindo
para instalar versões conflitantes
commit(x+1)
p falhou
r falhou
update(x+2)
interrogate/
update/
commit
r falhou
crash()
update(x+2)
commit(x+2)
interrogate
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
FIM
Críticas/Dúvidas
– Complexidade
– Paranóia
6