두 장군 문제

정의

다른 장군이 이끌고 있는 두 군대는 요새화된 도시를 공격 할 준비를 하고 있습니다. 군대는 도시 근처, 각각 계곡에 자리 잡고 있습니다. 세 번째 계곡은 두 언덕을 갈라 놓고, 두 장군이 통신 할 수 있는 유일한 방법은 메신저를 계곡을 통해 보내는 것입니다. 불행히도, 계곡은 도시의 군대에 의해 점령되고 있으며, 계곡을 통해 보내진 어떤 사자는 붙잡힐 가능성이 있습니다. 두 장군은 공격에는 동의했지만 공격 시간을 합의하지 않았습니다. 두 명의 장군은 그들의 공격이 성공하기 위해서는 도시를 동시에 공격해야 합니다. 그렇지 않으면, 단독으로 공격을 시도한 군대가 죽을 것입니다. 따라서, 그들은 공격 할 시간을 결정하고 그 시간에 공격에 동의하기 위해 서로 의사 소통해야 하며, 각 장군은 상대방이 공격 계획에 동의했음을 알고 있어야 합니다. 메시지 수신 확인은 원래 메시지만큼 쉽게 손실 될 수 있으므로 잠재적으로 무한한 일련의 메시지가 합의에 도달해야 합니다. 사고 실험은 그들이 어떻게 합의에 도달할 지를 고려하는 것입니다. 가장 간단한 형태로, 지도자인 것으로 알려진 한 장군이, 공격 시기를 결정하고, 이 시간을 다른 장군에게 알려야 합니다. 이 문제는 메시지를 보내고, 받은 메시지를 처리하는 등 장군이 사용할 수 있는 알고리즘을 도출해 내고 올바르게 결론을 내릴 수 있어야 합니다. 예, 두 장군은 합의된 시간에 함께 공격할 것입니다. 장군이 공격 할 시간에 동의하게하는 것이 매우 간단하다는 것을 허용하면 (즉, 성공적인 승인을 가진 하나의 성공적인 메시지), 두 장군 문제의 미묘함은 장군들 위의 진술에 안전하게 동의하기 위해 사용하는 알고리즘을 설계하는 것은 불가능하다는 것입니다.

문제의 설명

첫 번째 장군은 "8 월 4 일 9시에 공격"이라는 메시지를 보내 시작할 수 있습니다. 그러나 일단 파견되면, 첫 번째 장군은 메신저가 통과했는지 여부를 알 수 없습니다. 이러한 불확실은 첫 번째 장군이 단독으로 공격하게 될 위험 때문에 공격을 주저하게 합니다. 확실히, 두 번째 장군은 "나는 당신의 메시지를 받았고 8 월 4 일 9시에 공격 할 것입니다."라고 확인 메시지를 보낼 수 있습니다. 그러나 메신저는 잡힐 수 있어서 두 번째 장군은 첫 번째 장군이 확인 메세지가 없어서 물러날 수 있음을 알기 때문에 망설이게 됩니다. 더 많은 확인 메세지가 해결책처럼 보일 수 있습니다. 첫 번째 장군이 "8월 4일 9시에 계획된 공격에 대한 당신의 확인을 받았습니다."라는 두번째 확인 메세지를 보냅니다. 그러나 첫 번째 장군이 보낸 새로운 전령 역시 잡힐 수 있습니다. 따라서 확인 횟수가 아무리 많아도 증거가 될 수 업습니다. 한 장군이 다른 장군이 공격 계획에 동의했는지에 대한 두 번째 요구 사항을 보장 할 방법이 없습니다. 두 장군은 항상 마지막 메신저가 통과했는지에 대해 의문을 가지게 됩니다.

정해진 수의 메세지를 갖는 결정적 프로토콜의 경우

