두 장군의 문제

Two Generals' Problem
군대의 위치.A1군과 A2군은 통신을 해야 하지만 그들의 메신저는 B군에 의해 붙잡힐 수 있다.

컴퓨팅에서 두 장군의 문제는 신뢰할 수 없는 링크를 통해 통신함으로써 행동을 조정하려고 할 때의 함정과 설계상의 문제를 설명하기 위한 사고 실험입니다.실험에서, 두 명의 장군은 적지를 통해 전령을 보내야만 서로 의사소통을 할 수 있다.실험은 그들이 보내는 어떤 메신저도 잡힐 수 있다는 것을 알면서도 공격을 개시하는 시간에 어떻게 합의에 도달할 수 있는지를 묻는다.

이것은 보다 일반적인 비잔틴 일반 문제와 관련이 있으며 컴퓨터 네트워킹에 관한 입문 수업(특히 TCP가 엔드포인트 간의 상태 일관성을 보장할 수 없다는 것과 이것이 왜 그런지 보여주는)에 자주 나타난다.통신장애가 발생할 수 있는 부분에 대해 설명합니다.인식론적 논리학의 핵심 개념인 이 문제는 상식의 중요성을 강조한다.일부 저자들은 또한 이것을 두 장군의 역설, 양군 문제, 또는 협공 [1][2]문제라고도 부른다.두 장군의 문제는 해결할 수 없는 것으로 증명된 최초의 컴퓨터 통신 문제였다.이 증거의 중요한 결과는 비잔틴 장군 문제와 같은 일반화는 임의 통신 장애에 직면하여 해결할 수 없으며, 따라서 분산된 일관성 프로토콜에 대한 현실적인 기대의 기반을 제공한다는 것입니다.

정의.

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

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

사고실험은 그들이 합의에 도달하는 방법을 고려하는 것을 포함한다.가장 간단한 형태로는 한 장군이 리더로 알려져 있고, 공격 시간을 결정하고, 이 시간을 다른 장군에게 알려야 합니다.문제는 장군들이 올바른 결론을 내릴 수 있도록 메시지를 보내고 수신된 메시지를 처리하는 등 사용할 수 있는 알고리즘을 고안하는 것입니다.

그래, 우리 둘 다 약속한 시간에 공격할 거야.

두 장군이 공격 시기에 대해 합의하는 것은 매우 간단하다(즉, 성공적으로 인정된 하나의 성공적인 메시지). 두 장군의 문제의 미묘함은 위의 성명에 안전하게 동의하기 위한 알고리즘을 사용하는 것이 불가능하다는 데 있다.

문제의 예증명

첫 번째 장성은 8월 4일 0900시에 공격하라는 메시지를 보내는 것으로 시작할 수 있지만, 일단 파견된 후, 첫 번째 장성은 메신저가 통과했는지 여부를 알 수 없다.이러한 불확실성으로 인해 최초 장군은 단독 공격자의 위험 때문에 공격을 주저할 수 있습니다.

2등 장성은 1등 장성에 메시지를 받고 8월 4일 0900시에 공격하겠다고 답할 수도 있지만, 2등 장성은 1등 장성이 확인 없이 주저할 수도 있어 생포에 직면할 수도 있다.

추가 확인은 해결책처럼 보일 수 있습니다.첫 번째 장군은 "8월 4일 0900에 계획된 공격에 대한 당신의 확인을 받았습니다."라는 두 번째 확인을 보내도록 하겠습니다.그러나 첫 번째 장군으로부터의 새로운 메신저도 생포될 가능성이 있습니다.따라서 아무리 여러 차례 확인하더라도 각 장군이 상대방이 공격 계획에 동의했다고 확신할 수 있는 두 번째 요건을 보장할 수 있는 방법은 없다는 것이 금세 명백해진다.두 장군 모두 그들의 마지막 사신이 통과했는지에 대해 항상 의문을 가질 것이다.

증명

메시지 수가 고정된 결정론적 프로토콜의 경우

이 프로토콜은 결정론적이기 때문에, 하나 이상의 메시지가 성공적으로 배달되고 하나 이상의 메시지가 없는 고정된 수의 시퀀스가 있다고 가정합니다.그 가정은 두 장군이 공격할 수 있는 공통의 확실성이 있어야 한다는 것이다.

마지막으로 정상적으로 전달된 메시지를 생각해 보십시오.마지막 메시지가 정상적으로 전달되지 않은 경우 적어도1개의 일반(아마도 수신측)이 공격을 하지 않기로 결정합니다.단, 마지막 메시지 발신인의 관점에서 전송 및 전달된 메시지의 순서는 해당 메시지가 전달되었을 때와 완전히 동일합니다.

프로토콜은 결정론적이기 때문에 마지막 메시지를 보내는 장군은 여전히 공격을 결정합니다.이제 제안된 프로토콜이 한 장군은 공격하고 다른 한 명은 공격하지 않는 상황을 만들어 냈습니다. 이는 프로토콜이 문제의 해결책이라는 가정과 배치됩니다.

비확정 및 가변 길이 프로토콜용

잠재적으로 가변적인 메시지 수를 갖는 비결정론적 프로토콜은 엣지 라벨이 부착된 유한 트리와 비교될 수 있으며, 여기서 트리의 각 노드는 지정된 포인트까지의 탐색된 예를 나타낸다.메시지를 보내기 전에 종료되는 프로토콜은 루트 노드만 포함하는 트리로 표시됩니다.노드에서 각 자식까지의 가장자리에는 자식 상태에 도달하기 위해 전송된 메시지로 레이블이 지정됩니다.리프 노드는 프로토콜이 종료되는 지점을 나타냅니다.

