##확실성을 수용하고이를 제거하려고 시도하지 않고 수용 할 수있는 수준으로 완화시키는 방식을 사용하는 것입니다. 예를 들어, 첫 번째 장군은 100 명의 메신저를 보낼 수 있으며 모든 포착 확률이 낮을 것으로 예상합니다. 이 방법을 사용하면 첫 번째 장군은 무엇이든지간에 공격 할 것이며, 두 번째 장군은 메시지가 수신되면 공격 할 것입니다. 또는 첫 번째 장군이 메시지 스트림을 보낼 수 있고 두 번째 장군이 각자에게 수신 확인을 보낼 수 있습니다. 각각의 일반적인 느낌은받은 모든 메시지에보다 편안합니다. 그러나 증거에서 알 수 있듯이 공격이 조율 될지 확신 할 수 없습니다. 다른 알고리즘없이 공격하지 못하도록 막을 수있는 알고리즘은 없습니다 ( 예 : 4 개 이상의 메시지가 수신되는 경우 공격 ). 또한, 첫 번째 장군은 각 메시지에 1, 2, 3... n의 메시지임을 나타내는 마킹을 보낼 수 있습니다. 이 방법을 사용하면 두 번째 장군이 채널의 안정성을 알 수 있고 적절한 수의 메시지를 다시 보내 적어도 하나의 메시지 수신 가능성을 높일 수 있습니다. 채널을 신뢰할 수있게 만들 수 있으면 하나의 메시지만으로도 충분하며 추가 메시지가 도움이
않았다면 적어도 한 장군은 ( 아마도 수신측 ) 이 공격을 하지 않을 것으로 결정할 것이다. 마지막 메시지의 발신자 관점에서, 그러나, 보내지고 전달된 메시지의 순서는 그 메시지가 전달되었거나 되었던 것과 똑같은 것입니다. 프로토콜이 결정적이기 때문에, 마지막 메시지를 보내려는 장군은 여전히 공격하기로 결정합니다. 우리는 제안된 프로토콜이 한 장군을 공격하고 다른 공격자는 공격하지 않도록 상황을 만들었습니다. 프로토콜이 문제의 해결책이라는 가정과 모순됩니다. 비결정적이고 가변길이의 프로토콜의 경우 [ 편집 ] 가변 메시지 수를 갖는 비 결정적 프로토콜은 유한 트리와 비교 될 수 있는데, 트리의 각 리프 또는 브랜치 ( 노드 ) 는 지정된 포인트까지 탐색 된 예제를 나타냅니다. 이 트리의 루트에는 가능한 시작 메시지가 표시되며이 루트에서 나오는 분기 노드에는 가능한 다음 메시지가 표시됩니다. 리프 노드는 마지막 메시지를 보낸 후 끝나는 예제를 나타냅니다. 메시지를 보내기 전에 종료되는 프로토콜은 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 tr
두 장군 문제 - 위키백과, 우리 모두의 백과사전 두 장군 문제 위키백과, 우리 모두의 백과사전. ( 두장군문제에서 넘어옴 ) 둘러보기로 가기 검색하러 가기 이 문서의 내용은 출처가 분명하지 않습니다. 이 문서를 편집하여, 신뢰할 수 있는 출처를 표기해 주세요. 검증되지 않은 내용은 삭제될 수도 있습니다. 내용에 대한 의견은 토론 문서에서 나누어 주세요. ( 2018년 7월 ) 이 문서는 다른 언어판 위키백과의 문서 ( en : Two Generals'Problem ) 를 번역 중이며, 한국어로 좀 더 다듬어져야 합니다. 번역에 이상이 있다면 직접 편집하시거나, 해당 글의 토론 문서에 의견을 남겨주세요. ( 2018년 7월 ) 컴퓨팅 영역에서 두 장군 문제는 신뢰할 수 없는 링크를 통해 의사 소통함으로써 행동을 조정하려는 설계 과제와 함정을 설명하기 위한 사고 실험이다. 이것은 좀 더 일반적인 비잔틴 장군 문제 ( Byzantine Generals Problem ) 와 관련이 있으며 컴퓨터 네트워킹 ( 특히, TCP가 종단간 상태 일관성을 보장할 수 없는지와 이유에 대한 전송 제어 프로토콜 ( Transmission Control Protocol ) ( Transmission Control Protocol ) 과 관련
##으로 알려진 한 장군이, 공격 시기를 결정하고, 이 시간을 다른 장군에게 알려야 합니다. 이 문제는 메시지를 보내고, 받은 메시지를 처리하는 등 장군이 사용할 수 있는 알고리즘을 도출해 내고 올바르게 결론을 내릴 수 있어야 합니다. 예, 두 장군은 합의된 시간에 함께 공격할 것입니다. 장군이 공격 할 시간에 동의하게하는 것이 매우 간단하다는 것을 허용하면 ( 즉, 성공적인 승인을 가진 하나의 성공적인 메시지 ), 두 장군 문제의 미묘함은 장군들 위의 진술에 안전하게 동의하기 위해 사용하는 알고리즘을 설계하는 것은 불가능하다는 것입니다. 문제의 설명 [ 편집 ] 첫 번째 장군은 " 8 월 4 일 9시에 공격 " 이라는 메시지를 보내 시작할 수 있습니다. 그러나 일단 파견되면, 첫 번째 장군은 메신저가 통과했는지 여부를 알 수 없습니다. 이러한 불확실은 첫 번째 장군이 단독으로 공격하게 될 위험 때문에 공격을 주저하게 합니다. 확실히, 두 번째 장군은 " 나는 당신의 메시지를 받았고 8 월 4 일 9시에 공격 할 것입니다. " 라고 확인 메시지를 보낼 수 있습니다. 그러나 메신저는 잡힐 수 있어서 두 번째 장군은 첫 번째 장군이 확인 메세지가 없어서 물러날 수 있
수 있습니다. 채널을 신뢰할 수있게 만들 수 있으면 하나의 메시지만으로도 충분하며 추가 메시지가 도움이되지 않습니다. 마지막은 잃어 버릴 확률이 가장 높습니다. 장군이 메신저가 보내지고 가로 챌 때마다 장군이 생명을 희생해야한다고 가정하면, 공격이 조정되는 최대 신뢰도를 달성하는 데 필요한 메신저의 수를 최소화하도록 알고리즘을 설계 할 수 있습니다. 장군은 수천명의 목숨을 희생하지 못하도록함으로써 조정에 대한 매우 높은 자신감을 얻었으며 장군은 메신저가 부재 한 것을 거래에 착수 한 장군이 적어도 한 번 이상의 확인을 받았으며 공격하겠다고 약속했음을 동의 할 수있었습니다. 메신저가 위험 지대를 가로 지르는 데 1 분이 걸리면 확인을받은 후 200 분의 침묵이 생겨 메신저의 생명을 희생하지 않으면서도 매우 높은 자신감을 얻을 수 있습니다. 이 경우 메신저는 파티원이 공격 시간을받지 않은 경우에만 사용됩니다. 200 분이 지나면 각 장군은 다음과 같이 추론 할 수 있습니다. " 나는 200 분 동안 200 메신저가 위험 지대를 넘지 않았거나 다른 일반 장군이 공격을 확인하고 저지른 것을 의미하며 추가로 200 분 동안 메시지를받지 못했습니다. 나
##hieve 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 ". 원본 주소 " " 분류 : 계산 이론사고 실험숨은 분류 : 출처가 필요한 글 / 2018년 7월출처가 필요한 모든 글전체에 출처가 필요한 글번역 중인 문서 둘러보기 메뉴 개인 도구 로그인하지 않음토론기여계정 만들기로그인 이름공간 문서토론 변수 보기 읽기편집역사 보기 더 보기 검색 둘러보기 대문사용자 모임요즘 화제최근 문서 보기임의 문서로도움말기부 도구 여기를 가리키는 문서가리키는 글의 최근 올리기특수 문서 목록고유 링크문
##ocol 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의 문제를 다루기위한 실용적인 접근법은 통신 채널의 불확실성을 수용하고이를 제거하려고 시도하지 않고 수용 할 수있는 수준으로 완화시키는 방식을 사용
##습니다. 그러나 메신저는 잡힐 수 있어서 두 번째 장군은 첫 번째 장군이 확인 메세지가 없어서 물러날 수 있음을 알기 때문에 망설이게 됩니다. 더 많은 확인 메세지가 해결책처럼 보일 수 있습니다. 첫 번째 장군이 " 8월 4일 9시에 계획된 공격에 대한 당신의 확인을 받았습니다. " 라는 두번째 확인 메세지를 보냅니다. 그러나 첫 번째 장군이 보낸 새로운 전령 역시 잡힐 수 있습니다. 따라서 확인 횟수가 아무리 많아도 증거가 될 수 업습니다. 한 장군이 다른 장군이 공격 계획에 동의했는지에 대한 두 번째 요구 사항을 보장 할 방법이 없습니다. 두 장군은 항상 마지막 메신저가 통과했는지에 대해 의문을 가지게 됩니다. 증명 [ 편집 ] 정해진 수의 메세지를 갖는 결정적 프로토콜의 경우 [ 편집 ] 이 프로토콜은 결정적이기 때문에 하나 이상의 메세지가 성공적으로 배달이 되거나 그렇지 않은, 고정 된 수의 메시지 순서가 있다고 가정합니다. 이 가정은 이 공격 할 수 것이라는 공통된 확신이 있어야 합니다. 마지막 메시지가 성공적으로 전달 경우를 고려해보자. 만약 그 마지막 메시지가 성공적으로 전달되지 않았다면 적어도 한 장군은 ( 아마도 수신측 ) 이 공격을 하지 않을 것으로 결정할 것이다. 마지막 메시지의 발신
##의 문서로도움말기부 도구 여기를 가리키는 문서가리키는 글의 최근 올리기특수 문서 목록고유 링크문서 정보위키데이터 항목이 문서 인용하기 인쇄 / 내보내기 책 만들기PDF로 다운로드인쇄용 판 다른 언어 日 本 語 링크 편집 이 문서는 2018년 7월 17일 ( 화 ) 16 : 52에 마지막으로 편집되었습니다. 모든 문서는 크리에이티브 커먼즈 저작자표시 - 동일조건변경허락 3. 0에 따라 사용할 수 있으며, 추가적인 조건이 적용될 수 있습니다. 자세한 내용은 이용 약관을 참고하십시오. 미국 및 다른 국가에 등록되어 있는 Wikimedia Foundation, Inc. 소유의 등록 상표입니다. 개인정보 정책 위키백과 소개 면책 조항 개발자 쿠키 정책 모바일 보기
두 장군 문제(영어: Two Generals' Problem)는 컴퓨팅 영역에서 신뢰할 수 없는 링크를 통해 의사 소통할 때, 행동을 조작하려는 시도의 위험과 설계 과제를 설명하기 위한 사고 실험이다. 이 실험에서 두 장군은 전략 구성을 위해 적진을 통과하여 서로 상대방에게 전령을 보내게 된다. 이 실험은 그들이 보낸 전령이 잡힐 수도 있다는 것을 알면서도 공격을 시작할 시간에 대해 어떻게 합의에 도달할 수 있는지 묻는다. 이것은 일반적인 예시인 비잔티움 장군 문제와 관련이 있으며 컴퓨터 네트워크 과목 입문에서 종종 등장한다(특히 전송 제어 프로토콜(Transmission Control Protocol)(Transmission Control Protocol) 와 관련하여, TCP가 네트워크 종단 간의 상태의 일관성을 보장할 수 없는 지와 그 이유를 보여준다.). 이는 통신 장애가 발생할 수 있는 모든 종류의 양방향 통신에 적용된다. 인식론적 논리의 핵심 개념에서 이 문제는 상식의 중요성을 강조한다. 일부 저자는 이것을 2 장군 패러독스(Two Generals Paradox), 2 군대 문제(Two Armies Problem) 또는 협조 된 공격 문제(Coordinated Attack Problem)라고 한다. 두 장군 문제는 해결할 수 없는 것으로 판명된 최초의 컴퓨터 통신 문제였다. 이 증명의 중요한 결과는 비잔틴 장군 문제와 같은 일반화 또한 임의의 통신 실패로 인해 해결 될 수 없다는 것이다. 이와 같이, 모든 분산 일관성 프로토콜(distributed consistency protocols)에 대한 실질적인 기대의 기반을 제공한다.