Mostrar código-fonte de Consenso distribuído

Um problema fundamental em [[Sistema de processamento distribuído|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 [[Eleição de líder|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 [[Tolerância a falhas (hardware)|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 [[Processo (informática)|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|data=dezembro de 2015}}

;Término: Todo processo não defeituoso deve escolher um valor
;Validação: Se todos os processos propuserem um mesmo valor <math>v</math>, então todos os processos não defeituosos devem escolher <math>v</math>.
;Integridade: Todo processo não defeituoso deve escolher no máximo um valor, e se ele escolher algum valor <math>v</math>, então <math>v</math> 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 <math>v</math>, então todos os processos não defeituosos devem escolher <math>v</math>.
;Integridade: Se um processo não defeituoso escolhe <math>v</math>, então <math>v</math> 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.<ref name="aguilera_stumbling">{{citar periódico| doi = 10.1007/978-3-642-11294-2_4|título= Stumbling over Consensus Research: Misunderstandings and Issues| volume = 5959|páginas= 59–72| series = Lecture Notes in Computer Science|ano= 2010|último1 = Aguilera |primeiro1 = M. K. | isbn = 978-3-642-11293-5}}</ref> 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.<ref name="fischer_impossibility">{{citar periódico |último1 = Fischer |primeiro1 = M. J. |authorlink1 = Michael J. Fischer |último2 = Lynch |primeiro2 = N. A. |authorlink2 = Nancy Lynch |último3 = Paterson |primeiro3 = M. S. |authorlink3 = Michael S. Paterson |doi = 10.1145/3149.214121 |título = Impossibility of distributed consensus with one faulty process |periódico = [[Journal of the ACM]] |volume = 32 |número = 2 |páginas = 374–382 |ano = 1985 |url = http://theory.lcs.mit.edu/tds/papers/Lynch/jacm85.pdf |acessodata = 2015-12-18 |arquivourl = https://web.archive.org/web/20070705132628/http://theory.lcs.mit.edu/tds/papers/Lynch/jacm85.pdf |arquivodata = 2007-07-05 |urlmorta = yes }}</ref> 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.<ref name="aguilera_stumbling"/>

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)=== 
{{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:

# 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:<ref>{{citar periódico|último =Milosevic|primeiro =Zarko|autor2 =Martin Hutle |autor3 =Andre Schiper |título=Unifying  Byzantine Consensus Algorithms with Weak Interactive Consistency|periódico=Principles of Distributed Systems, Lecture Notes in Computer Science|ano=2009|volume=5293|páginas=300–314|doi=10.1007/978-3-642-10877-8_24}}</ref>

# se um processo não defeituoso envia <math>v</math>, então todo processo não defeituoso ou recebe <math>v</math> 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.<ref name="lamport_WBGP">{{citar periódico| doi = 10.1145/2402.322398|título= The Weak Byzantine Generals Problem|periódico= Journal of the ACM| volume = 30|número= 3|páginas= 668|ano= 1983|último1 = Lamport |primeiro1 = L.}}</ref> 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.<ref>{{citar web|último =Fischer|primeiro =Michael J|título=The Consensus Problem in Unreliable Distributed Systems (A Brief Survey)|url=http://zoo.cs.yale.edu/classes/cs426/2012/bib/fischer83consensus.pdf|acessodata=21 de abril de 2014}}</ref>

==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, <ref>{{citar periódico|último1 = Lamport |primeiro1 = L. | authorlink1 = Leslie Lamport|último2 = Shostak |primeiro2 = R. |último3 = Pease |primeiro3 = M. | doi = 10.1145/357172.357176 |título= The Byzantine Generals Problem |periódico= ACM Transactions on Programming Languages and Systems | volume = 4 |número= 3 |páginas= 382–401 |ano=1982 | url = http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf}}</ref><ref>{{citar periódico|último =Lamport|primeiro =Leslie|autor2 =Marshall Pease |autor3 =Robert Shostak |título=Reaching Agreement in the Presence of Faults|periódico=Journal of the ACM|data=abril de 1980|volume=27|número=2|páginas=228–234|doi=10.1145/322186.322188|pmid=|url=http://research.microsoft.com/users/lamport/pubs/reaching.pdf|acessodata=2007-07-25}}</ref> se t/n < 1/3, e também o caso dos generais bizantinos fraco<ref name="lamport_WBGP"/> 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.<ref>{{citar livro|primeiro =Hagit|último =Attiya|autorlink = Hagit Attiya |título=Distributed Computing 2nd Ed|ano=2004|publicado=Wiley|isbn=978-0-471-45324-6|páginas=101–103}}</ref>

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.<ref name="fischer_impossibility"/> 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''<ref>{{citar periódico|último =Berman|primeiro =Piotr|autor2 =Juan A. Garay|título=Cloture Votes: n/4-resilient Distributed Consensus in t + 1 rounds|periódico=Theory of Computing Systems|volume=26|series=2|páginas=3–19|doi=10.1007/BF01187072|url=http://www.springerlink.com/content/gx21355767268411/|acessodata=19 de dezembro de 2011}}</ref> 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'' > 4''f''.

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 [[Distributed lock manager#Google's Chubby lock service|Chubby]].<ref>
{{citar conferência
  |título=The Chubby lock service for loosely-coupled distributed systems
  |autor =Burrows, M.
  |conferencia=Proceedings of the 7th [[Symposium on Operating Systems Design and Implementation]]
  |páginas=335–350
  |ano=2006
  |publicado=USENIX Association Berkeley, CA, USA
  |   url=http://research.google.com/archive/chubby-osdi06.pdf
}}</ref> 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.<ref>{{citar conferência
  |primeiro = Tushar
  |último = C.
  |autorlink = |autor2 =Griesemer, R |autor3 =Redstone J.
  |título= Paxos Made Live - An Engineering Perspective
  |conferencia= Proceedings of the Twenty-sixth Annual ACM [[Symposium on Principles of Distributed Computing]]
  |páginas= 398–407
  |publicado= ACM Press New York, NY, USA
  |ano= 2007
  |local= Portland, Oregon, USA
  | url = http://delivery.acm.org/10.1145/1290000/1281103/p398-chandra.pdf?key1=1281103&key2=4382532021&coll=GUIDE&dl=GUIDE&CFID=15324100&CFTOKEN=95510390
  | doi = 10.1145/1281100.1281103
  |acessodata= 2008-02-06
}}</ref>

[[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 (payment protocol)|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.

[[Protocolo Stellar|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.<ref>{{citar web|último =Herlihy|primeiro =Maurice|título=Wait-Free Synchronization|url=http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf|acessodata=19 de dezembro de 2011}}</ref>

==Referências==
{{Reflist|30em}}

==Leituras futuras==
*{{citar periódico|último1 = Herlihy |primeiro1 = M. |último2 = Shavit |primeiro2 = N. | doi = 10.1145/331524.331529 |título= The topological structure of asynchronous computability |periódico= Journal of the ACM | volume = 46 |número= 6 |páginas= 858 |ano= 1999 | pmid =  | pmc = }}
*{{citar periódico|último1 = Saks |primeiro1 = M. |último2 = Zaharoglou |primeiro2 = F. |título= Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge |periódico= [[SIAM Journal on Computing|SIAM J. Comput.]] | volume = 29 |número= 5 |páginas= 1449–1483 |ano= 2000 | doi = 10.1137/S0097539796307698}}

{{DEFAULTSORT:Consenso Distribuido}}
[[Categoria:Sistemas computacionais tolerantes a falhas]]