부분 동기 모델 (Partial synchrony model)

합의 알고리즘을 설계할 때는 해당 합의 알고리즘이 어떠한 환경에서 합의를 이룰 수 있는지 엄밀한 정의가 선행되어야 한다. 특히, 블록체인 네트워크는 여러 대의 노드로 구성되기 때문에 각 노드가 주고 받는 메시지의 지연 시간(delay) 대한 고려가 필요하다.

분산 컴퓨팅에서는 전통적으로 크게 2가지 커뮤니케이션 모델을 이야기한다.

먼저, 동기 모델(synchronous model)에서는 time bound Δ가 있어서 모든 메시지가 Δ 안에 도착하는 것이 보장된다.

반대로 비동기 모델(asynchronous model)에서는 메시지가 정해진 시간 내에 도착한다는 보장이 없다. 하지만 메시지가 언젠가는 도착한다는 보장은 있다.

우리가 알고 있는 각각의 합의 알고리즘은 동기 혹은 비동기 모델을 가정하고 해당 합의 알고리즘이 safety와 liveness를 보장한다는 사실을 증명한다. 따라서 동기 모델을 가정하고 safety와 liveness를 증명한 합의 알고리즘의 경우 비동기 모델을 상정했을 때 이러한 속성이 유효하다는 보장이 없다.

동기 모델을 가정한 합의 알고리즘의 예로 비트코인의 작업증명(PoW) 합의 알고리즘이 있다. 비트코인은 10분 안에 비트코인 네트워크에 연결된 모든 노드에 메시지(블록/트랜잭션)이 도착한다는 전제 하에 합의 알고리즘을 설계하였다.

동기 모델을 가정한 합의 알고리즘은 메시지가 도착하는데 소요되는 시간 Δ만큼 타임아웃을 두어야 하므로 효율성이 떨어진다. Δ 값을 줄이면 효율성을 높일 수 있지만, 메시지가 Δ+ϵ 이후에 도착하기 시작하면 합의 알고리즘의 가장 중요한 속성인 safety와 liveness가 깨진다. 비트코인의 블록 생성 시간인 10분이 길다고 이 시간을 마냥 줄일 수는 없는 이유가 여기에 있다.

비동기 모델은 네트워크 지연에 대해 아무런 전제도 하지 않기 때문에 훨씬 더 견고한 합의 알고리즘을 설계할 수 있다. 고정된 타임아웃 값이 아닌 실제 네트워크의 속도에 비례해 합의를 진행할 수 있다는 점도 장점이다. 하지만 비동기 모델을 가정한 합의 알고리즘은 알고리즘이 복잡하고 속성을 증명하기도 어렵다는 단점이 있다.

또한, 비동기 모델을 가정하면 아예 합의 자체가 불가능한 경우도 생긴다. 대표적으로 Fischer, Lynch, Paterson이 1985년 발표한 논문은 비동기 모델에서는 단 하나의 노드라도 fail-stop (비잔틴 노드가 아닌 단순 크래시)하면 합의가 불가능하다는 사실을 증명하였다.

동기 모델과 비동기 모델 모두 합의 알고리즘을 설계하는데 있어 아쉬운 점이 있는데, 이러한 문제를 해결하고자 Dwork, Lynch, Stockmeyer가 1988년 논문에서 부분 동기 모델(partial synchrony model)을 제안하였다. 부분 동기 모델은 네트워크가 동기 상태와 비동기 상태를 번갈아 오간다고 가정한다.

부분 동기 모델은 조금 더 엄밀하게 정의하면 다음과 같다. 네트워크에 GST(Global Stabilization Time)라는 이벤트가 있는데, GST가 언제 일어날지는 알 수 없지만 일단 일어나고 나면 정해진 시간 Δ 내에 모든 메시지가 도착한다. 네트워크가 GST 이전에는 비동기 모드로 있다가 GST 이후에 동기 모드가 된다고 생각할 수 있다. 노드 입장에서 언제 GST가 일어났는지 알 수 있는 방법은 없다.

부분 동기 모델을 가정한 합의 알고리즘은 네트워크가 비동기인 상태에서도 항상 safety를 보장하고, GST가 발생하여 네트워크가 동기 모드가 되면 liveness를 보장하는 방식을 취한다. BFT 계열의 합의 알고리즘은 대부분 부분 동기 모델을 가정하고 있는데, 코드체인에서 사용하고 있는 텐더민트와 리브라 프로젝트에서 차용한 LibraBFT(HotStuff 기반)도 모두 부분 동기 모델을 가정하고 합의 알고리즘을 설계하였다.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s