Um problema fundamental em sistemas de processamento distribuído é alcançar a confiabilidade geral do sistema com a existência de processos defeituosos. Ademais, isso, normalmente, requer que processos concordem que algum dado ou valor é necessário durante uma computação. Exemplos de aplicações de consenso distribuído incluem confirmar ou não uma transação para indefinida base de dados e concordar em relação à identidade de um líder.
Descrição do problema O problema do consenso requer um acordo entre certa quantidade de processos para um único dado. Dessa forma, alguns dos processos podem falhar ou não ter uma boa confiabilidade em outros aspectos, por conseguinte, protocolos de consenso devem ser tolerante a falhas. Os processos devem, de alguma forma, fortalecer seus valores candidatos, se comunicar uns com os outros e entrar num acordo em relação a um único valor.
Uma possível abordagem para atingir o consenso é que todos os processos concordem num valor da maioria. Nesse contexto, a maioria requer, pelo menos, mais da metade dos votos disponíveis (onde cada processo tem direito a um voto). No entanto, um ou mais processos defeituosos podem enviesar o resultado, de modo que o consenso não seja atingido ou que seja atingido incorretamente.
Protocolos que resolvem problemas de consenso são feitos para lidar com um número limitado de processos defeituosos. Esses protocolos devem satisfazer uma certa quantidade de requisitos para que ele seja utilizável. Por exemplo, um protocolo trivial poderia configurar as saídas de todos os processos para o valor binário 1. Dessa forma, ele não seria utilizável e, sendo assim, o requisito é modificado de maneira que a saída deva depender, de algum modo, da entrada. Ou seja, o valor de saída de um protocolo de consenso deve ser o valor de entrada de algum dos processos. Outro requisito é que o processo tenha a possibilidade de escolher e dar como saída apenas um valor onde essa decisão é irrevogável. Um processo é considerado não defeituoso numa execução se ele não apresentar nenhuma falha. Logo, um protocolo de consenso que tolere falhas deve satisfazer as seguintes propriedades
Término Todo processo não defeituoso deve escolher um valor Validação Se todos os processos propuserem um mesmo valor , então todos os processos não defeituosos devem escolher . Integridade Todo processo não defeituoso deve escolher no máximo um valor, e se ele escolher algum valor , então deve ter sido proposto por algum processo. Acordo Todo processo não-defeituoso deve concordar com o mesmo valor.
Um protocolo que pode garantir corretamente o consenso entre n processos em que no máximo t falham é chamado t-resiliente.
Ao avaliar o desempenho de protocolos de consenso, há dois fatores importantes: o tempo de execução e a complexidade da mensagem. O tempo de execução é dado na notação grande-O em relação ao número de rodadas de troca de mensagens como uma função de algum parâmetro de entrada (normalmente o número de processos e/ou o tamanho da entrada). Complexidade da mensagem se refere à quantidade de tráfego de mensagem que é gerado pelo protocolo. Outros fatores podem ser uso de memória e tamanho das mensagens.
Modelos de computação Existem dois tipos de falhas que um processo pode sofrer, um falha de mau funcionamento ou uma falha do tipo byzantine. Uma falha de mau funcionamento ocorre quando um processo para abruptamente e não é retomado. Falhas do tipo Byzantine são falhas que absolutamente nenhuma condição é imposta. Por exemplo, elas podem acontecer como consequência das ações maliciosas de um adversário. Um processo que experimenta uma falha do tipo byzantine pode mandar dados contraditórios ou entrar em conflito com os dados de outros processos, assim como, ele também pode ficar inativo e então retomar a atividade depois de uma demora grande. Dentre os dois tipos de falha, o maior destaque torna-se a do tipo byzantine, afinal são muito mais disruptivas. Assim, um protocolo de consenso que tolere falhas do tipo byzantine deve ser resiliente a todo erro possível que venha a ocorrer.
Um versão mais resistente do protocolo de consenso que tolera falhas do tipo byzantine é mostrado abaixo:
Término Todo processo não defeituoso deve escolher um valor ValidaçãoSe todos os processos não defeituosos propuserem um mesmo valor , então todos os processos não defeituosos devem escolher . Integridade Se um processo não defeituoso escolhe , então deve ter sido proposto por algum processo não defeituoso. Acordo Todo processo não defeituoso deve concordar com o mesmo valor.
Vários modelos de computação podem definir um problema de consenso. Alguns modelos podem lidar com grafos completamente conectados enquanto outros podem lidar com estruturas de dados circulares e árvores. Devem ser considerados para o envio de mensagens modelos síncronos e assíncronos. Em alguns modelos, autenticação de mensagem é permitida; enquanto que em outros, os processos são inteiramente anônimos. Modelos com memória compartilhada, em que processos comunicam-se ao acessar objetos na memória compartilhada, também é uma área de pesquisa importante.
Um caso especial do problema de consenso chamado de consenso binário restringe o número de valores na entrada e, consequentemente, o domínio da saída para um único dígito binário {0,1}. Quando o domínio da entrada é grande em relação ao número de processos, por exemplo, o conjunto dos números naturais, torna-se evidente que o consenso é impossível num modelo síncrono de troca de mensagens.
Por outro viés, enquanto que a comunicação no mundo real é, de modo geral, inerentemente assíncrona, é mais prático e vantajoso modelar sistemas síncronos. Em sistemas distribuídos completamente assíncronos de troca de mensagens, em que um processo possa ter uma falha de funcionamento, foi provado que atingir um consenso é impossível. Entretanto, essa impossibilidade vem do pior cenário de um escalonamento de processo. Ademais, é importante ressaltar que esse cenário é altamente improvável. Na realidade, escalonamento de processos possui certo grau de aleatoriedade.
Num modelo assíncrono, algumas falhas podem ser tratadas por um protocolo de consenso síncrono. Por exemplo, a perda de um vínculo de comunicação pode ser modelada como um processo que sofreu uma falha do tipo Byzantine.
Em sistemas síncronos presume-se que todas as comunicações aconteçam em rodadas. Em apenas uma rodada, um processo pode mandar todas as mensagens que são necessárias enquanto recebe todas as mensagens enviadas por outros processos. Dessa maneira, nenhuma mensagem de uma determinada rodada pode influenciar outra mensagem desta mesma rodada.
Equivalência de problemas de consenso
Três importantes problemas de consenso estão listados abaixo.
Difusão confiável terminante (Terminating Reliable Broadcast)
Um conjunto de n processos, numerados de 0 a n - 1, comunicam-se enviando mensagens uns para os outros. O processo 0 deve transmitir um valor v para todos os outros processos de modo que:
se o processo 0 não é defeituoso, então todo processo que não seja defeituoso deve receber v para qualquer dois processos não defeituosos, cada um deve receber o mesmo valor.
Esse problema também é conhecido como "problema do general".
Consenso Requisitos formais para um protocolo de consenso podem ser:
Concordância: Todo processo não defeituoso deve concordar com o mesmo valor. Validação fraca: Se todo processo não defeituoso receber o mesmo valor de entrada, então eles devem todos dar como saída aquele valor. Validação forte: Para cada processo não defeituoso, a sua saída deve ser a entrada de algum processo não defeituoso. Término: Todos processos devem, eventualmente, escolher um valor para dar como saída.
Consistência interativa fraca (Weak Interactive Consistency)
Para n processos num sistema parcialmente síncrono (o sistema alterna entre bons e maus períodos de sincronia), cada processo escolhe um valor privado. Os processos comunicam-se uns com os outros por rodadas para determinar algum valor público e gerar um vetor de consenso com os seguintes requisitos:
se um processo não defeituoso envia , então todo processo não defeituoso ou recebe ou não recebe nada (propriedade da integridade) todas as mensagens mandadas numa rodada por um processo não defeituoso são recebidas na mesma rodada por todos processos não defeituosos (propriedade da consistência).
Desse modo, pode ser mostrado que variações desses problemas são equivalentes no sentido de que a solução de um problema, em um tipo de modelo, pode ser a solução de outro problema em um tipo de modelo diferente. Por exemplo, a solução para o problema dos generais bizantinos fraco num modelo síncrono de troca de mensagens autenticadas, leva a um solução da Consistência Interativa Fraca. Um algoritmo de consistência interativa pode resolver o problema do consenso ao fazer com que cada processo escolha o valor da maioria em seu vetor de consenso, assim como o valor de consenso.
Resultado de solubilidade de alguns problemas de consenso
Existe um protocolo t-resiliente síncrono e anônimo que resolve o problema dos generais bizantinos, se t/n < 1/3, e também o caso dos generais bizantinos fraco onde t é o número de falhas e n é o número de processos.
Para um sistema de três processadores em que um deles é do tipo byzantine, não há solução para o problema de consenso usando um modelo binário síncrono de troca de mensagem.
Num sistema inteiramente assíncrono não há um consenso que tolere uma ou mais falhas de funcionamento, até mesmo quando é apenas requisitada a propriedade da não-trivialidade. Esse resultado é algumas vezes chamado de prova FLP de impossibilidade. Os autores Michael J. Fischer, Nancy Lynch e Mike Paterson foram premiados com um Dijkstra Prize pela importância do trabalho. O resultado FLP não afirma que o consenso nunca poderá ser atingido; ele diz meramente que, sob as premissas do modelo, nenhum algoritmo pode sempre atingir um consenso no tempo delimitado. Na prática, é altamente improvável de atingir um consenso.
Alguns protocolos de consenso Um exemplo de um protocolo de consenso binário tolerante a falhas do tipo Byzantine de tempo polinomial é o algoritmo Phase King feito por Garay e Berman. Esse algoritmo consegue atingir um consenso num modelo síncrono de troca de mensagens com n processos e com um máximo de f falhas, provido n > 4f.
No algoritmo phase king, existem f + 1 fases, com duas rodadas por fase.
Cada processo rastreia sua saída preferida (que inicialmente é igual ao próprio valor de entrada do processo). Na primeira rodada de casa fase, cada processo transmite a todos os outros o seu valor preferido no momento. Ele, então, recebe os valores de todos os processos e determina qual valor é o da maioria e sua contagem. Na segunda rodada da fase, o processo cuja identidade corresponde ao número da fase atual é designado o rei da fase. O rei envia a todos o valor da maioria, que foi observado por ele na primeira rodada e serve como desempate. Daí, cada processo atualiza seu valor preferido da seguinte forma: Se a contagem do valor da maioria que o processo observou na primeira rodada for maior que n/2 + f, o processo muda sua preferência para o valor da maioria; caso contrário, ele usa o valor informado pelo rei da fase. No fim das f + 1 fases, os processos informam seus valores escolhidos.
O Google implementou uma biblioteca de serviço de bloqueio distribuído chamada Chubby. Chubby mantém informações de bloqueio em pequenos arquivos que são armazenados num banco de dados replicado para prover uma alta disponibilidade em face de falhas. O banco de dados é implementado no topo de uma camada de registro de eventos tolerante a falhas que é baseado no algoritmo de consenso de "Paxos". Nesse esquema, clientes Chubby se comunicam com o mestre Paxos com o objetivo de acessar/atualizar a cópia do registro de eventos; i.e., ler/escrever nos arquivos.