두 장군 문제

두 장군 문제(영어: Two Generals' Problem)는 컴퓨팅 영역에서 신뢰할 수 없는 링크를 통해 의사 소통할 때, 행동을 조작하려는 시도의 위험과 설계 과제를 설명하기 위한 사고 실험이다. 이 실험에서 두 장군은 전략 구성을 위해 적진을 통과하여 서로 상대방에게 전령을 보내게 된다. 이 실험은 그들이 보낸 전령이 잡힐 수도 있다는 것을 알면서도 공격을 시작할 시간에 대해 어떻게 합의에 도달할 수 있는지 묻는다.

이것은 일반적인 예시인 비잔티움 장군 문제와 관련이 있으며 컴퓨터 네트워크 과목 입문에서 종종 등장한다(특히 전송 제어 프로토콜(Transmission Control Protocol) 와 관련하여, TCP가 네트워크 종단 간의 상태의 일관성을 보장할 수 없는 지와 그 이유를 보여준다.). 이는 통신 장애가 발생할 수 있는 모든 종류의 양방향 통신에 적용된다.

인식론적 논리의 핵심 개념에서 이 문제는 상식의 중요성을 강조한다. 일부 저자는 이것을 2 장군 패러독스( Two Generals Paradox), 2 군대 문제(Two Armies Problem) 또는 협조 된 공격 문제(Coordinated Attack Problem)라고 한다.

두 장군 문제는 해결할 수 없는 것으로 판명된 최초의 컴퓨터 통신 문제였다. 이 증명의 중요한 결과는 비잔틴 장군 문제와 같은 일반화 또한 임의의 통신 실패로 인해 해결 될 수 없다는 것이다. 이와 같이, 모든 분산 일관성 프로토콜(distributed consistency protocols)에 대한 실질적인 기대의 기반을 제공한다.

정의

다른 장군이 이끌고 있는 두 군대는 요새화 된 도시를 공격 할 준비를 하고 있다. 군대는 도시 근처, 각각 계곡에 자리 잡고 있다. 세 번째 계곡은 두 언덕을 갈라 놓고, 두 장군이 통신 할 수 있는 유일한 방법은 전령을 계곡을 통해 보내는 것이다. 불행히도, 계곡은 도시의 수비대에 의해 점령되어 있으며, 계곡을 통해 보내진 어떤 전령은 붙잡힐 가능성이 있다.

두 장군은 공격에는 동의했지만 공격 시간을 합의하지 않았다. 두 명의 장군은 그들의 공격이 성공하기 위해서는 도시를 동시에 공격해야 한다. 그렇지 않으면, 단독으로 공격을 시도한 군대가 죽을 것이다. 따라서, 그들은 공격 할 시간을 결정하고 그 시간에 공격에 동의하기 위해 서로 의사 소통해야 하며, 각 장군은 상대방이 공격 계획에 동의했음을 알고 있어야 한다. 메시지 수신 확인은 원래 메시지만큼 쉽게 손실 될 수 있으므로 잠재적으로 무한한 일련의 메시지가 합의에 도달해야 한다.

사고 실험은 그들이 어떻게 합의에 도달할 지를 고려하는 것이다. 가장 간단한 형태로, 지도자인 것으로 알려진 한 장군이, 공격 시기를 결정하고, 이 시간을 다른 장군에게 알려야 한다. 문제는 메시지를 보내고, 받은 메시지를 처리하는 등 장군이 사용할 수 있는 알고리즘을 도출해 내고 올바르게 결론을 내릴 수 있어야 한다.

예를 들면 "두 장군은 합의된 시간에 함께 공격할 것이다."

장군이 공격 할 시간에 동의하게 하는 것이 매우 간단하다는 것을 허용하면(즉, 성공적인 승인을 가진 하나의 성공적인 메시지), 두 장군 문제의 미묘함은 장군들 위의 진술에 안전하게 동의하기 위해 사용하는 알고리즘을 설계하는 것은 불가능하다는 것이다.

문제의 설명

첫 번째 장군은 "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".