Simulação de uma Versão do Algoritmo de Consenso Paxos

Introdução

O objetivo deste segundo trabalho prático é implementar uma versão do algoritmo de consenso Paxos. Nesta versão o algoritmo deve considerar falhas Crash e utilizar canais de comunicação confiáveis, ou seja, não haverá perda de mensagens durante a comunicação entre os processos. Na tentativa de realizar o consenso, o sistema identificará processos falhos, para os quais não serão enviadas as mensagens. Além disso, todos os demais processos serão comunicados sobre a existência desses processos falhos assim que eles forem identificados. Nos resultados mostrados nas próximas seções serão mostradas algumas simulações que sempre se encerram assim que um processo consegue o consenso com os demais. Serão mostrados ainda resultados de simulações em que mais de um processo se considera líder e o algoritmo tem que lidar com a rejeição de mensagens por parte de alguns processos em virtude da aceitação de uma mensagem recebida anteriormente. Detalhes sobre o funcionamento serão descritos a seguir.

Implementação

A implementação inicialmente definiu duas estruturas para serem utilizadas. A definição dos dados de um processo e da mensagem enviada. A definição do processo utilizou a mesma estrutura utilizada para a definição dos nodos no trabalho prático 1, apenas foram acrescentados os campos id_atual para controlar a geração dos identificadores das mensagens. Como os processos podem, independente um dos outros, gerar novos identificadores cada vez que uma mensagem sua é rejeitada, o controle dos id's fica associado ao próprio processo. Da mesma forma o id_aceito identifica qual o id da mensagem que foi aceita por aquele processo. Isso será necessário quando um processo precisar saber qual o id da mensagem que foi aceita pelo processo que causou a rejeição por parte deste processo. Por fim, o campo vl_consenso identifica qual o valor que o processo deseja que os demais processos “aceitem”, ou seja, qual será o valor “combinado” com os demais após o consenso. Na implementação aqui apresentada vl_consenso será o próprio id da mensagem, a fim de simplificar a implementação uma vez que este valor é indiferente para o objetivo proposto. A estrutura do processo é apresentada na Figura 1.

Figura 1 – Definição do Processo

A mensagem, conforme apresentado na Figura 2, contém os campos “id”, que será gerado a partir do “id_atual” do processo; um vetor “tempo” com N posições, onde N será o número de processos existentes e guardará o tempo aleatório gerado para que cada processo processe o recebimento da mensagem; “instante” que armazena o instante de tempo da criação da mensagem e será usada para comparar o momento do processamento da mensagem com o instante de criação + o tempo decorrido para o processamento da mensagem; um vetor “aceite”, também com N posições que indica quais os processos que já aceitaram a mensagem enviada, e com isso poder identificar quando o consenso já é possível e por fim o valor que deseja-se sincronizar com os demais processos.

Figura 2 – Definição da Mensagem

Inicialmente a simulação escalona o processo 0 para enviar uma mensagem, considerando-o como o líder. Antes do envio da mensagem ele verifica o status dos demais processos. Caso identifique algum como falho ele não faz o envio da mensagem a este processo e seta o vetor STATE de todos os processos para comunicar a falha no referido processo. Para cada um dos processos que receberão a mensagem e feita a geração de um número aleatório que corresponde ao instante de tempo em que o processo receberá a mensagem, para que ocorram atrasos e esta situação possa ser tratada pelo algoritmo.

No recebimento da mensagem é feita a verificação se o processo já aceitou alguma mensagem com ID maior do que este que foi enviado. Se não ele envia ACK para os demais processos e seta o seu próprio campo “id_aceito” com o número do ID da mensagem enviada. Caso já houver a aceitação de uma mensagem com ID maior, ele envia NACK para os demais. Uma decisão de implementação adotada é que, mesmo que mais de um processo se julgue líder, a validação será feita pelo ID da mensagem, ou seja, mesmo que um processo faça o envio de uma mensagem, caso ele receba uma mensagem com ID maior ele aceitará a mensagem enviada.

