Consenso distribuído

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^{[carece de fontes]}

Término

Todo processo não defeituoso deve escolher um valor

Validação

Se todos os processos propuserem um mesmo valor $v$, então todos os processos não defeituosos devem escolher $v$.

Integridade

Todo processo não defeituoso deve escolher no máximo um valor, e se ele escolher algum valor $v$, então $v$ 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ção

Se todos os processos não defeituosos propuserem um mesmo valor $v$, então todos os processos não defeituosos devem escolher $v$.

Integridade

Se um processo não defeituoso escolhe $v$, então $v$ 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)

Ver artigo principal: 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:

1. se o processo 0 não é defeituoso, então todo processo que não seja defeituoso deve receber v
2. 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:

1. se um processo não defeituoso envia $v$, então todo processo não defeituoso ou recebe $v$ ou não recebe nada (propriedade da integridade)
2. 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.

Bitcoin usa proof of work (prova de trabalho) para manter sua rede peer-to-peer. Nós na rede de bitcoin tentam resolver um problema criptográfico de proof-of-work, onde a probabilidade de achar uma solução é proporcional ao esforço computacional, em hashes (tabelas) por segundo, gastos, e o nó que resolve o problema tem sua versão do bloco de transações adicionado ao servidor, em que o mesmo é assegurado por tempo e distribuído peer-to-peer, além dele ser aceito por todos os outros nós. Como qualquer nó na rede pode tentar resolver o problema de proof-of-work, um ataque Sybil torna-se inviável a não ser que o atacante tenha mais que 50% dos recursos computacionais da rede.

Ripple é um protocolo aberto usado para transferências monetárias via web, ou seja, ele facilita as transferências de dinheiro entre instituições. Uma de suas características principais é que ele possibilita a conversão entre (diversas) moedas sem envolver as criptomoedas como bitcoin, por exemplo. Dois bancos americanos parassaram a dar suporte ao protocolo: O New Jersey-based Cross River Bank e o CBW Bank, o que evidencia seu potencial. Quanto ao funcionamento de seu algoritmo de consenso, um requisito comum nesse tipo de sistema, em que todos os nós da rede devem se comunicar sincronamente, é contornado; utiliza-se sub-redes coletivamente confiáveis dentro da rede maior possibilitando a diminuição da latência introduzida pelo requisito, além de manter a robustez do algoritmo de consenso em face de falhas do tipo Byzantine.

Stellar, assim como bitcoin e Ripple, opera com um protocolo descentralizado e aberto que facilita o envio e recebimento de dinheiro em múltiplas moedas. O projeto possui uma moeda digital interna com o mesmo nome, também como bitcoin e Ripple. Quanto ao funcionamento de seu esquema de consenso, os servidores Stellar se comunicam e se sincronizam uns com os outros para garantir que as transações sejam válidas e aplicadas com sucesso na contabilidade global. Todo esse processo de chegar a um consenso ocorre aproximadamente de 2 a 5 segundos.

Vários jogos online peer-to-peer de estratégia em tempo real usam um protocolo de Lockstep (modificado) como um protocolo de consenso, com o intuito de gerenciar o estado do jogo entre jogadores numa partida. Cada ação do jogo resulta numa transmissão delta do estado do jogo para todos os jogadores no jogo juntamente com uma hash contendo todo o estado do jogo. Cada jogador valida a mudança ao aplicar o delta ao seu próprio estado do jogo. Se as hashes de estado do jogo. Se as hashes não chegarem num consenso, então um voto é lançado, e aqueles jogadores cujo estado do jogo está na minoria são desconectados e removidos do jogo (conhecido como desync.).

Aplicações de protocolos de consenso

Uma importante aplicação de protocolo de consenso é prover sincronização. Métodos tradicionais de acesso concorrente a dados compartilhados implementam alguma forma de exclusão mútua através de travas/bloqueios. Contudo, a desvantagem é que se um processo "morre" enquanto ele está na região crítica, outro processo não defeituoso pode nunca obter acesso à região. Assim, exclusão mútua não é bem adequada a sistemas assíncronos tolerante a falhas. Uma implementação livre de espera de um objeto que dê suporte a acessos concorrentes garante que qualquer processo pode completar sua execução dentro de um número finito de passos independente do comportamento de outros processos. Objetos atômicos, como registradores de leitura e escrita, foram propostos para a implementação de sincronização livre de espera. Todavia, foi mostrado que tais objetos, assim como primitivas tradicionais como test&set (teste & configure) e fetch&add (pegue & adicione), não podem ser usados para tais implementações.

Leituras futuras

• Herlihy, M.; Shavit, N. (1999). «The topological structure of asynchronous computability». Journal of the ACM. 46 (6). 858 páginas. doi:10.1145/331524.331529 
• Saks, M.; Zaharoglou, F. (2000). «Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge». SIAM J. Comput. 29 (5): 1449–1483. doi:10.1137/S0097539796307698