14

Eleição de líder é um problema da área de sistemas distribuídos que busca selecionar de forma consensual um processo num conjunto de processos tendo como objetivo selecionar um líder para uma determinada tarefa wikipedia

Em computação distribuída como funciona a eleição de um líder? Quando é que a escolha de um líder é importante?

10
  • Eu estava tentando fazer uma pergunta para aboradar alguns problemas das computacao das nuvens e agora decidi separar. De modo a que as perguntas nao sejam amplas demais. 2/11/2016 às 8:55
  • 1
    Como essa pergunta entra no escopo do site? Pergunto porque já votei pra fechar a outra mas gostaria de entender o que torna esta dentro do escopo para que eu não vote novamente.
    – user28595
    2/11/2016 às 14:09
  • @diegofm Depende do ponto de vista. Eu considero a pergunta cair em dúvidas teóricas sobre conceitos e práticas aplicados ao desenvolvimento de software. Eu nao concordei com o fecho da minha outra pergunta por ser fora do escopo (nem vale a pena discutir isso). Mas ela era de fato ampla demais (eu mesmo votei para fechar como ampla demais). 2/11/2016 às 14:16
  • Eu acho no escopo no sentido de ser um problema de programação, mas acho ampla no sentido de que tem infinitas maneiras, se não puser um cenário específico. Fica a recomendação já dada nas outras, de editar por um cenário para estudo de caso. Talvez alguém consiga postar uma resposta com as principais técnicas resumidas, quem sabe. Vamos ver o que acontece.
    – Bacco
    5/11/2016 às 23:12
  • @Bacco Eu não posso exigir nenhum tipo de resposta mas sim o ideal era uma resposta que resumisse as técnicas principais. 5/11/2016 às 23:27

1 Resposta 1

9
+50

Em sua pergunta já existe a resposta, talvez para entendê-la melhor deve-se conceituar inicialmente computação distribuída.

Sistema Distribuído

Um sistema de processamento distribuído ou paralelo é um sistema que interliga vários nós de processamento (computadores individuais, não necessariamente homogéneos) de maneira que um processo de grande consumo seja executado no nó "mais disponível", ou mesmo subdividido por vários nós. Conseguindo-se, portanto, ganhos óbvios nestas soluções: uma tarefa qualquer, se divisível em várias subtarefas pode ser realizada em paralelo.

Quando é que a escolha de um líder é importante?

A eleição torna-se necessária quando o sistema distribuído está sendo iniciado pela primeira vez ou o líder anterior não consegue se comunicar com os demais processos pela ocorrência de alguma falha.

Em computação distribuída como funciona a eleição de um líder?

Há vários algoritmos que realizam a eleição do líder, cada um específico a alguma situação.

Algoritmo em anel

O algoritmo em anel ou LCR, iniciais de Le Lann, Chang e Roberts, serve para eleger um líder se os processos estiverem dispostos em um anel. Cada processo deve conhecer seu vizinho à direita e à esquerda e deve ter um identificador numérico, único, fixo e atribuído antes do início da eleição. Originalmente este algoritmo visava a recuperação de um token perdido em uma rede com topologia em forma de anel, elegendo um nó da rede que servisse como ponto de partida para o novo token.

A execução do algoritmo busca eleger o processo de maior identificador e fazer com que todos os membros do anel reconheçam o novo líder.

Se um dos nós identifica a perda do token, inicia a eleição enviando uma mensagem de eleição com o seu número de nó ao vizinho da direita. Se o nó que recebe a mensagem de eleição tem um identificador maior que o informado na mensagem que recebeu, passa uma mensagem de eleição para seu vizinho da direita com seu próprio identificador. Caso contrário aceita que o nó que tem o identificador contido na mensagem será o líder e repassa ao seu vizinho da direita. Se o nó recebe uma mensagem com o identificador idêntico ao seu, ele se declara líder. Este evento só ocorre quando a mensagem contendo o maior identificador circulou por todo o anel tornando todos os seus membros cientes do resultado.

Algoritmo de bully

O algoritmo de bully serve para eleger um líder entre processos identificados por um identificador numérico, único, fixo e atribuído antes do início da eleição. Entretanto neste caso a topologia não é limitada a um anel e cada um dos processos pode se comunicar com qualquer outro no sistema. Novamente a execução do algoritmo busca eleger o processo de maior identificador e fazer com que todos reconheçam o novo líder.

Se um dos processos identifica a perda de contato com o líder, inicia uma nova eleição enviando a todos os outros uma mensagem contendo seu identificador. Todos os nós respondem ao processo que iniciou a eleição com os seus próprios identificadores. Se o processo que iniciou a eleição possuir o maior identificador entre todos os outros, proclama-se líder e avisa todos os outros, senão aguarda que o processo de maior identificador inicie uma eleição e se torne líder. Este algoritmo possui este nome justamente por seu comportamento de bully (intimidador/valentão). O processo de maior identificador predomina sobre os de menor número e mesmo que um destes ganhe uma eleição, rapidamente toma o posto do eleito propondo uma nova eleição.

Wiki-pt

inserir a descrição da imagem aqui

Exemplo

#!/usr/bin/python
import socket
import os
import sys