이 프로토콜은 결정적이기 때문에 하나 이상의 메세지가 성공적으로 배달이 되거나 그렇지 않은, 고정 된 수의 메시지 순서가 있다고 가정합니다. 이 가정은 이 공격 할 수 것이라는 공통된 확신이 있어야 합니다.
마지막 메시지가 성공적으로 전달 경우를 고려해보자. 만약 그 마지막 메시지가 성공적으로 전달되지 않았다면 적어도 한 장군은(아마도 수신측)이 공격을 하지 않을 것으로 결정할 것이다. 마지막 메시지의 발신자 관점에서, 그러나, 보내지고 전달된 메시지의 순서는 그 메시지가 전달되었거나 되었던 것과 똑같은 것입니다. 프로토콜이 결정적이기 때문에, 마지막 메시지를 보내려는 장군은 여전히 공격하기로 결정합니다.  우리는 제안된 프로토콜이 한 장군을 공격하고 다른 공격자는 공격하지 않도록 상황을 만들었습니다. 프로토콜이 문제의 해결책이라는 가정과 모순됩니다.

비결정적이고 가변길이의 프로토콜의 경우

가변 메시지 수를 갖는 비 결정적 프로토콜은 유한 트리와 비교 될 수 있는데, 트리의 각 리프 또는 브랜치 (노드)는 지정된 포인트까지 탐색 된 예제를 나타냅니다.
이 트리의 루트에는 가능한 시작 메시지가 표시되며이 루트에서 나오는 분기 노드에는 가능한 다음 메시지가 표시됩니다. 리프 노드는 마지막 메시지를 보낸 후 끝나는 예제를 나타냅니다. 메시지를 보내기 전에 종료되는 프로토콜은 null 트리로 표시됩니다.
문제를 해결하는 비 결정적 프로토콜이 있다고 가정합니다. 그런 다음 모든 절점을 제거하여 다른 절점에서 얻을 수있는 이전 절의 결정적인 예와 비슷한 인수에 의해 결정적 프로토콜이 문제를 해결해야합니다.
비 결정적 프로토콜은 유한하므로, 빈 트리가 나타내는 프로토콜이 문제를 해결할 것입니다. 분명히 이것은 불가능합니다. 따라서 문제를 해결하는 비 결정적 프로토콜은 존재할 수 없습니다.
A nondeterministic protocol with a variable message count can be compared to a finite tree, where each leaf or branch (node) in the tree represents an explored example up to a specified point.
The roots of this tree are labeled with the possible starting messages, and the branch nodes stemming from these roots are labeled with the possible next messages. Leaf nodes represent examples which end after sending the last message. A protocol that terminates before sending any messages is represented by a null tree.
Suppose there exists a nondeterministic protocol which solves the problem. Then, by a similar argument to the deterministic example in the previous section, where the one can be obtained from the other by removing all leaf nodes, the deterministic protocol must then also solve the problem.
Since the nondeterministic protocol is finite, it then follows that the protocol represented by the empty tree would solve the problem. Clearly this is not possible. Therefore a nondeterministic protocol which solves the problem cannot exist.

공학적 접근법

