b'\n_START_ARTICLE_\nProblema dos dois generais\n_START_PARAGRAPH_\nEm computa\xc3\xa7\xc3\xa3o, o Problema dos Dois Generais, \xc3\xa9 um experimento mental\xc2\xa0para ilustrar as armadilhas e desafios de planejamento na tentativa de coordenar uma a\xc3\xa7\xc3\xa3o atrav\xc3\xa9s da comunica\xc3\xa7\xc3\xa3o sobre uma enlace n\xc3\xa3o confi\xc3\xa1vel. Est\xc3\xa1 relacionado a um problema mais geral conhecido como o Problema dos\xc2\xa0Generais Bizantinos\xc2\xa0(embora publicado muito antes dessa generaliza\xc3\xa7\xc3\xa3o) e aparece com frequ\xc3\xaancia em aulas introdut\xc3\xb3rias sobre redes de computadores (em especial com rela\xc3\xa7\xc3\xa3o ao Protocolo de Controle de Transmiss\xc3\xa3o, onde ele mostra que o TCP n\xc3\xa3o pode garantir a consist\xc3\xaancia de estado entre as extremidades e tamb\xc3\xa9m o porqu\xc3\xaa), embora se aplique a qualquer tipo de comunica\xc3\xa7\xc3\xa3o entre dois pontos onde falhas de comunica\xc3\xa7\xc3\xa3o podem ocorrer. Um conceito-chave na l\xc3\xb3gica epist\xc3\xaamica, este problema destaca a import\xc3\xa2ncia do conhecimento comum. Alguns autores tamb\xc3\xa9m se referem a este problema como\xc2\xa0Paradoxo dos\xc2\xa0Dois Generais,\xc2\xa0Problema dos Dois Ex\xc3\xa9rcitos\xc2\xa0ou\xc2\xa0Problema de Ataque Coordenado. O Problema dos Dois Generais foi o primeiro problema de comunica\xc3\xa7\xc3\xa3o de computador provado ser insol\xc3\xbavel. Uma consequ\xc3\xaancia importante desta prova \xc3\xa9 que as generaliza\xc3\xa7\xc3\xb5es, como o Problema dos Generais Bizantinos, tamb\xc3\xa9m s\xc3\xa3o insol\xc3\xbaveis na presen\xc3\xa7a de falhas de comunica\xc3\xa7\xc3\xa3o arbitr\xc3\xa1rias, proporcionando assim uma base de expectativas realistas para quaisquer protocolos de consist\xc3\xaancia distribu\xc3\xadda.\n_START_SECTION_\nIlustrando o problema\n_START_PARAGRAPH_\nO primeiro general pode come\xc3\xa7ar enviando uma mensagem "Ataque \xc3\xa0s 09:00 em 4 de agosto." No entanto, uma vez enviada, o primeiro general n\xc3\xa3o tem ideia se o mensageiro entregou ou n\xc3\xa3o.\xc2\xa0Essa incerteza pode levar o primeiro general a hesitar a atacar, devido ao risco de ser o \xc3\xbanico atacante._NEWLINE_Para ter certeza, o segundo general pode enviar uma confirma\xc3\xa7\xc3\xa3o de volta para o primeiro: "eu recebi a sua mensagem e iremos atacar \xc3\xa0s 09:00 em 4 de agosto." No entanto, o mensageiro carregando a confirma\xc3\xa7\xc3\xa3o pode ser capturado e o segundo general pode hesitar, sabendo que o primeiro n\xc3\xa3o faria nada sem a sua confirma\xc3\xa7\xc3\xa3o._NEWLINE_Mais confirma\xc3\xa7\xc3\xb5es podem parecer uma solu\xc3\xa7\xc3\xa3o - deixe o primeiro general enviar uma segunda confirma\xc3\xa7\xc3\xa3o: "recebi sua confirma\xc3\xa7\xc3\xa3o do ataque planejado \xc3\xa0s 09:00 em 4 de agosto." No entanto, esse novo mensageiro do primeiro general, tamb\xc3\xa9m est\xc3\xa1 sujeito a ser capturado. Assim, rapidamente se torna evidente que n\xc3\xa3o importa quantas rodadas de confirma\xc3\xa7\xc3\xa3o sejam feitas, n\xc3\xa3o h\xc3\xa1 maneira de garantir a segunda condi\xc3\xa7\xc3\xa3o, de que cada general est\xc3\xa1 ciente de que o outro concordou no plano de ataque. Seja qual for o general, que envie o \xc3\xbaltimo mensageiro, sempre estar\xc3\xa1 na d\xc3\xbavida se o mensageiro entregou ou n\xc3\xa3o.\n_START_SECTION_\nPara protocolos determin\xc3\xadsticos com um n\xc3\xbamero fixo de mensagens\n_START_PARAGRAPH_\nDevido ao fato de este protocolo ser\xc2\xa0determin\xc3\xadstico, suponha que exista uma seq\xc3\xbc\xc3\xaancia de um n\xc3\xbamero fixo de mensagens, uma ou mais entregue com \xc3\xaaxito e uma ou mais n\xc3\xa3o. A suposi\xc3\xa7\xc3\xa3o \xc3\xa9 de que deve haver uma certeza compartilhada para que os dois generais ataquem._NEWLINE_Considere a \xc3\xbaltima mensagem que foi entregue com sucesso. Se a \xc3\xbaltima mensagem n\xc3\xa3o foi entregue com sucesso, ent\xc3\xa3o um general pelo menos (provavelmente, o receptor) decidiria n\xc3\xa3o atacar. Do ponto de vista do remetente da \xc3\xbaltima mensagem, no entanto, a seq\xc3\xbc\xc3\xaancia de mensagens enviadas e entregues seria exatamente a mesma se a aquela \xc3\xbaltima mensagem tivesse sido entregue._NEWLINE_Sendo o protocolo\xc2\xa0determin\xc3\xadstico, o general que enviar a \xc3\xbaltima mensagem decidir\xc3\xa1 atacar. Agora criamos uma situa\xc3\xa7\xc3\xa3o onde o protocolo sugerido leva um general a atacar e o outro n\xc3\xa3o - contradizendo a hip\xc3\xb3tese de que o protocolo foi uma solu\xc3\xa7\xc3\xa3o para o problema.\n_START_SECTION_\nPara protocolos n\xc3\xa3o-determin\xc3\xadsticos e de comprimento vari\xc3\xa1vel\n_START_PARAGRAPH_\nUm protocolo\xc2\xa0n\xc3\xa3o-determin\xc3\xadstico\xc2\xa0com uma contagem de mensagem vari\xc3\xa1vel pode ser comparado a uma\xc2\xa0grafo\xc2\xa0infinito, onde cada folha ou ramo (n\xc3\xb3) no grafo representa um exemplo explorado at\xc3\xa9 um determinado ponto._NEWLINE_As ra\xc3\xadzes deste grafo s\xc3\xa3o rotuladas com as poss\xc3\xadveis mensagens iniciais, e o ramo de n\xc3\xb3s decorrente destas ra\xc3\xadzes s\xc3\xa3o rotuladas com as prov\xc3\xa1veis pr\xc3\xb3ximas mensagens. As folhas representam exemplos que terminam ap\xc3\xb3s o envio da \xc3\xbaltima mensagem. Um protocolo que termina antes de enviar qualquer mensagem \xc3\xa9 representada por um grafo vazio._NEWLINE_Suponha que existe um protocolo\xc2\xa0n\xc3\xa3o-determin\xc3\xadstico\xc2\xa0que resolve o problema. Ent\xc3\xa3o, atrav\xc3\xa9s de um argumento semelhante para o exemplo\xc2\xa0determin\xc3\xadstico\xc2\xa0na se\xc3\xa7\xc3\xa3o anterior, onde um pode ser obtido a partir do outro apenas removendo todos as folhas, o protocolo\xc2\xa0determin\xc3\xadstico\xc2\xa0deve ent\xc3\xa3o resolver o problema._NEWLINE_Sendo o protocolo\xc2\xa0n\xc3\xa3o-determin\xc3\xadstico\xc2\xa0finito, ent\xc3\xa3o o protocolo representado pelo grafo vazio resolveria o problema. Claramente que isso n\xc3\xa3o \xc3\xa9 poss\xc3\xadvel. Portanto, um protocolo\xc2\xa0n\xc3\xa3o-determin\xc3\xadstico\xc2\xa0que resolve o problema n\xc3\xa3o existe.\n_START_SECTION_\nAbordagens de engenharia\n_START_PARAGRAPH_\nUma abordagem pragm\xc3\xa1tica para lidar com o Problema dos Dois Generais \xc3\xa9 a utiliza\xc3\xa7\xc3\xa3o de esquemas que aceitem a incerteza do canal de\xc2\xa0comunica\xc3\xa7\xc3\xb5es\xc2\xa0e n\xc3\xa3o tentar elimin\xc3\xa1-lo, mas, em vez disso reduzi-la a um n\xc3\xadvel aceit\xc3\xa1vel. Por exemplo, o primeiro general, pode enviar 100 mensageiros, antecipando que a probabilidade de todos serem capturadas \xc3\xa9 baixa. Com esta abordagem, o primeiro general atacar\xc3\xa1 sem se importar, e o segundo general atacar\xc3\xa1 se alguma mensagem for recebida. De forma alternativa, o primeiro general pode enviar um fluxo de mensagens e o segundo general enviar as confirma\xc3\xa7\xc3\xb5es para cada, com cada general se sentindo mais confort\xc3\xa1vel com toda mensagem recebida. No entanto, como visto na prova, nenhum pode ter certeza que o ataque ser\xc3\xa1 coordenado. N\xc3\xa3o h\xc3\xa1 algoritmo que eles possam usar (e.g. ataque se mais de quatro mensagens forem recebidas), que dar\xc3\xa1 certeza de impedir o ataque de um sem o outro. Al\xc3\xa9m disso, o primeiro general pode enviar uma marca\xc3\xa7\xc3\xa3o em cada mensagem como 1, 2, 3 ... n. Este m\xc3\xa9todo permitir\xc3\xa1 que o segundo general saiba o qu\xc3\xa3o confi\xc3\xa1vel \xc3\xa9 o canal e enviar um n\xc3\xbamero apropriado de mensagens de volta para assegurar uma alta probabilidade de pelo menos uma mensagem ser recebida. Se o canal for confi\xc3\xa1vel, ent\xc3\xa3o, uma mensagem ser\xc3\xa1 suficiente e as demais mensagens n\xc3\xa3o ser\xc3\xa3o mais necess\xc3\xa1rias. A \xc3\xbaltima \xc3\xa9 t\xc3\xa3o prov\xc3\xa1vel de se perder quanto a primeira._NEWLINE_Partindo do princ\xc3\xadpio de que os generais devem sacrificar vidas toda vez que um mensageiro \xc3\xa9 enviado e interceptado, um algoritmo pode ser projetado para minimizar o n\xc3\xbamero de mensageiros necess\xc3\xa1rio para atingir a quantidade m\xc3\xa1xima de confian\xc3\xa7a de que o ataque est\xc3\xa1 coordenado. Para salv\xc3\xa1-los de sacrificar centenas de vidas para atingir uma alta confian\xc3\xa7a na coordena\xc3\xa7\xc3\xa3o, os generais poderiam concordar com a utiliza\xc3\xa7\xc3\xa3o da aus\xc3\xaancia de mensageiros como uma indica\xc3\xa7\xc3\xa3o de que o general que come\xc3\xa7ou a transa\xc3\xa7\xc3\xa3o recebeu pelo menos uma confirma\xc3\xa7\xc3\xa3o, e se comprometeu a atacar. Suponha que leva um minuto para um mensageiro atravessar a zona de perigo. Permitindo que 200 minutos de sil\xc3\xaancio ocorram ap\xc3\xb3s as confirma\xc3\xa7\xc3\xb5es terem sido recebidas, nos permite alcan\xc3\xa7ar confian\xc3\xa7a extremamente alta sem sacrificar vidas de mensageiros.\xc2\xa0Neste caso, os mensageiros s\xc3\xa3o usados somente no caso de uma das partes n\xc3\xa3o ter recebido a hora do ataque. No final de 200 minutos, cada general pode argumentar: "eu n\xc3\xa3o recebi uma mensagem adicional em 200 minutos; ou 200 mensageiros n\xc3\xa3o conseguiram atravessar a zona de perigo, ou significa que o outro general confirmou e se comprometeu com o ataque e cr\xc3\xaa que eu tamb\xc3\xa9m confirmarei e me comprometerei".\n_START_SECTION_\nHist\xc3\xb3ria\n_START_PARAGRAPH_\nO 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 \xc3\xa9 descrito come\xc3\xa7ando na p\xc3\xa1gina 73 no contexto de comunica\xc3\xa7\xc3\xa3o entre dois grupos de gangsters._NEWLINE_Foi dado a este problema o nome de Paradoxo dos Dois Generais\xc2\xa0por\xc2\xa0Jim Gray\xc2\xa0em 1978 em "Notes on Data Base Operating Systems" come\xc3\xa7ando na p\xc3\xa1gina 465. Esta refer\xc3\xaancia \xc3\xa9 amplamente tida como uma fonte para a defini\xc3\xa7\xc3\xa3o do problema e a prova da impossibilidade, embora ambos tenham sido publicados anteriormente como dito acima.'