Quando um processo recebe um ACK ele verifica se já há maioria de ACK para a mensagem que ele enviou. Em caso afirmativo ele fará o consenso, e caso contrário ele deve aguardar. Esta maioria leva em conta apenas os processos não-falhos.

Quando um processo recebe um NACK, independente da quantidade de ACK recebida ele deve gerar novamente um ID, baseado no ID aceito pelo processo que enviou o NACK, e reenvia a mensagem para os demais.

Todos os envios de mensagem, seja a mensagem inicial do líder, ou o envio de ACK e de NACK, verifica o status dos demais processos para identificação de processos falhos.

Por fim, quando todos os processo tiverem recebido o valor do consenso, o sistema é interrompido e é informada a obtenção do consenso.

Código Fonte Implementado

Simulações Realizadas

As simulações seguiram duas possibilidades iniciais. Um único líder enviando mensagem para os demais (mostrada nos logs 1, 2 e 3). Ou dois processos se considerando líder e enviando mensagem para os demais (mostrada nos logs 4 e 5). Outras variações consideraram a existência ou não de processos falhos. A descrição de cada uma das simulações é apresentada na Tabela 1.

Tabela 1 – Descrição das Simulações Realizadas

Análise das Simulações Realizadas

Em todos os casos simulados o consenso foi atingido. Para os casos em que mais de um processo se considera líder foi necessário gerar rodadas extras de envio de mensagem em função da rejeição de mensagens. Nos casos em que havia um único líder o consenso foi mais natural a partir do recebimento da mensagem pelos processos.

Outro ponto avaliado se refere à existência de processos falhos. Também nesses casos a simulação obteve o consenso conseguindo identificar os processos falhos, seja no início ou no meio da simulação, e ainda não menos importante, soube considerar os processo falhos (ou seja, não incluí-los na análise) no momento de avaliar se a maioria dos processos havia enviado ACK para a mensagem ou não.

Conclusão

A conclusão advém da própria análise das simulações. Ademais, além do comportamento esperado obtido em todos os testes, é importante ressaltar que o resultado foi obtido com o estabelecimento de algumas premissas:

1) Os canais de comunicação são confiáveis. De fato, todas as mensagens enviadas durante as simulações não se perderam e chegaram a seus destinos.

2) Completude, isto é, após um tempo todas as falhas são identificadas (e no nosso caso, passam a ser conhecidas imediatamente por todos os processos).

3) Acurácia, não há suspeitas sobre processos corretos. No cenário proposto, não foi tratada a situação de suspeitar de um processo correto. Ou seja, a acurácia esteve presente naturalmente, uma vez que cada processo sempre foi tratado como correto a não ser que sua falha fosse de fato detectada. Esta premissa foi fundamental, uma vez que a acurácia é difícil de ser obtida em sistemas reais.

4) Acordo, ou seja, todos os processos corretos decidem pelo mesmo valor. As simulações foram encerradas assim que o acordo fosse obtido.

5) Validade, em que um processo correto, quando decide por um valor, este valor foi proposto por um processo correto. Nas simulações, processos falhos não fizeram proposta de valores.

6) Terminação, isto é, todo processo correto eventually decide por um valor. Novamente, conforme descrito no item 4, todas as simulações foram encerradas corretamente e dentro de um intervalo de tempo que fizesse parte do intervalo considerado para a simulação. Isso se deveu, sobretudo, ao intervalo de tempo aleatório para o recebimento das mensagem considerar um valor de 0 a 100. Ou seja, não foi permitido intervalos extremamente longos. Para os demais envios (ACK e NACK) os envios e recebimentos aconteciam instantaneamente, e portanto sem risco de atrasos consideráveis.

Referências Bibliográficas

Kivsch, J. & Amir, Y. Paxos for System Builders An Overview”. Proceedings of the 2008 Workshop on Large-Scale Distributed Systems and Middleware (LADIS 2008), Yorktown, NY.2008.

Duarte, E. P. Sistemas Distribuídos - Notas de Aula. 2015.