Two Generals의 문제를 다루기위한 실용적인 접근법은 통신 채널의 불확실성을 수용하고이를 제거하려고 시도하지 않고 수용 할 수있는 수준으로 완화시키는 방식을 사용하는 것입니다. 예를 들어, 첫 번째 장군은 100 명의 메신저를 보낼 수 있으며 모든 포착 확률이 낮을 것으로 예상합니다. 이 방법을 사용하면 첫 번째 장군은 무엇이든지간에 공격 할 것이며, 두 번째 장군은 메시지가 수신되면 공격 할 것입니다. 또는 첫 번째 장군이 메시지 스트림을 보낼 수 있고 두 번째 장군이 각자에게 수신 확인을 보낼 수 있습니다. 각각의 일반적인 느낌은받은 모든 메시지에보다 편안합니다. 그러나 증거에서 알 수 있듯이 공격이 조율 될지 확신 할 수 없습니다. 다른 알고리즘없이 공격하지 못하도록 막을 수있는 알고리즘은 없습니다 (예 : 4 개 이상의 메시지가 수신되는 경우 공격). 또한, 첫 번째 장군은 각 메시지에 1, 2, 3 ... n의 메시지임을 나타내는 마킹을 보낼 수 있습니다. 이 방법을 사용하면 두 번째 장군이 채널의 안정성을 알 수 있고 적절한 수의 메시지를 다시 보내 적어도 하나의 메시지 수신 가능성을 높일 수 있습니다. 채널을 신뢰할 수있게 만들 수 있으면 하나의 메시지만으로도 충분하며 추가 메시지가 도움이되지 않습니다. 마지막은 잃어 버릴 확률이 가장 높습니다.
장군이 메신저가 보내지고 가로 챌 때마다 장군이 생명을 희생해야한다고 가정하면, 공격이 조정되는 최대 신뢰도를 달성하는 데 필요한 메신저의 수를 최소화하도록 알고리즘을 설계 할 수 있습니다. 장군은 수천명의 목숨을 희생하지 못하도록함으로써 조정에 대한 매우 높은 자신감을 얻었으며 장군은 메신저가 부재 한 것을 거래에 착수 한 장군이 적어도 한 번 이상의 확인을 받았으며 공격하겠다고 약속했음을 동의 할 수있었습니다. 메신저가 위험 지대를 가로 지르는 데 1 분이 걸리면 확인을받은 후 200 분의 침묵이 생겨 메신저의 생명을 희생하지 않으면서도 매우 높은 자신감을 얻을 수 있습니다. 이 경우 메신저는 파티원이 공격 시간을받지 않은 경우에만 사용됩니다. 200 분이 지나면 각 장군은 다음과 같이 추론 할 수 있습니다. "나는 200 분 동안 200 메신저가 위험 지대를 넘지 않았거나 다른 일반 장군이 공격을 확인하고 저지른 것을 의미하며 추가로 200 분 동안 메시지를받지 못했습니다. 나는 그렇게 할 것이다 ".
A pragmatic approach to dealing with the Two Generals' Problem is to use schemes that accept the uncertainty of the communications channel and not attempt to eliminate it, but rather mitigate it to an acceptable degree. For example, the first general could send 100 messengers, anticipating that the probability of all being captured is low. With this approach the first general will attack no matter what, and the second general will attack if any message is received. Alternatively the first general could send a stream of messages and the second general could send acknowledgments to each, with each general feeling more comfortable with every message received. As seen in the proof, however, neither can be certain that the attack will be coordinated. There's no algorithm that they can use (e.g. attack if more than four messages are received) which will be certain to prevent one from attacking without the other. Also, the first general can send a marking on each message saying it is message 1, 2, 3 ... of n. This method will allow the second general to know how reliable the channel is and send an appropriate number of messages back to ensure a high probability of at least one message being received. If the channel can be made to be reliable, then one message will suffice and additional messages do not help. The last is as likely to get lost as the first.
Assuming that the generals must sacrifice lives every time a messenger is sent and intercepted, an algorithm can be designed to minimize the number of messengers required to achieve the maximum amount of confidence the attack is coordinated. To save them from sacrificing hundreds of lives to achieve a very high confidence in coordination, the generals could agree to use the absence of messengers as an indication that the general who began the transaction has received at least one confirmation, and has promised to attack. Suppose it takes a messenger 1 minute to cross the danger zone, allowing 200 minutes of silence to occur after confirmations have been received will allow us to achieve extremely high confidence while not sacrificing messenger lives. In this case messengers are used only in the case where a party has not received the attack time. At the end of 200 minutes, each general can reason: "I have not received an additional message for 200 minutes; either 200 messengers failed to cross the danger zone, or it means the other general has confirmed and committed to the attack and has confidence I will too".