분산 제어에도 불구한 자기안정화

분산 컴퓨팅 분야에서 "자기안정화(self-stabilization)" 개념을 처음 정의하고 증명한 기념비적 논문. 단 6페이지지만, 그 영향은 토큰 링 네트워크부터 현대의 결함 내성 시스템까지 이어진다.

다익스트라가 던지는 질문은 단순하면서도 깊다. 느슨하게 결합된 프로세스들을 협력시키는 통상적 방법은 "적법한 상태(legitimate state)"라는 불변 관계를 유지하는 것이다 — 위반을 일으킬 수 있는 각 단계 앞에 검사를 두면 된다. 공통 저장소가 있다면 쉽다. 그러나 공통 저장소가 없고 시스템 상태가 여러 프로세스에 흩어져 있으며, 각 프로세스가 오직 "이웃"하고만 정보를 교환할 수 있다면 — 즉 분산 제어라면 — 문제는 복잡해진다.

다익스트라가 본 결정적 결함은, 그가 아는 모든 분산 제어 설계가 불안정하다는 것이었다. 일단 비적법 상태에 빠지면 영원히 그 상태로 남을 수 있었다. 그래서 그는 새로운 속성을 정의한다. 시스템이 초기 상태와 무관하게 유한한 단계 내에 적법한 상태에 도달하는 것이 보장될 때, 그 시스템을 "자기안정화" 시스템이라 부른다.

설정은 우아하다. 0번부터 N번까지 번호 매겨진 N+1개의 유한 상태 기계가 링(ring)으로 배열되어 있다. 링 중앙에는 "데몬(demon)"이 서서, 공정한 무작위 순서로 기계 하나에게 "스스로 조정하라"고 명령한다. 적법한 상태란 정확히 하나의 기계가 "특권(privilege)"을 가지는 상태이며 — 그 특권은 링을 따라 회전해야 한다. 이것은 곧 상호 배제 문제다.

다익스트라는 이 문제가 수개월 동안 자신을 괴롭혔다고 고백한다 — 해를 찾는 것과 해의 비존재를 증명하는 것 사이를 오가며. 그 돌파구는 세 가지 관찰에 있었다. 첫째, 모든 기계가 동일해서는 안 된다 — 데몬이 대칭성을 영원히 보존할 수 있기 때문이다. 그래서 하나의 기계를 예외적으로 만든다(대칭성 파괴). 둘째, 조정은 그 기계의 특권을 잃게 해야 한다. 셋째, 진정한 카운터는 불가능하므로 모듈로 K 카운터를 쓰되, 잘 정의된 것은 "동등성"뿐이다. 결과는 놀랍도록 간결한 알고리즘이며, K ≥ N이면 자기안정화가 증명된다. 더 놀라운 것은 — 중앙 데몬을 "분산 데몬"으로 바꿔도, 추가 개선 없이 그대로 작동한다는 것이다.

느슨하게 결합된 순차 프로세스들의 협력을 보장하는 체계적인 방법은 "시스템이 적법한 상태(legitimate state)에 있다"는 관계를 불변으로 유지하는 것이다. 그 불변 관계를 위반할 가능성이 있는 각 단계는, 그것이 실제로 위반을 야기하지 않는지 확인하는 테스트를 선행해야 한다.

공통 접근 가능한 저장소가 존재하지 않고 "시스템 상태"가 여러 프로세스에 분산된 변수들에 기록되어야 할 때, 그리고 각 프로세스가 오직 "이웃들(neighbours)"과만 정보를 교환할 수 있을 때 복잡한 문제가 발생한다. 지역 정보를 기반으로 한 지역 행동이 전역 목표를 달성해야 한다. 이러한 시스템들("분산 제어")은 설계되어 왔지만, 내가 익숙한 그러한 모든 설계는 일단 비적법 상태에 빠지면 영원히 그 상태로 남을 수 있다는 점에서 불안정하다.

0번부터 N번까지 번호가 매겨진 N+1개의 유한 상태 기계로 구축된 시스템을 고려한다. 기계들은 링(ring) 형태로 배열되어 있다. 링의 중앙에는 데몬(demon)이 서 있는데, 매번 "공정한 무작위 순서"로 기계들 중 하나에게 "스스로 조정하라"는 명령을 내린다. 조정 시 기계는 자신의 이전 상태와 두 이웃의 현재 상태의 함수인 새로운 상태로 전이한다.

적법한 상태란 정확히 하나의 기계가 특권을 가진 상태로 정의된다. 모든 가능한 후속 상태들 역시 적법해야 하며, 특권이 링을 따라 회전해야 한다. 다시 한 번 독자들에게 여기서 읽기를 멈추고 명시된 문제를 직접 풀어보라고 권유한다 — 이 문제는 수개월 동안 나와 함께했으며, 처음에는 그럴듯해 보이던 많은 해결책이 잘못된 것으로 판명되었다.

