[분산시스템특론] 2. 두 장군 이야기

두 장군 이야기

어느 중세시대, 적의 부대 Z를 아군부대 A와 B가 동시에 공격하려고 한다.

이때 이 두 부대가 동시에 적의 부대를 공격해야만 이길 수 있으며, 두 부대 사이에는 적의 부대가 존재하기 때문에, 전령이 메세지를 전달하기 위해서는 적진을 은밀하게 뚫고 지나가야 한다고 해보자.

 

과연 A와 B는 동시에 Z를 공격하는 것이 가능할까?

 

우선 A와 B는 언제 동시에 공격할 지 먼저 공격 시간을 정해야 한다.

만약 현대같이 그냥 카톡같은 메신저가 있다면 A가 '10시에 공격하자' 라고 해도 B가 빠르게 이를 확인하여 서로 합의에 다다를 수 있을 것이다.

하지만 이 상황에서는 사람이 직접 적진을 뚫고 메세지를 전달해야 하기 때문에 전령이 중간에 잡혀서 죽으면 메세지가 유실될 수도 있다.

 

만약 전령이 메세지를 전달하는데 성공했다고 해보자.

과연 그때도 A와 B는 서로 안심하고 10시에 동시에 공격할 수 있을까?

안타깝게도 그럴 수는 없다.

전령을 보냈던 A 입장에서는 내가 보낸 메세지가 B에게 도착했는지, 중간에 유실되었는지 알 수 없다.

만약 중간에 유실되었는데 도착했을 것이라고 믿고 10시에 공격을 감행했다가 혼자 공격을 가게되면 패배할 것이다.

따라서 B가 메세지를 받으면, 메세지를 잘 받았다는 응답을 A에게 다시 보낼 필요가 있다.

 

하지만 그 응답 역시 중간에 적진을 뚫고 가다가 유실될 수도 있다.

따라서 설사 그 메세지가 A쪽으로 잘 도착했더라도, B 입장에서는 섣불리 공격을 감행할 수 없다.

왜냐하면 A가 B로부터의 응답을 성공적으로 받지 못했다면, A는 B로 메세지가 도착했다는 것을 확신할 수 없어 공격을 나갈 수 없기 때문이다.

결국 B가 다시 확신을 얻으려면 A는 자신이 메세지를 받았다는 응답을 B에게 보내주어야 한다.

 

이 응답이 성공적으로 도착하지 않으면 A는 B가 공격할 것임을 안심할 수 없기 때문에, 다시 이에 대한 응답을 추가로 받아야 하고, 이것이 연쇄적으로 계속 발생하기 때문에 이론상 이 둘 사이의 합의는 절대 일어날 수 없다.

 

다만 공학적으로는 둘 사이에 무한히 메세지를 주고받을 수는 없으므로, 약간의 유도리를 둬서 정해진 시간 안에 메세지를 받으면 상대방이 동의한 것으로 간주하고 통신을 연결하는 방법을 사용한다.

즉, 양쪽이 한번씩 응답을 받았으면 서로 동의한 것으로 간주하는 것이다. (3-way handshaking)

다만, 이는 어디까지나 '간주' 하는 것이기 때문에 '보장'은 할 수 없다.

 

네트워크에서는 내가 보낸 메세지가 상대방에게 반드시 도착할 것이라는 보장을 할 수 없다.

또한 내가 보낸 메세지가 상대방에게 성공적으로 도착한다면 적어도 어느 시간 안에는 반드시 도착한다는 것도 보장을 할 수 없다.

만약 이 둘 중 하나라도 보장할 수 있다면 그 사람은 노벨상을 탈 수 있다.