Algoritmos de Eleição
Roteiro:
• Motivação e Principais Requisitos
• Algoritmos em Anel
• Algoritmo Bully
• Algoritmo do Convite
Referências:
• Livro do Chow/Johnson: seção 10.2
• Livro do Colouris/Dollimore/Kindberg: seção 11.3
• Livro do Michel Raynal: Distributed Algorithms and Protocols,
Wiley & Sons, 1988 (seção 2.5)
• S. Sight & A. Kurose: Electing “good” leaders, Journal of Parallel
and Distributed Computing Systems, 21: 194-201, 1994.
© Markus Endler
1
Eleição
Objetivo:
• obter um consenso em um grupo de processos sobre a
escolha de um único processo
Aplicações:
• Em muitos serviços (ou aplicações) distribuídos um
processo (arbitrário) exerce um papel diferenciado
(coordenador)
• Quando este falha, o grupo precisa re-eleger um novo
coordenador
Exemplos:
• Servidores replicados com com replicação passiva
(primary-backup)
• Um processo sequenciador para comunicação multicast
com ordenação total (exemplo: sistema Amoeba)
© Markus Endler
2
Eleição vs. Exclusão Mútua
Diferenças entre Exclusão Mútua e Eleição:
• Na Eleição, todos os participantes precisam saber quem foi
escolhido
• A maioria dos Algoritmos de Eleição não faz suposições sobre o
número total de processos
• Geralmente, Eleição é iniciada como reação a uma detecção de
falha (p.ex. do antigo coordenador)
• Algoritmos de eleição precisam lidar com a possibilidade de falha
durante a escolha do novo coordenador.
• Para o problema da eleição assume-se uma ordem total do conjunto
de IDs dos processos, e o conhecimento de um limite máximo deste
conjunto
Similaridades:
• Qualquer processo pode iniciar uma eleição (porém, não mais do
que uma eleição a cada vez), ou seja, pode haver várias execuções
simultâneas do algoritmo de eleição
• Todos os processos precisam estar de acordo com a decisão
tomada (o novo coordenador, ou o próximo a entrar na SC)
© Markus Endler
3
Principais Requisitos
Definição:
•
Durante uma eleição, cada processo pode estar engajado em uma
eleição (participante) ou não (não participante)
Os principais requisitos de qualquer Algoritmo de Eleição são:
•
Safety/Segurança: deve-se garantir a unicidade do elemento
escolhido
•
Liveness/Progresso: em algum momento, define-se um coordenador
Considere N processos P1,..,PN, cada um com uma variável Coord,
incialmente indefinida (Coord = undef)
As condições acima são formuladas como:
Segurança: Um processo participante Pi tem Coord = undef ou Coord =
P, onde P é um processo correto (não faltoso) ao término do
algoritmo.
Liveness: Todos os processos Pi participam da eleição e em algum
momento ou tem Coord  undef, ou terão falhado.
Geralmente, o problema é reduzido ao de encontrar o maior/menor ID no
grupo.
© Markus Endler
4
Eleição em uma toplogia de Anel
•
Assuma que cada processo tem um PID  [1, MAX]
•
E mensagens só circulam em um sentido
Objetivo: Achar o maior/menor PID.
Qual seria a idéia?
p8
p3
p9
• Como detectar o término do
algoritmo (ter encontrado o
manor/maior PID) ?
• Quantas rodadas são
necessárias?
© Markus Endler
p4
p1
5
Algoritmos baseados em Anel
Chang & Roberts (1979) propuseram um algoritmo simples para processos
interligados em uma estrutura lógica de anel (onde as mensagens só
circulam em um sentido)
O algoritmo funciona em 2 rodadas, para um número arbitrário de processos.
Ideia Central:
•
Processo Pi inicia o algoritmo enviando uma mensagem (election, Pi.PID)
para o próximo processo P (i+1)mod N.
•
Ao receber uma mensagem (election,ID), o processo Pj calcula max(ID,
PIDj) e manda este valor para o próximo
•
O processo que receber o seu próprio PID é o novo coordenador.
•
O coodenador coloca em circulação uma mensagem (elected,
coord.PID), para que todos fiquem sabendo quem é o novo coordenador
e o algoritmo termina quando esta msg retorna a ele.
O modelo de sistema:
•
Processos não falham
•
Comunicação é confiável e segura
•
Sistema é assíncrono
•
Todos os processos possuem PIDs distintos!
© Markus Endler
6
Algoritmos baseados em Anel
O algoritmo de Chang & Roberts garante a unicidade do coordenador
(segurança) porque:
•
A mensagem election passa por todos os processos (todos são
participantes)
•
Como todos tem PID distintos, existe um único processo com
PIDmax
•
Como a mensagem elected passa por todos os processos, todos
setam o mesmo valor para a variável Coord.
Liveness é garantida por:
•
A função max é uma aproximação sucessiva deste PIDmax
•
Por se tratar de um anel, e não haver perdas de mensagem, o
processo com PIDmax em algum momento receberá a mensagem
com seu próprio PID (PIDmax)
Características do Algorítmo:
•
Simetria textual
•
Vários processos podem inciar simultaneamente o algoritmo
•
Complexidade de mensagens por requisição 2 N.
•
No pior caso (todos começando simultaneamente) é O(N2)
© Markus Endler
7
Algoritmos baseados em Anel
Hirschberg & Sinclair [HS80] propuseram um algoritmo com custo de
comunicação O(N log N), que:
•
funciona em rodadas e
•
assume um anel de tamanho N com links bi-direcionais confiáveis
Ideia Central:
•
Iniciado a partir de um processo candidato, que a cada rodada
difunde (e compara ) o seu PID com vizinhos cada vez mais
afastados (mensagem Cand);
•
caso um dos vizinhos perceba que possui PID maior do que o do
candidato, este inicia uma nova eleição (difundindo o seu próprio
PID)
•
Processos com PID menores respondem ao candidato,
concordando com sua candidatura
•
Processos intermediários:
–
repassam mensagens, ou iniciam nova eleição (caso seu PID >
PIDCand)
[HS90] Hirschberg & Sinclair: Decentralized Extrema Finding in Circular
Configurations of Processes. Communications of the ACM, 23 (11), Nov. 1980.
© Markus Endler
8
Algoritmo de Hirschberg & Sinclair
Um pouco mais de detalhes:
Na rodada j o Pi envia a msg (Cand,Pi.ID) para os elementos:
P(i-2j) mod N e P(i+2j) mod N
Ao receber a mensagem (Cand,ID), processo Pk compara ID com o
seu próprio identificador Pk.PID:
Se (ID > Pk.PID) então retorna ao remetente TRUE
senão retorna FALSE e passa a ser o candidato
Se o iniciador receber duas respostas TRUE, continua candidato e
passa à proxima rodada  incrementa j
Quando o iniciador recebe a msg Cand com o próprio PID, sabe que foi
eleito o novo coordenador e
Difunde uma mensagem Elected com o seu ID no anel.
© Markus Endler
9
O Algoritmo de Hirschberg & Sinclair
Exemplo para 7 processos: Algoritmo iniciado pelo P5
P4
P1
P3
P7
P5
P2
P0
P4
False
Os 3 tipos de mensagem:
Cand (PID, d, dmax), onde:
•
dmax: distância máxima (# hops) a serem percorridos
•
d: distânca (#hops) já percorridos pela mensagem
Resp (bool, P), onde:
•
Bool = TRUE indica que P permanece candidato
•
P indica o processo ao qual a resposta é destinada (o candidato)
Elected(sender)
© Markus Endler
10
O Algoritmo de Hirschberg & Sinclair
Cada processo pode estar em um de 4 estados:
• not_involved = não foi consultado ainda
• candidate = é o atual responsável pelas pesquisas (enquanto
for o de maior PID)
• lost = recebeu msg com PID maior
• elected = quando P descobre que ele é o de maior PID
Variáveis em cada processo:
Enum state: initialy not_involved
// State = {candidate, not_involved, lost, elected}
Int maxhops, hops
Int Nr_replies // pode ser 0,1 ou 2
Bool remain
// TRUE = continua candidato na proxima rodada
Int winner
// ID do processo eleito
O algoritmo é composto de um procedimento para iniciar a eleição
(Election) e uma tread (Monitor) que trata as mensagens
recebidas, e que compartilham variáveis state e end_phase
© Markus Endler
11
Procedimento de invocação da Eleição
Election() {
state = candidate;
dmax = 1;
while (state == candidate) {
Nr_replies = 0;
remain = TRUE;
send(left, Cand (self.ID, 0, dmax) );
send(right, Cand (self.ID, 0, dmax) );
wait(end_phase) => {
// espera sinal do Monitor
if (remain==FALSE) state = lost;
else dmax = dmax * 2;
// dobra a distânca
}
}
}
Obs: Assumimos que next[k] relaciona os vizinhos da esq/direita:
• next[left] = right
• next[right] = left
© Markus Endler
12
A thread Monitor (1)
Loop {
received(k, Resp(bool,dest) ) =>
if (dest == self) {
Nr_replies++;
remain = remain  bool;
if (Nr_replies==2) signal (end_phase);
} else send(next(k), Resp(bool,dest) )
// forward Resp
}
received(k, Cand(ID,d,dmax) )=> {
if (ID < self.ID) {
send(k, Resp(FALSE,ID) );
if (state == not_involved) Election();
// start election
} elseif (ID > self.ID) {
state = lost;
d++;
if (d < dmax) send(next(k), Cand(ID,d,dmax) ); // forward
else send(k, Resp(TRUE, ID);
// reply to candidate
} elseif (state  elected) {
// ID == self.ID
state = elected;
// isto termina o while de Election()
winner = self.ID;
send(next(k), Elected(winner)); // announces in one direction
}
}
continua ...
© Markus Endler
13
A thread Monitor (2)
... continua
received(k, Elected(new) => {
if (winner  new) {
send(next(k), Elected(new));
winner = new;
state = not_involved;
}
}
}
A corretude do algoritmo deriva dos seguintes fatos:
• apenas o processo de maior ID (e.g. P.max) é capaz de receber a sua
própria msg Cand. Qualquer outro processo com ID < max terá a sua msg
Cand respondida negativamente por P.max.
• todos os processos ao longo dos caminhos (i-2j, i+2j) irão interferir na
eleição (responder negativamente), caso tenham ID maior do que o do
candidato
© Markus Endler
14
Eleição para Grafos Completos
• A topologia em anel é meio artificial, pois todos os processos
precisam estar ativos para repassar as mensagens...
• Suponhamos agora que:
– PID  [1, MAX]
– Processos podem estar ativos ou faltosos (não responder às
requisições)
– Durante a eleição processos podem falhar, ou voltar a ficarem
ativos (mas com o mesmo PID)
Objetivo: encontrar o maior PID dentre os processos ativos
Sugestões...?
p8
p1
p9
p3
p4
© Markus Endler
p2
15
O Algoritmo “Bully”
Garcia-Molina[GM82] propôs um algoritmo para um sistema síncrono
com falhas tipo fail-stop, baseado na difusão de mensagens
(conectividade total).
O algoritmo faz as seguintes suposições adicionais:
• Toda mensagem é entregue em Tm unidades de tempo após o seu
envio;
• Todos os processos não falhos respondem a todas as mensagens
recebidas em Tp unidades de tempo;
• Todos os processos têm acesso a uma memória não volátil
(p.exemplo: disco local ou Sist. de Arquivos Distribuído – NFS)
Com as duas primeiras suposições, é possível definir um detector de
falhas confiável: se um processo não responde em 2Tm+Tp
unidades de tempo, então tem-se certeza de que o mesmo falhou.
A terceira suposição é necessária para manter o registro de versões
(instâncias da eleição) em ordem estritamente crescente.
[GM82] Garcia-Molina. Elections in a Distributed Computing System,
IEEE Trans. On Computers, C-31(2),48-59, 1982.
© Markus Endler
16
Algoritmo Bully: Princípio de Funcionamento
• Periodicamente o atual coordenador verifica se a configuração do
grupo mudou (um processo falhou ou se recuperou de falha)  inicia
eleição
• Se algum participante desconfiar da falha do Coordenador  inicia
eleição
•Dentre os processos ativos em determinado momento, aquele com o
maior PID deve ser eleito o coordenador. Este tenta convencer os
demais intimidando-os (“bullying”).
• Antes de iniciar a1a. fase, o processo iniciador da eleição faz uma
consulta para ver se existe algum processo com maior PID. ( A
possibilidade da detecção confiável de falhas garante que somente o
processo de maior prioridade vai tentar ser o coordenador)
• A eleição funciona em 3 fases: ao final de cada fase, garante-se que
todos os processos não falhos estão sincronizados com o mesmo estado
(global) da eleição:
Normal >F1> Election >F2 > Reorganizing >F3> Normal
© Markus Endler
17
Algoritmo Bully: Princípio de Funcionamento
Principais Variáveis em cada Processo P:
State: um valor em {Down,Election,Reorganizing,Normal}
Coord: o ID do candidato a Coordenador, segundo a visão de P
Definition: o estado relevante da aplicação
Up:
conjunto de IDs de processos supostamente ativos no
grupo
halted: ID do processo que notificou P da eleição (iniciador)
Significado dos estados:
• Down = processo voltando de um período de falha
• Election = um (ou mais candidatos) tentando se estabelecer como
Coordenador
• Reorganizing = o estado da aplicação está sendo difundido para todos
os membros do grupo (p.exemplo a nova lista de membros ativos)
• Normal = processamento normal (até início da próxima eleição)
© Markus Endler
18
Segurança e Liveness
As propriedades de segurança (safety) e progresso (liveness) do algoritmo
são as seguintes:
Safety:
Seja G um estado global consistente(*). Então para quaisquer dois pares
de processos Pi e Pj as seguintes condições são satisfeitas em G:
• Se Pi e Pj estão nos estados {Normal,Reorganizing}, então Pi.Coord =
Pj.Coord
• Se Pi e Pj estão no estado Normal, então Pi.Definition = Pj.Definition
(estados sincronizados)
Liveness:
Seja G um estado consistente(*). Então as duas seguintes propriedades
estarão satisfeitas em algum ponto de qualquer processamento a partir
de G:
• Existe um Pi tal que Pi.State = Normal && Pi.Coord = Pi
• Para qualquer processo Pj não-falho, vale Pj.State = Normal &&
Pj.Coord = Pi
(*) Uma coleção de estados locais dos processos e canais de comunicação,
que de fato, poderia ter ocorrido em uma execução do sistema.
© Markus Endler
19
Detecção de Mudança no Grupo
Periodicamente:
• Coord verifica a existência de um processo ativo (com PID maior ou
menor do que PIDCoord )
• Coord verifica se todos os participante estão ativos (respondem à
mensagen AYNormal)
• Participante verifica se seu Coord. está ativo (mensagem AYUp)
Se alguém tiver detectado qq mudança inicia-se uma nova eleição...
• Quando um processo se recupera de uma falha, também inicia nova
eleição.
Obs: AY.. = AreYou...
© Markus Endler
20
Detecção de Mudança no Grupo
Coord
Part A
Part B
AYNormal
AYN_answer
AYUp
AYU_answer
crash
Election()
AYNormal
Election()
AYN_answer
Election()
AYUp
crash
Election()
Timer T
© Markus Endler
21
Execução da Eleição
P4
AYUp
P3
P2
P1
 P tq. P.ID > P3
C1
& P.State=Normal
EnterElection
P P.StateNormal
C2
SetCoord
NewState
© Markus Endler
P UP:
P.State=Reorg. 
P.Coord=P3
C3
C4
 P tq. (P.ID < P3) :
P.Coord  P
P UP:
P.State=Normal 
P.Coord=P3
22
Procedimentos que iniciam uma Eleição
• Qualquer processo que deixa de receber msg do coordenador
por um certo período  suspeita de sua falha
Check_Coordinator () {
if (State==Normal || State == Reorganizing) {
send (coord,AYUp);
set timer T;
}
received(coord, AYU_answer) => set timer T;
timeout T => Election();
}
• Qualquer processo que esteja voltando de um
período de falha
Recovery () {
State = Down;
Election();
}
© Markus Endler
23
Coordenador verifica o estado dos demais processos
Check_members() {
if (State==Normal && Coord == self) {
forall Pj: send (j,AYNormal);
set timer T;
replied = ;
}
loop {
received(k, AYN_answer, status) => {
replied = replied  {k};
if (k  Up && status  Normal) || k Up) {
Election();
// detected new or candidate process
exit;
}
timeout T => if  k ( k  Up && k  replied ) {
Election();
exit;
}
} // endloop
}
Obs: para cada tipo de mensagem existe uma mensagem de resposta
(AYNormal - AYN_answer, etc.)
© Markus Endler
24
Procedimento Election (1)
Election() {
highest = True;
forall P with P.ID > self.ID send(P, AYUp); // look for higher-priority processes
set timer T;
received(sender, AYU_answer) => {
highest = False; return;}
timeout T => ;
// wait only for certain amount of time
State = Election;
halted = self;
// I am the initiator and candidate
Up = ;
forall P s.th (P.ID < self.ID) send(P, EnterElection); // “invite” other participants
set timer T;
loop {
received(k, EE_answer) => Up = Up  {k}
timeout T => exit;
}
Coord = self;
State = Reorganizing;
Obs: participant= process with a lower PID
...
© Markus Endler
25
Procedimento Election (2)
...
num_answers = 0;
forall P  Up send(P,Set_Coord, self);
// try to establish (him)self as Coord
Set timer T;
loop {
received(k, SC_answer) => num_answers++;
timeout T =>
if (num_answers = | Up |) exit loop;
else { Election(), return; }
// set of participants has changed
}
num_answers = 0;
forall P  Up send(P,New_State, Definition) // sends state for synchronization
loop {
received(k, NS_answer) => num_answers++;
timeout T =>
if num_answers = | Up | exit loop;
else { Election(), return; }
// set of participants has changed
}
State = Normal
}
© Markus Endler
26
Thread Monitor
Loop {
received(k, M) => {
case M == AYUp: send(k,AYU_answer);
case M == AYNormal: send(k,state);
case M == EnterElection(k): {
State = Election;
suspend_normal_application processing
if (k > self)
// defines, in which Election will participate
stop_election_procedure (if executing)
halted = k;
send(k,EE_answer);
}
case M == Set_Coord(newCoord): {
if (State==Election && halted==newCoord) {
Coord = newCoord;
State = Reorganizing;
}
send(k, SC_answer); }
case M == NewState (NewDefinition) :
if (Coord == k && State = Reorganizing) {
Definition = newDefinition;
// updates state
State = Normal;
}
} // endloop
© Markus Endler
27
Algoritmo do Convite (Invitation Algorithm)
De Garcia-Molina[GM82] é também o Algoritmo do Convite, que:
• é uma variante do Algoritmo Bully para sistemas assíncronos e
• que trata a possibilidade de ocorrem partições na rede.
Sistemas Assíncronos:
• Sem a suposição sobre tempos máximos de processamento e
comunicação, não é possível saber com certeza se um
processo falhou. Sabe-se apenas que a comunicação (em certo
período) não está sendo possível.
Partições:
• Impossibilidade temporária da comunicação entre grupos de
processos
© Markus Endler
28
Algoritmo do Convite
Suposições do Modelo:
• Comunicação é segura
• Falhas do tipo fail-stop
• Nós guardam o estado em memória persistente (após se recuperar
de uma falha, conseguem recuperar o estado anterior)
• Processos podem ficar temporariamente isolados uns dos outros
(partições na rede)
• As mudanças de conectividade da rede ocorrem com baixa
freqüência
Características:
• Permite que existam mais de um grupo (com seu coordenador)
isolados
• Mas se houver alguma possibilidade de comunicação entre estes
grupos, eles irão se fundir
© Markus Endler
29
Algoritmo do Convite (Invitation Algorithm)
Ideia Central:
• em vez de se tentar eleger um coordenador para todos os
processos, elege-se somente o coordenador para cada um dos
grupos de processos cujos membros estão conseguindo
interagir
Obs: permite-se grupos unitários consistindo apenas do
candidato a coordenador!
• Periodicamente, cada coordenador verifica se existem outros
coordenadores, e tenta convidar todos os membros do grupo
correspondente a se juntar ao seu grupo.
• Para evitar que dois coordenadores fiquem se “roubando
mutuamente” membros do outro grupo, após a descoberta do
outro coordenador, este espera um tempo inversamente
proporcional à sua prioridade (valor do PID) até começar a
enviar os convites.
 Para isto, é necessário usar a noção de grupo, com um
identificador único (groupID)
© Markus Endler
30
Algoritmo do Convite
Adaptando as propriedades de segurança e progresso para o algoritmo do
convite:
Safety:
Seja G um estado consistente. Então para quaisquer dois pares de
processos Pi e Pj as seguintes condições são satisfeitas em G:
• Se Pi e Pj estão nos estados {Normal,Reorganizing} e Pi.Group =
Pj.Group, então Pi.Coord = Pj.Coord
• Se Pi e Pj estão no estado Normal, e Pi.Group = Pj.Group então
Pi.Definition = Pj.Definition
Liveness:
Seja R o conjunto máximo de processos mutuamente comunicáveis em
um estado consistente G. Então as duas seguintes propriedades serão
em algum momento satisfeitas (para qualquer processamento a partir
de G), contanto que o conjunto máximo de processos mutuamente
comunicáveis R permaneça igual e não ocorram outras falhas:
• Existe um Pi  R tal que Pi.State = Normal && Pi.Coord = Pi
• Para todos os processos Pj  R não-falhos, vale Pj.State = Normal &&
Pj.Coord = Pi
© Markus Endler
31
Algoritmo do Convite (Invitation Algorithm)
A propriedade de segurança é facil de ser satisfeita, pois depende
de como é escolhido o grupo (= pode ser qualquer conjunto de
processos que concorde em adotar o mesmo coordenador).
Para satisfazer a propriedade de progresso, precisa-se garantir
que:
• Se membros de grupos distintos conseguem se comunicar,
então em algum momento futuro, terá sido formado um novo
grupo (com coordenador único) contendo todos os processos
mutuamente comunicáveis (ou seja, o conjunto R).
Para tal, é necessário que os coordenadores dos grupos
correspondentes concordem sobre a formação de um novo
grupo contendo todos os membros dos grupos originais e um
único coordenador.
• Sucessivamente, grupos menores vão se aglutinando, até
formar um grupo contendo todo R.
• Cada coordenador, periodicamente tenta descobrir outros
coordenadores e executar um Merge() nos grupos tendo como
parâmetro a lista de outros coordenadores encontrados
(Others).
© Markus Endler
32
Funcionamento Básico
• Periodicamente, um coordenador difunde um AYCoord? tentando
contactar outros coordenadores, armazena o ID destes na variável
Other e tenta juntar os grupos (procedimento Merge(Other))
através de mensagens Invitation.
• Ao receber uma Invitation de outro coordenador, NC, um
coordenador C repassa esta mesagem para os participantes de
seu grupo, que respondem diretamente a NC usando msg Accept.
O próprio C também envia Accept para NC.
• O NC por sua vez confirma o seu papel de novo coordenador
através de Accept_answer. Se esta mensagem não chegar a
tempo, qualquer processo pode executar recovery();
• A seguir, NC envia a mensagem Ready com seu estado Definition
para todos os processos da união dos grupos originais.
Principais variáveis em cada processo:
State
// {Normal, Election, Reorganizing}
UpSet
// conjunto dos membros do próprio grupo
Up
// conjunto dos membros da união dos grupos
Group
// identificação do grupo (par [CoordID,count])
Others
// conjunto de outros coordenadores descobertos
© Markus Endler
33
Execução da Eleição
Merge(P2)
P4
Invitation P4
P3
P2
Accept
Accept_answer
P1
Invitation P4
Accept
Accept_answer
Up
Ready
Ready_answer
Grupo A
© Markus Endler
Grupo B
34
Coordenador procura por outros coordenadores
Periodicamente, cada coordenador verifica se consegue se comunicar com
outro coordenador (e coleta na variável Others as Ids correspondentes)
Check_members() {
if (State==Normal && Coord == self) {
Others = ;
forall Pj send (j,AYCoord);
set timer T;
}
loop {
received(k, AYC_answer, is_Coord) => {
if( is_Coord == TRUE) Others = Others  {k};
}
timeout T => if Others ==  return;
else exit;
}
} // endloop
set timer 1/self.Priority;
// higher priority coordinator merges first
timeout => Merge(Others);
}
Obs: Se um participante de outro grupo receber msg AYCoord, informa a
identidade de seu atual coordenador (em AYC_answer).
© Markus Endler
35
Tipos de Mensagem
origem  destino
AY_Coordinator
AYC_answer (bool)
AY_There (groupID)
AYT_answer (bool)
Invitation(newCoord, newGroup)
Accept (newGroup)
Accept_answer (bool)
Ready (newGroup, newDefinition)
Coord  any
Coord  Coord
Mem  Coord
Coord  Mem
C  C, C  Mem
any  Coord
Coord  any
Coord  any
Identificação do Grupo agora é composta de:
(ID do Coord, número de sequência)
© Markus Endler
36
Quando um Membro suspeita de falha do Coordenador
membro simplesmente cria um novo grupo contendo somente ele
próprio.
Check_Coord() {
// periodically called
if (Coord == self) return;
send(Coord, AYThere,Group);
set timer T;
is_Coord=FALSE;
received(k, AYT_answer, is_Coord) => { // coordenator is alive
if( is_Coord == TRUE) return;
timeout T => Recovery();
// coordenator has crashed
}
Recovery() {
State= Election;
stop_processing();
Counter++;
Group = (self Counter);
Coord = self;
Up = ;
State = Reorganizing;
Definition = my_appl_state;
State = Normal;
}
© Markus Endler
// creates a new group
37
O procedimento Merge
Merge(CoordSet) {
if (Coord == self) && (State = Normal) {
State = Election;
suspend_processing_application;
Counter++;
Group = (self Counter);
// creates a new group
UpSet = Up;
Up =
;
set timer T1;
foreach p  (CoordSet  UpSet) send(p, Invitation(self,Group));
// replies “Accept” collected in UP by monitor thread
when timeout T1=> {
// waits T1 for accept replies
State= Reorganizing;
Nr_answers=0;
set timer T2;
foreach p  Up send(p, Ready(Group,Definition));
loop {
when revd(Ready_answer(sender,inGroup, newGroup) => {
if (inGroup==TRUE  newGroup==Group) Nr_answers++;
when timeout T2 => {
// waits T2 for Ready_answers
if (Nr_answers < | Up |) Recovery();
else state = Normal;
} // endloop
}
}
© Markus Endler
38
Thread para tratar um Convite
Cada processo (participante|coordenador) precisa executar uma thread para
tratar mensagens Invitation.
loop {
when State == Normal  recv(p, Invitation(newCoord, newGroup) => {
suspend_processing_application;
oldCoord = Coord;
UpSet = Up;
// UpSet: the members of its own group
State = Election;
Coord = newCoord;
Group = newGroup;
if (oldCoord == self)
// if coordenador, forward to members
foreach p  UpSet send(p, Invitation(Coord,Group)) ;
send(Coord, Accept(Group));
set timer T;
when recv (Coord, Accept_answer(accepted)) => { }
when timeout T => { accepted = FALSE}
if (accepted == FALSE) Recovery();
State = Reorganizing;
}
}
© Markus Endler
39
Thread Monitor para responder às mensagens
Loop {
received(k, M) => {
// receiving a message from process k
case M == Ready(newGroup,newDefinition):
if (Group==newGroup)  State == Reorganizing {
Definition = newDefinition; // only if in Reorganizing
State = Normal;
send(Coord, Ready_answer(True, Group));
} else
send(k, Ready_answer(False));
case M == AYCoordinator:
if (State==Normal  Coord==self)
send(k, AYC_answer(TRUE));
else
send(k, AYC_answer(FALSE));
case M == AYThere(oldGroup):
if (Group==oldGroup  Coord==self  k  Up)
send(k, AYT_answer(TRUE);
else
send(k, AYT_answer(FALSE);
case M == Accept(newGroup):
if State==Election  Coord==self
 Group==newGroup { // only if in Election and for new Group
Up = Up  {k}
// Up is used by Merge()
send(k, Accept_answer(TRUE));
} else
send(k, Accept_answer(FALSE));
}
} // endloop
© Markus Endler
40
O Modelo de Sistema
•
•
•
•
Sincronismo
Comunicação
Tipos de Falhas
Estabilidade do sistema
© Markus Endler
41
Conclusões sobre o Algoritmo do Convite
Por não fazer qualquer suposição sobre o sincronismo do
sistema, este algoritmo é de utilidade prática e até é
mais simples do que o Algoritmo Bully.
A corretude do mesmo se baseia na idéia de consistência
relativa, que é muito usada em sistemas assíncronos:
• aplica-se a exigência de consistência (concordância
sobre o Coord e lista de membros) somente para os
atuais membros do grupo
• Não há qualquer requisito sobre corretude/consistência
da visão do grupo total. Esta é atualizada pela lei do
“melhor esforço” (p.ex. inclusão esponânea de novos
membros, unificação de grupos quando há descoberta
mútua, etc)
• Por exemplo: se existirem dois grupos a serem
juntados, então somente se não houver outras falhas
durante o Merge (incluindo as falhas de comunicação),
em algum momento futuro os grupos serão unificados;
© Markus Endler
42