비잔틴 장애 허용

비잔틴 장애 허용(BFT: Byzantine Fault Tolerance)은 레슬리 램포트와 쇼스틱, 피스가 공저한 1982년 논문에서 언급된 것으로 비잔틴 제국의 여러 부대가 멀리 떨어진 상태에서 성공적으로 공격 계획을 세우는 상황을 가정하고 있다. 부대 내에는 배신자가 있을 수도 있고, 이 배신자 또는 배신자들은 충직한 지휘관들과 달리 규칙에 얽매이지 않고 행동이 자유롭다. 이때 충직한 지휘관들이 성공적인 공격을 위해 필요한 충직한 지휘관들의 수와 이들이 어떤 규칙을 따라야 하는지에 대한 문제를 풀어내는 것이 비잔틴 장애 또는 비잔티 장군 문제이다.

특징

비잔티움 장애

첫번째 솔루션은 전달된 메시지가 위조될 수 있다는 시나리오로 시작한다. 하지만 이 때 배반한 장군의 수가 전체 장군 수의 3분의 1과 같거나 넘지 않는 경우, 비잔티움 장애에 해당하는 것으로 한다. 3분의 1 또는 그 이상의 배반자가 있으면, 하나의 지휘관과 두 중위 문제(one Commander and two Lieutenants problem)로 간주할 수 있으며, 이처럼 지휘관이 배반자인 경우는 해결할 수 없다. 한 명의 배반자 지휘관 A와 두 중위 B, C가 있다고 가정하자. A가 B에게 공격하라고, C에게는 후퇴하라고 명령하는 경우 A의 메시지를 전달받은 B, C는 누가 배반자인지 알 수 없다. A가 아니라 중위 B와 C가 배반했을 수도 있기 때문이다. 따라서 n명의 지휘관이 있고 그중 t명이 배반자인 경우 오직 {\displaystyle n>3t} {\displaystyle n>3t}이고 커뮤니케이션이 동시에 이루어져야만(synchronous; bounded delay) 솔루션이 있다.

비잔티움 장애 허용

두 번째 솔루션은 메시지의 서명이 위조될 수 없다를 가정한다. 보안이 중요한 시스템(security-critical system)에서 디지털 서명은(공개 키 암호화로 형태로 구현) 임의의 배반자 지휘관이 있는 상황에서 비잔틴 장애 허용을 제공한다. 하지만 안전이 중요한 시스템(safety-critical system)에서 CRCs 등은 대부분의 상황에서 적용될 수 있는 간단한 에러를 찾는 코드를 낮은 비용에 제공하며, 이는 비잔틴 장애와 비잔틴 장애가 아닌 것 모두에 가능하다. 따라서 암호화된 디지털 서명 방식은 별도의 보안 위협이 있지 않은 한, 시스템에서 안전이 중요한 역할은 아니다. 또한 Lamport, Shostak, Pease는 앞서 서술한 두 솔루션 외에도 모든 지휘관이 서로 소통할 수 없는 경우 등 다양한 경우에 관해서도 서술했다.

Byzantine Agreement(비잔틴장군의 동의)

참고자료

• L. Lamport, R. Shostak, M. Pease, "The Byzantine Generals Problem", people.eecs.berkeley.edu, 1982-06

같이 보기

• 합의 알고리즘
• 프랙티컬 비잔틴 장애 허용
• 텐더민트 비잔틴 장애 허용

이 비잔틴 장애 허용 문서는 알고리즘에 관한 토막글입니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 이 문서의 내용을 채워주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW) 매칭 알고리즘 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반