Problema dos dois generais

Em computação, o Problema dos Dois Generais, é um experimento mental para ilustrar as armadilhas e desafios de planejamento na tentativa de coordenar uma ação através da comunicação sobre uma enlace não confiável. Está relacionado a um problema mais geral conhecido como o Problema dos Generais Bizantinos (embora publicado muito antes dessa generalização) e aparece com frequência em aulas introdutórias sobre redes de computadores (em especial com relação ao Protocolo de Controle de Transmissão, onde ele mostra que o TCP não pode garantir a consistência de estado entre as extremidades e também o porquê), embora se aplique a qualquer tipo de comunicação entre dois pontos onde falhas de comunicação podem ocorrer. Um conceito-chave na lógica epistêmica, este problema destaca a importância do conhecimento comum. Alguns autores também se referem a este problema como Paradoxo dos Dois Generais, Problema dos Dois Exércitos ou Problema de Ataque Coordenado. O Problema dos Dois Generais foi o primeiro problema de comunicação de computador provado ser insolúvel. Uma consequência importante desta prova é que as generalizações, como o Problema dos Generais Bizantinos, também são insolúveis na presença de falhas de comunicação arbitrárias, proporcionando assim uma base de expectativas realistas para quaisquer protocolos de consistência distribuída.

Definição

Dois exércitos, cada um liderado por um general, estão se preparando para atacar uma cidade fortificada. Os exércitos estão acampados próximo à cidade, cada um em sua própria montanha. Um vale separa as duas montanhas, e a única forma dos dois generais se comunicarem é por meio do envio de mensageiros através do vale. Infelizmente, o vale é ocupado pelos defensores da cidade e há a chance que algum mensageiro enviado seja capturado.

Posições dos exércitos. Exércitos A1 e A2 precisam se comunicar, mas seus mensageiros podem ser capturados pelo exército B.

Enquanto os dois generais concordaram que irão atacar, eles não concordaram sobre a hora do ataque. É necessário que os dois generais tenham seus exércitos atacando a cidade ao mesmo tempo para ter sucesso, caso contrário o solitário exército atacante irá morrer tentando. Eles devem, portanto, se comunicar um com o outro para decidir a hora de atacar e para concordar em atacar na mesma hora, e cada general deve saber que ambos chegaram a um acordo no plano de ataque. Como a confirmação de recebimento de mensagem pode ser perdida facilmente como a mensagem original, uma série potencialmente infinita de mensagens são necessárias para se chegar a um consenso.

O experimento mental envolve considerar como eles podem prosseguir para chegar a um consenso. Em sua forma mais simples, um general é dito ser o líder, decide a hora do ataque e deve comunicar essa hora ao outro general. O problema é chegar com algoritmos que os generais podem usar, incluindo o envio de mensagens e o processamento de mensagens recebidas, que pode permiti-los concluir corretamente:

Sim, vamos atacar na hora marcada.

A partir daí é bastante simples para os generais chegarem a um acordo sobre a hora de atacar (i.e. uma mensagem bem sucedida, com confirmação bem sucedida). Porém, a sutileza do Problema dos Dois Generais está na impossibilidade de projetar algoritmos que sejam utilizados pelos generais para concordar de forma segura com o enunciado acima.

Ilustrando o problema

O primeiro general pode começar enviando uma mensagem "Ataque às 09:00 em 4 de agosto." No entanto, uma vez enviada, o primeiro general não tem ideia se o mensageiro entregou ou não. Essa incerteza pode levar o primeiro general a hesitar a atacar, devido ao risco de ser o único atacante.

Para ter certeza, o segundo general pode enviar uma confirmação de volta para o primeiro: "eu recebi a sua mensagem e iremos atacar às 09:00 em 4 de agosto." No entanto, o mensageiro carregando a confirmação pode ser capturado e o segundo general pode hesitar, sabendo que o primeiro não faria nada sem a sua confirmação.

Mais confirmações podem parecer uma solução - deixe o primeiro general enviar uma segunda confirmação: "recebi sua confirmação do ataque planejado às 09:00 em 4 de agosto." No entanto, esse novo mensageiro do primeiro general, também está sujeito a ser capturado. Assim, rapidamente se torna evidente que não importa quantas rodadas de confirmação sejam feitas, não há maneira de garantir a segunda condição, de que cada general está ciente de que o outro concordou no plano de ataque. Seja qual for o general, que envie o último mensageiro, sempre estará na dúvida se o mensageiro entregou ou não.

Prova

Para protocolos determinísticos com um número fixo de mensagens

Devido ao fato de este protocolo ser determinístico, suponha que exista uma seqüência de um número fixo de mensagens, uma ou mais entregue com êxito e uma ou mais não. A suposição é de que deve haver uma certeza compartilhada para que os dois generais ataquem.

