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 pontoa-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ções
send(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
p1
p2
r
update(x+1)
• Um reconfigurador vê no máximo
uma visão comitada de versão
x+1
commit(x+1)
r falhou
update(x+2)
commit(x+2)
interrogate
Características (2)
p
p1
p2
p3
r
commit(x+1)
• Reconfiguradores competindo
para instalar versões conflitantes
p falhou
r falhou
update(x+2)
interrogate/
update/
commit
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