첫째. 핵심적인 관찰은, 우리의 기계들이 모두 동일하다면 문제를 풀 수 없다는 것이다. 기계의 수가 비소수이면 초기 상황은 순환 대칭성을 가질 수 있고, 데몬이 링 주위에 균등하게 간격을 둔 명령을 내리면 순환 대칭성은 파괴되지 않을 것이다. 모든 기계를 동일하지 않게 만드는 가장 유망한 선택은 하나의 기계를 예외적으로 만들고 나머지 모두를 상호 동등하게 만드는 것이다.

둘째. 조정 명령이 그 순간 특권을 가진 기계에게 향할 때만 효과가 있고, 그 결과 특권을 잃는 해를 찾을 수 있다. "특권을 가진" 함수가 적어도 하나의 기계가 특권을 가지도록 선택되면, "막다른 길"은 선험적으로 배제된다 — 링은 살아 있을 것이다.

셋째. 우리는 유한 기계에 국한되어 있으므로 모듈로 K 카운터를 도입한다. 두 카운터 값에 대해 모듈로 K의 최댓값이나 최솟값은 정의되지 않는다. 잘 정의되어 있고 모호함 없이 적용될 수 있는 것은 동등성(equality)과 후속 함수(successor function)이다. 이는 상태들의 동등성 관점에서 "특권을 가진" 함수를 정의하도록 제안한다.

기계 nr.0을 예외적으로 한다. 1 ≤ i ≤ N에 대해, 기계 nr.i가 그 왼쪽 이웃과 다를 때 — 즉 x[i] ≠ x[i-1]일 때 — 특권을 갖도록 한다. 예외적 기계 nr.0은 x[0] = x[N]일 때 특권을 갖는다. 이렇게 하면 적어도 하나의 기계가 항상 특권을 갖는다.

기계가 "발화(fires)"할 때 — 데몬이 특권 기계에 명령을 내릴 때 — 그것은 오른쪽 이웃에게만 특권을 줄 수 있다. 적어도 하나의 기계가 특권을 가져야 하므로, 유일한 특권 기계의 발화는 항상 유일한 특권을 오른쪽 이웃에게 준다. 일단 적법한 상태에서 시스템은 적법한 상태로 남을 것이고 특권은 링을 따라 회전한다.

임의의 상태에서 시작할 때 무슨 일이 일어나는가. 예외적 기계가 처음으로 발화할 때, 그 새로운 상태를 파란색이라 부르고 다른 모든 상태를 흰색이라 부른다. 그때부터 예외적 기계가 생성하거나 파란 상태로부터 복사된 각 상태는 파란색이다. K ≥ N이면, 예외적 기계의 처음 N번의 발화 후 — 모든 상태가 파란색이 되고 같은 값이 되어 — 시스템은 적법한 상태에 도달한다.

여기까지는 좋지만, 내가 구현하기에 매우 불편할 수 있는 다소 강력한 데몬을 도입했다는 반론이 제기될 수 있다. 우리는 그 중앙 집중화된 기관을 "분산 데몬(distributed demon)"으로 대체할 수 있을까?

각 변수를 두 이웃이 연결하는 사적인 양방향 스위치로 갖추어 동시 접근을 배제한다고 가정하자. 그리고 기계들이 유한한 속도와 빈도로 스스로 조정한다고 가정하자 — 데몬의 명령을 기다리는 대신에. 작동할까? 놀랍게도 추가적인 개선 없이 작동한다.

일반 기계 nr.i의 조정은 왼쪽 이웃의 동시 활동으로부터 영향을 받을 수 없다. x[i-1]이 두 검사 사이에 값을 바꾸면, 첫 번째 값이 x[i]와 달랐다면 프로그램은 이 값이 처음에도 제공된 것처럼 행동하고, 두 번째 값이 x[i]와 같으면 할당은 효과가 없어 조정이 일어나지 않은 것과 같다.

N+1개의 유한 상태 기계가 링으로 배열되어 있다. 임의의 — 무질서한 — 초기 상태에서 출발한다. 여러 기계가 동시에 "특권"을 가진 비적법 상태다. 데몬이 기계들을 차례로 발화시키면, 예외적 기계 nr.0이 새로운 "파란" 상태를 만들고, 그 상태가 링을 따라 복사되어 퍼진다. K ≥ N이면, 유한한 단계 안에 모든 기계가 같은 상태가 되어 — 정확히 하나의 특권만 남는 적법한 상태로 수렴한다.