Considere a última mensagem que foi entregue com sucesso. Se a última mensagem não foi entregue com sucesso, então um general pelo menos (provavelmente, o receptor) decidiria não atacar. Do ponto de vista do remetente da última mensagem, no entanto, a seqüência de mensagens enviadas e entregues seria exatamente a mesma se a aquela última mensagem tivesse sido entregue.

Sendo o protocolo determinístico, o general que enviar a última mensagem decidirá atacar. Agora criamos uma situação onde o protocolo sugerido leva um general a atacar e o outro não - contradizendo a hipótese de que o protocolo foi uma solução para o problema.

Para protocolos não-determinísticos e de comprimento variável

Um protocolo não-determinístico com uma contagem de mensagem variável pode ser comparado a uma grafo infinito, onde cada folha ou ramo (nó) no grafo representa um exemplo explorado até um determinado ponto.

As raízes deste grafo são rotuladas com as possíveis mensagens iniciais, e o ramo de nós decorrente destas raízes são rotuladas com as prováveis próximas mensagens. As folhas representam exemplos que terminam após o envio da última mensagem. Um protocolo que termina antes de enviar qualquer mensagem é representada por um grafo vazio.

Suponha que existe um protocolo não-determinístico que resolve o problema. Então, através de um argumento semelhante para o exemplo determinístico na seção anterior, onde um pode ser obtido a partir do outro apenas removendo todos as folhas, o protocolo determinístico deve então resolver o problema.

Sendo o protocolo não-determinístico finito, então o protocolo representado pelo grafo vazio resolveria o problema. Claramente que isso não é possível. Portanto, um protocolo não-determinístico que resolve o problema não existe.

Abordagens de engenharia

Uma abordagem pragmática para lidar com o Problema dos Dois Generais é a utilização de esquemas que aceitem a incerteza do canal de comunicações e não tentar eliminá-lo, mas, em vez disso reduzi-la a um nível aceitável. Por exemplo, o primeiro general, pode enviar 100 mensageiros, antecipando que a probabilidade de todos serem capturadas é baixa. Com esta abordagem, o primeiro general atacará sem se importar, e o segundo general atacará se alguma mensagem for recebida. De forma alternativa, o primeiro general pode enviar um fluxo de mensagens e o segundo general enviar as confirmações para cada, com cada general se sentindo mais confortável com toda mensagem recebida. No entanto, como visto na prova, nenhum pode ter certeza que o ataque será coordenado. Não há algoritmo que eles possam usar (e.g. ataque se mais de quatro mensagens forem recebidas), que dará certeza de impedir o ataque de um sem o outro. Além disso, o primeiro general pode enviar uma marcação em cada mensagem como 1, 2, 3 ... n. Este método permitirá que o segundo general saiba o quão confiável é o canal e enviar um número apropriado de mensagens de volta para assegurar uma alta probabilidade de pelo menos uma mensagem ser recebida. Se o canal for confiável, então, uma mensagem será suficiente e as demais mensagens não serão mais necessárias. A última é tão provável de se perder quanto a primeira.

Partindo do princípio de que os generais devem sacrificar vidas toda vez que um mensageiro é enviado e interceptado, um algoritmo pode ser projetado para minimizar o número de mensageiros necessário para atingir a quantidade máxima de confiança de que o ataque está coordenado. Para salvá-los de sacrificar centenas de vidas para atingir uma alta confiança na coordenação, os generais poderiam concordar com a utilização da ausência de mensageiros como uma indicação de que o general que começou a transação recebeu pelo menos uma confirmação, e se comprometeu a atacar. Suponha que leva um minuto para um mensageiro atravessar a zona de perigo. Permitindo que 200 minutos de silêncio ocorram após as confirmações terem sido recebidas, nos permite alcançar confiança extremamente alta sem sacrificar vidas de mensageiros. Neste caso, os mensageiros são usados somente no caso de uma das partes não ter recebido a hora do ataque. No final de 200 minutos, cada general pode argumentar: "eu não recebi uma mensagem adicional em 200 minutos; ou 200 mensageiros não conseguiram atravessar a zona de perigo, ou significa que o outro general confirmou e se comprometeu com o ataque e crê que eu também confirmarei e me comprometerei".

História

O Problema dos Dois Generais e sua prova de impossibilidade foi primeiro publicado por E. A. Akkoyunlu, K. Ekanadham, e R. V. Huber em 1975 em "Some Constraints and Trade-offs in the Design of Network Communications", onde é descrito começando na página 73 no contexto de comunicação entre dois grupos de gangsters.

Foi dado a este problema o nome de Paradoxo dos Dois Generais por Jim Gray em 1978 em "Notes on Data Base Operating Systems" começando na página 465. Esta referência é amplamente tida como uma fonte para a definição do problema e a prova da impossibilidade, embora ambos tenham sido publicados anteriormente como dito acima.