두 장군의 문제를 해결하는 비결정론적 프로토콜 P가 있다고 가정합니다.그런 다음, 위의 고정 길이 결정론적 프로토콜에 사용되는 것과 유사한 인수에 의해, P'는 또한 P'를 나타내는 트리가 모든 리프 노드와 그것들로 이어지는 에지를 제거함으로써 P'에 대한 그것으로부터 얻어지는 Two Generals' 문제를 해결해야 한다.

P는 유한하기 때문에 메시지를 보내기 전에 종료되는 프로토콜이 문제를 해결합니다.하지만 확실히 그렇지 않다.따라서 문제를 해결하는 비결정적 프로토콜은 존재할 수 없습니다.

엔지니어링 어프로치

두 장군의 문제를 다루기 위한 실용적인 접근법은 통신 채널의 불확실성을 받아들이고 이를 제거하려는 것이 아니라 허용 가능한 수준으로 완화하는 방법을 사용하는 것이다.예를 들어, 첫 번째 장군은 100명의 메신저를 보낼 수 있으며, 모든 것이 잡힐 확률은 낮다고 예상한다.이 접근방식에서는 첫 번째 장군은 무슨 일이 있어도 공격을 하고 두 번째 장군은 메시지를 수신하면 공격을 합니다.또는 첫 번째 일반은 메시지 스트림을 보내고 두 번째 일반은 수신된 모든 메시지에 대해 보다 편안하게 느끼는 확인 응답을 각각 보낼 수 있습니다.그러나 증거에서 알 수 있듯이 공격이 조정될지 확신할 수 없습니다.한쪽이 다른 쪽 없이 공격하는 것을 확실하게 막을 수 있는 알고리즘은 없습니다(예를 들어 4개 이상의 메시지가 수신된 경우 공격).또, 제1의 일반은, 각 메세지에 대해서, 그것이 n의 메시지 1, 2, 3…이라고 하는 마킹을 송신할 수 있다.이 방법을 사용하면 두 번째 일반은 채널의 신뢰성을 파악하고 적절한 수의 메시지를 반송하여 적어도1개의 메시지가 수신될 가능성이 높아집니다.채널을 신뢰할 수 있는 상태로 만들 수 있는 경우 1개의 메시지로 충분하며 추가 메시지는 도움이 되지 않습니다.마지막도 첫 번째와 마찬가지로 길을 잃기 쉽다.

장성이 메신저를 보내고 요격할 때마다 목숨을 희생해야 한다고 가정할 때, 공격이 조정되는 최대한의 신뢰를 얻기 위해 필요한 메신저 수를 최소화하는 알고리즘을 설계할 수 있다.조정에 있어 매우 높은 신뢰를 얻기 위해 수백 명의 목숨을 희생하는 것으로부터 그들을 구하기 위해, 장군들은 거래를 시작한 장군이 최소한 한 번의 확인을 받았고 공격을 약속했다는 표시로 전령부재를 사용하는 것에 동의할 수 있다.만약 메신저가 위험 구역을 통과하는 데 1분이 걸린다고 가정하면, 확인을 받은 후 200분의 침묵을 유지하면 메신저의 생명을 희생하지 않으면서 매우 높은 신뢰를 얻을 수 있습니다.이 경우 메신저는 파티가 공격 시간을 수신하지 않은 경우에만 사용됩니다.200분 후에 각 장군은 "나는 200분 동안 추가 메시지를 받지 못했다; 200명의 메신저가 위험 구역을 넘지 못했거나, 다른 장군이 공격을 확인하고 약속했으며, 나도 그럴 것이라고 확신한다"고 추론할 수 있다.

역사

두 장군의 문제와 불가능한 증거는 E.A.에 의해 처음 출판되었다.아코윤루, KEkanadham과 R. V. Huber는 1975년 "네트워크 [3]통신 설계에서의 몇 가지 제약과 트레이드오프"에서 두 갱스터 그룹 간의 의사소통의 맥락으로 73페이지부터 설명되어 있습니다.

이 문제는 1978년 465페이지의[4] "데이터베이스 [5]운영체제 노트"에서 Jim Gray에 의해 두 개의 일반 패러독스로 명명되었습니다.이 참조는 문제의 정의와 불가능성의 증거에 대한 소스로 널리 제공되지만, 두 가지 모두 위에서 언급한 바와 같이 이전에 출판되었다.

레퍼런스

  1. ^ Gmytrasiewicz, Piotr J.; Edmund H. Durfee (1992). "Decision-theoretic recursive modeling and the coordinated attack problem". Proceedings of the First International Conference on Artificial Intelligence Planning Systems. San Francisco: Morgan Kaufmann Publishers: 88–95. doi:10.1016/B978-0-08-049944-4.50016-1. ISBN 9780080499444. Retrieved 27 December 2013.
  2. ^ 조직적인 공격과 질투심이 알레산드로 판코네시를 놀라게 했다.2011년 5월 17일 취득.
  3. ^ Akkoyunlu, E. A.; Ekanadham, K.; Huber, R. V. (1975). Some constraints and trade-offs in the design of network communications (PDF). Portal.acm.org. pp. 67–74. doi:10.1145/800213.806523. S2CID 788091. Retrieved 2010-03-19.
  4. ^ "Jim Gray Summary Home Page". Research.microsoft.com. 2004-05-03. Retrieved 2010-03-19.
  5. ^ Notes on Data Base Operating Systems. Portal.acm.org. January 1978. pp. 393–481. ISBN 9783540087557. Retrieved 2010-03-19.