두 장군 문제, 비잔틴 장군 문제

Jmnote bot (토론 | 기여)님의 2017년 7월 10일 (월) 15:05 판 (봇: 자동으로 텍스트 교체 (-==참고 자료== +==참고==))
Two Generals' Problem, Two Generals Paradox, Two Armies Problem, Coordinated Attack Problem
두 장군 문제, 두 장군 역설, 두 부대 문제, 협공 문제
Byzantine Generals Problem
비잔틴 장군 문제, 비잔틴 장군의 딜레마

1 두 장군 문제

  • 컴퓨터 과학 분야의 사고 실험
  • 불확실한 연결 기반의 통신상황에서 동작을 동기화할 때의 함정, 설계 과제를 명시하기 위한 것
  • 문제의 본질: 두 장군이 안전하게 합의할 수 있는 알고리즘을 설계하는 것이 불가능함

1.1 상황

 

  • 두 장군이 각각 이끄는 두 부대 A1, A2가, 요새도시 B를 공격할 준비를 하고 있음
  • 두 부대는 도시 근처의 두 언덕 뒤에 각각 진을 침
  • 두 언덕은 계곡으로 나뉘어 있어, 소통하는 유일한 방법은 계곡을 통과하는 연락병을 보내는 것뿐임
  • 불행히도 계곡에는 적군이 있어 연락병이 포획될 가능성이 있음
  • 두 장군은 사전에 공격하기로는 합의했으나 그 시각은 합의되지 않았음
  • 승리하려면 두 부대가 동시에 도시를 공격해야만 함
( 한쪽이 먼저 단독으로 공격하면 패배함 )
  • 그래서 소통을 통해 공격시간을 합의하고 상대의 확답을 받아야 함
  • 확답조차도 제대로 전달될지 확실하지 않으므로 완벽히 확신하려면 무한히 많은 메시지가 필요함

2 비잔틴 장군 문제

  • 두 장군 문제를 일반화한 문제

2.1 상황

  • 비잔틴 제국의 여러 장군들이 하나의 적군 도시를 공격하기 위해 출병함
  • 적은 매우 강해서 과반수 이상의 장군들이 같은 시각에 공격해야만 승리하고, 그렇지 않으면 패배
  • 모든 장군들간의 소통은 연락병 보내는 방법 밖에 없음
  • 장군들 중에는 배신자가 있을 수 있어서 서로 신뢰할 수 없음
( 배신자는 가짜 공격 명령을 보낼 수도 있음 )
  • 서로 신뢰할 수 없는데 공격시각을 어떻게 합의할까?

3 같이 보기

4 참고

문서 댓글 ({{ doc_comments.length }})
{{ comment.name }} {{ comment.created | snstime }}