## Variaveis globais
mySock = 0
## Path onde estao os sockets
SPATH='/tmp/bully'

## Funcao q manda mensagem
def sendMsg(dest,msg):
        global mySock
        try:
                ns = socket.socket(socket.AF_UNIX,socket.SOCK_STREAM)
                ns.connect((dest))
                ns.send(msg+';'+mySock)
                ns.close()
                return 1
        except:
                return 0
## Funcao q fica se comunicando com o coordenador para ver se esta ativo
def verificaCoord(coord):
        global SPATH
        global mySock

        while True:
                ## Verifica se o coordenador esta ativo
                status = sendMsg(coord,'1')
                if status == 0:
                        print 'Coodenador parado '+str(coord)+'. Iniciando Eleicao'
                        list = os.listdir(SPATH)
                        for i in list:
                                if int(i) > int(mySock):
                                        status = sendMsg(i,'E')
                                        if status == 0:
                                                print 'Erro enviando E ao processo '+i
                        break
                else:
                        print 'Conectou no coordenador '+coord
        return 0

def main():
        ## Variaveis
        fCord = 1
        BUF=1024

        global mySock
        global SPATH
        try:
                ## Se recebeu um argumento he um processo recussitado
                mySock = sys.argv[1]
                ## Testa se existem processos com prioridade maior
                list = os.listdir(SPATH)
                for i in list:
                        if int(i) > int(mySock):
                                status = sendMsg(i,'1')
                                if status == 1:
                                        fCord = 0 ## Se houver processos maiores, nao he coordenador
                                        continue
                ## Se for o maior anuncia a todos
                if fCord == 1:
                        for i in list:
                                if int(i) < int(mySock):
                                        status = sendMsg(i,'C')
        except:
                ## Nome do socket = pid do processo
                mySock=str(os.getpid())
                fCord = 0
        print 'Iniciando. PID='+str(mySock)
        ## Verifica se existe o diretorio para os sockets
        try:
                os.chdir(SPATH)
        except:
                ## Se nao existe cria o diretorio
                os.mkdir(SPATH)
        try:
                ## Cria o socket
                s = socket.socket(socket.AF_UNIX,socket.SOCK_STREAM)
                s.bind((mySock)) ## Atribui um nome ao socket
                s.listen(1) ## Estabelece fila para conexoes
                ## Inicialmente o menor PID he o coordenador
                list = os.listdir(SPATH)
                ## Ordena os pids e pega o primeiro
                list.sort(cmp)
                if list:
                        COORD=list[0]
                else:
                        COORD=mySock
                ## Nao he o coordenador
                if COORD != mySock and fCord == 0:
                        ## Divide o processo
                        childPID = os.fork()
                        if childPID == 0:
                                ## O filho permanece testando o coordenador
                                verificaCoord(COORD)
                                #sys.exit(1)
                else:
                        COORD = mySock
                        print 'Eu sou o coordenador '+str(mySock)
                ## Todos os processos pais permanecem em wait, aguardando conexao
                conn, addr = s.accept()
                data = conn.recv(BUF)
                while True:
                        if data:
                                msg = data.split(';')
                                ## Se a mensagem recebida for de eleicao
                                if msg[0] == 'E':
                                        print 'Recebido mensagem '+msg[0]+' de PID='+str(msg[1])
                                        ## Enviar msg para pid menor parar eleicao
                                        sendMsg(msg[1],'PE')
                                        #procura se tem alguem maior q ele
                                        list = os.listdir(SPATH)
                                        maior = 1
                                        for i in list:
                                                if int(i) > int(mySock):
                                                        #print 'Enviar para PID '+i
                                                        status = sendMsg(i,'E')
                                                        if status == 1:
                                                                maior = 0
                                        #se for o maior envia msg para todos como novo coord.
                                        if maior == 1:
                                                print 'Eu sou o novo Coordenador '+str(mySock)
                                                os.kill(childPID,9)
                                                for i in list:
                                                        if int(i) < int(mySock):
                                                                print 'enviando C para '+str(i)
                                                                send = sendMsg(i,'C')

                                ## Recebeu msg para parar eleicao
                                if msg[0] == 'PE':
                                        print 'Recebida mensagem '+msg[0]+' de PID='+str(msg[1])
                                ## Recebeu msg de verificacao de conexao
                                #if msg[0] == '1':
                                #       print 'Recebida mensagem '+msg[0]+' de PID='+str(msg[1])
                                ## Recebeu msg de coordenador
                                if msg[0] == 'C':
                                        print 'Novo coordenador '+msg[1]
                                        os.kill(childPID,9)
                                        childPID = os.fork()
                                        if childPID == 0:
                                                ## Novo filho gerado monitora o novo coordenador
                                                verificaCoord(msg[1])
                                                #sys.exit(1)
                                data = conn.recv(BUF)
                        else:
                                conn, addr = s.accept()
                                data = conn.recv(BUF)
        except:
                print "Unexpected error:", sys.exc_info()[0]
                s.close()
                os.remove(SPATH+'/'+str(mySock))
                print 'Processo '+str(mySock)+' parando'


## Invoca a funcao main na inicializacao do programa
if __name__ == '__main__':
        main()

Mais informações em inglês Wiki-en

1

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .