Edsger  W.  Dijkstra

컴퓨터를 만든 15 인의 과학자 : Dennis Shasha. Cathy Lazere 공저, 박영숙 옮김, 세종연구원, 1998 (원서 : Out of Their Minds : 1995)

질겁할 만한 산문과 최단 경로

최단 경로

결정적 섹션의 문제

만찬의 철학자들

미국의 다이크스트라

수학의 심연

난 어머니 [수학자] 에게  수학이 어려운 주제이냐고 물었습니다.
어머니는 반드시 모든 공식을 배우라고, 그러면 틀림없이 그걸 알 게 될 거라고 하셨지요.
또 한 가지 기억해야 할 것은 무언가를 증명하는 데 다섯 줄 이상이 필요하다면 그 방법은 잘못된 것이란 사실입니다. - 에드스거 W. 다이크스트라

옷의 디자인처럼 과학에도 어떤 유행이 있다. 자기 분야의 근본적인 문제들과 씨름을 하느라 유행을 무시해 버리는 몇 안되는 사람들은 큰 도박을 하고 있는 셈이다. 성공하는 사람들은 비판을 할 수 있는 권리를 얻게 된다. 에드스거 W. 다이크스트라는 1950 년까지 거슬러 올라가는 그의 삶 전반에 걸쳐 성공적으로 도박을 하면서 신랄한 비판까지 해 왔다. 최단 경로 알고리즘과 상호 배제에 대한 그의 연구는 그가 나머지 세계도 공유하기를 원하는 구세계의 세련미와 단순성으로 특징지을 수 있다.

1930 년 로테르담에서 태어난 다이크스트라는 두 과학자의 아들이다. 그의 아버지는 화학자였고 그의 어머니는 수학자였던 것이다. 다이크스트라는 일찍이 과학에 소질과 흥미를 나타냈다.

1942 년 다이크스트라는 12 살의 나이로 엘리트 고등학교인 김나지움 에라스미니엄에 입학하였다. 그 곳에서 그는 전통 독일식 교육을 받으면서 고전 그리스어와 라틴어, 프랑스어, 독일어, 영어, 생물학, 수학, 물리학, 화학 등을 공부하였다. 전쟁은 다이크스트라와 그의 가족을 포함해 대부분의 독일 시민들에게 고난을 안겨 주었다. 점령기의 막바지에 다다르면서 먹을 것이 귀해지자 그의 가족들은 그를 도시 밖으로 내보냈다.

어린 다이크스트라는 1945 년 7 월 다시 가족들과 결합하였다. 그 시기의 상황은 정치적 이상주의가 감돌고 있었다. 다이크스트라 자신은 법을 공부해 국제연합에서 조국을 위해 일하겠다는 생각이었지만, 그의 아버지는 그런 생각을 단념하도록 설득하였다.

대신 그는 라이덴 대학에 들어갔고, 거기서는 물리학과 수학 가운데 하나를 선택해야만 했다.

이론 물리학을 공부하기로 선택한 다이크스트라는 그 분야의 많은 문제들이 광범위한 계산을 요구한다는 것을 깨닫고 프로그래밍을 배우기로 마음먹었다. 전시에 암호 해독 작업을 한 경험을 토대로 영국인들은 1940 년대와 50 년대에 걸쳐 유럽식 계산의 발전을 주도하였다. 1951 년 다이크스트라는 케임브리지 대학에서 프로그래밍 과정 여름 학교에 참가하였다. 1952 년 3 월에는 암스테르담의 수학센터에서 시간제 일자리를 얻었고, 그 곳에서 일하면서 컴퓨터 프로그래밍에 점차 깊이 관여하게 되었다.

1950 년대 초 포트란이나 리스프가 등장하기 이전에는 프로그래머들이 각 컴퓨터의 특이한 설계에 맞추어 프로그램을 작성하였다. 일반적으로 프로그래머에게는 기계가 수행할 수 있는 명령어들의 리스트가 주어졌다. 하드웨어 설계사들은 만일 프로그래밍의 복잡성을 희생시키는 것으로 자신들의 설계를 단순화할 수만 있다면, 주저없이 그렇게 하였을 것이다. 하지만 다이크스트라와 함께 일하고 있었던 하드웨어 설계사들을 정반대였다.

이 무렵까지만 해도 다이크스트라는 완전히 프로그래밍에 인생을 건 것은 아니었다. 당시 네덜란드에는 사실상 프로그래밍 분야가 잘 알려져 있지도 않았다.

다이크스트라의 의구심은 당시 널리 만연해 있던 프로그래밍에 대한 문지를 반영하는 것이었다. 다이크스트라가 역시 프로그래머였던 동료 데베츠 (M. C. Debets) 와의 결혼 허가 신청을 하려 했을 때에도 당국에서 프로그래머를 직업으로 인정하지 않아, 결국 그는 마지못해 자신에게 '이론을 다루는 물리학자 (theoretical physicist)' 라는 꼬리표를 달아야 했다.

최단 경로

다이크스트라가 아직 수학 센터에 몸담고 있던 시절, 그는 다가오는 1956 국제 수학 회의에서 ARMAC 의 역량을 보여 달라는 요구를 받았다. 그는 철도 지도상에서 두 지점 간의 최단 노선을 결정하는 문제에 대해 생각하기 시작했다. 어느 화창한 토요일 아침, 다이크스트라는 아내와 함께 카페 테라스에 앉아 커피를 마시고 있었다. 갑자기 그는 침묵에 잠겼다.

그림 1  다이크스트라의 최단 경로 알고리즘

원래의 코어 세트는 S 만으로 구성될 것이다.
다음으로, C3 이 총 시간 비용 2 를 가지고 추가될 것이다.
다음으로, C2 가 S→C3→C2 의 경로를 거쳐 총비용 4 로 추가될 것이다.
다음으로, C1 이 총비용 5 로 추가될 것이다.
그렇게 하여, 이 시점의 코어 세트는 S, C1, C2, C3 로 구성된다.
다음으로, C4 가 S→C1→C4 의 경로를 통해 11 의 비용으로 추가될 것이다.
이 시점에는 T 가 S→C3→C2→T 의 경로를 통해 16 의 비용으로 추가될 것이다.

그림 1 은 철도 노선 대신 고속도로를 사용하여, 다이크스트라가 스스로에게 제기하였던 문제를 개략적으로 나타낸 것이다. 거기서 해야 할 일은 S 도시에서 T 도시까지 가장 빠르게 가는 노선, 즉 최단 경로를 찾아 내는 것이었다. 독자들도 범례 텍스트나 다음 단락으로 넘어가기 전에 먼저 그 문제를 풀어 보기 바란다.

다이크스트라의 기본적인 접근 방식은 출발지인 S 도시와 목적지인 T 도시 사이에서 끊임없이 커지는 도시들의 '코어 세트 (core set)' 를 만드는 것이었다. 그 알고리즘의 모든 주어진 단계마다 코어세트 내의 어떤 도시에 이르는 최단 시간은 모두 미리 주어져 있다. 처음에는 코어 세트가 S 도시만으로 구성될 것이며, 그 곳에 이르는데에는 전혀 시간이 걸리지 않는다. 각각의 후속 단계에서는 코어세트 외부에서 한 도시를 찾아내 그것을 X 로 명명한다. 이 때, X 는 S 도시에서 코어 세트 외부의 다른 어떤 도시로 가는 것보다 X 까지 가는 데 걸리는 시간이 가장 짧다는 속성을 가진다. 어떤 경로를 따라 이동하는 데에는 최소한 0 분이 걸리기 때문에, X 는 코어 세트내의 어떤 도시에 직접 연결되어 있어야만 한다. 그걸 Y 라고 하자. 그러면 이제 X 까지 가는 시간은 S 도시에서 Y 까지 가는 데 걸리는 최소한의 시간 (Y 는 코어 세트 내에 있으므로 이 값은 이미 알려져 잇다) 에다 Y 에서 X 까지 가는 시간을 더한 값이 된다. 자, 이 X 를 코어 세트에 추가시키고 계산된 시간을 기록한다. X 가 도시 T 가 될 때 그 과정은 끝이 난다. 그림 1 은 이 알고리즘의 각 단계에서 코어 세트가 어떤 식으로 커지는가를 보여 준다.

이제 간단히 다이크스트라의 알고리즘이라 불리고 있는 최단 경로의 알고리즘은 그동안 철도 건설, 통신 네트워크의 경로 설계, 항공기 운항 계획 등 모두 목적지에 이르는 최선의 길을 찾아 내야 하는 응용 분야에서 사용되어 왔다. 다이크스트라는 곧이어 연관된 실질적 문제를 해결하기 위해 그 알고리즘의 방향을 살짝 변경하였다.

기계 설계를 담당한 루프스트라 (Loopstra) 와 숄텐 (Scholten) 은 ARMAC 의 엔지니어였던 인물들로, 자신들의 다음 번 기계를 제작하면서 가능한 한 값이 비싸지 않은 구리를 사용해 반드시 필요한 모든 회로에 전기를 전달할 방법을 찾고 있었다. 다이크스트라는 기술상의 이유에서 자신이 직접 '최단 부분확장 트리 알고리즘' 이라 명명했던 방법을 사용해 그 문제를 해결하였다.

당시 그것은 예사롭지 않은 논문이었다. 그 한 가지 이유는 유한 문제를 해결하는 효율적인 방법을 제안했다는 것 때문이었고, 또 한 가지 이유는 그것이 결과들을 주의 깊게 증명하였기 때문이었다.

결정적 섹션의 문제

상호 배제 (mutual exclusion) 와 협동 순차 처리 (cooperating sequential processes) 에 대한 다이크스트라의 혁신적 연구는 1960 년대 초 ARMAC 의 후계자인 X1 과 그 뒤를 이은 X8 의 설계로 시작되었다. 이들은 하드웨어의 관점에서 볼 때 그 당시의 대표적인 기계들이었다.

이와 달리, 소프트웨어는 어떤 흐름을 타기 시작했다. 다이크스트라는 컴퓨터에 부착된 각각의 장치가 컴퓨터와 메시지를 교환하면서 한 번에 한 단계씩 작업을 수행하도록 배열하였다. 컴퓨터 전문용어로는 이를 통신 순차 처리라 부른다. 다이크스트라는 이 절차들을 조정하거나 동기화하여 '내가 그것들에 대해 조리 있게 추론할 수 있도록' 만드는 방법을 생각하기 시작했다.

프로그래머들은 이러한 도전을 아주 빈번하게 경험한다. 두 가지 처리가 동시에 동일한 자료에 접근한다고 가정해 보자. 한 가지 처리가 그 자료를 수정하면 그로 인해 다른 처리가 잘못 행동하는 결과가 초래된다. 잘못된 행동을 피하기 위해서는 그 처리들 가운데 하나가 공유 자료에 접근하는 동안에 다른 하나가 접근하지 말아야 한다. 이것이 바로 다이크스트라가 동기화라는 용어를 빌어 나타내고자 한 바이다.

다이크스트라는 다시 열차에 대해 생각해 보았다. 이번엔 신호기 (semaphore) 라고 부르는 열차의 신호 체계에 관한 것이었다. X 도시와 Y 도시 사이에 따로 설치된 두 줄의 트랙이 있다고 가정해 보자. 하나는 X 에서 Y 로 가는 것이고 다른 하나는 Y 에서 X 로 향하는 것이다. 두 트랙이 그 노선의 일정 구역에서 하나로 좁혀진다면, 양 방향에서 달리고 있던 열차들이 같은 구획의 트랙을 사용해야만 한다. 충돌을 피하기 위해 엔지니어들은 신호기를 사용하여 그 공유된 트랙 위에 반드시 한 번에 한 대의 열차만 있도록 만든다. 신호기는 한 번에 오직 한 방향으로만 녹색등이 켜지고, 어느 한 대의 열차가 트랙의 그 결정적인 구획 위에 머무는 동안에는 절대로 그 신호의 색이 변하지 않도록 해 준다. 따라서, 신호기의 사용은 주어진 시간동안 그 결정적인 트랙 위에는 오직 한 대의 열차만이 있게 되는 것을 보장해 준다. 이것을 상호 배제라고 한다.

다이크스트라는 상호 배제의 개념을 컴퓨터와 이에 접속된 키보드 사이의 통신에 적용시켰다. 이들 두 장치는 버퍼 (buffer) 라고 알려져 있는 기억 장치 내의 통신 영역을 통해 정보를 교환한다. 기본 원칙은 이 두 가지 장치가 버퍼를 읽거나 쓰는 행동이 한 번에 하나씩만 이루어져야 한다는 것이다.

1961 년 다이크스트라는 철도 신호기로 제시된 두 가지 조작, 즉 P 와 V 를 사용해 반드시 필요한 프로토콜들을 표현하는 방법을 생각하였다. P 는 독일어로 '통과하다' 라는 뜻의 passeren 을 의미하며, V 는 '자유를 주다' 라는 뜻을 가진 vrijgeven 의 머릿글자이다. 컴퓨터 과학 분야에서는 거의 영어를 사용함에도 불구하고 컴퓨터 설계사들이 아직까지 이 약자들을 사용하고 있다는 것은 바로 이 아이디어의 위력을 보여주는 증거이다. 다이크스트라의 세련된 해법은 깔끔한 추론에 대한 그의 바람에서 비롯된 결과였다.

그것은 분명 더 이상 사실이 아니다. 실제로 현대의 모든 프로세서들과 대부분의 메모리 보드는 하드웨어에서 테스트-세트 (test and set) 명령이나 그와 비슷한 어떤 명령을 사용하여 P 와 V 의 기능을 지원한다. 이들 명령은 버퍼같은 컴퓨터 자원을 잠그고 복귀가 성공하거나, 아니면 그 자원이 이미 잠겨 있어 복귀가 실패라는 결정을 내린다. IBM 의 360 아키텍처는 1964 년 최초로 테스트-세트를 실행 시켰던 것 가운데 하나로서, 그 아이디어의 전체적인 합리성을 제시해 주었다.

만찬의 철학자들

다이크스트라에게는 동료들과 다른 방식으로 사물을 보는 능력이 있었다. 그것은 그 자신이 '내가 고립되어 있다는 행복한 사실' 이라고 표현했던 상황에서 비롯된 결과였다. 다른 사람들이 지나쳐 버리는 본질적인 문제들을 끄집어 내는 그의 능력은 1965 년 다시 한 번 뚜렷하게 부각되었다.

그 해 가을의 어느 날 저녁, 다이크스트라는 자리에 앉아 자신의 아인트호펜 공과대학 학생들을 위해 지금은 널리 알려져 있는 시험문제 하나를 출제하고 있었다. 다이크스트라는 그것을 만찬의 5 조 (dining quintuple) 문제라고 불렀었지만, 얼마 안 있어 옥스퍼드의 호아 (C. A. R. Hoare) 교수가 지어준 만찬의 철학자들 문제라는 이름으로 유명해지게 되었다.

후난 성의 철학자 다섯 명이 탁자에 둘러 앉아 있다고 상상해 보자. 그들은 각자 밥이 가득 담긴 밥그릇과 그 한쪽 옆에 놓인 젓가락을 하나씩 가지고 있다. 각 철학자의 오른쪽 젓가락은 그 옆에 앉은 사람의 왼쪽 젓가락이 된다. (그림 2 참조) 자, 그 만찬의 규칙은 다음과 같다.

1. 각 철학자는 잠시 동안 생각을 하고, 잠시 동안 먹고 난 다음, 잠시 동안 기다린다.

2. 먹을 때는 반드시 오른쪽 젓가락과 왼쪽 젓가락을 모두 집어야 한다.

3. 철학자들은 젓가락을 집어 들거나 내려 놓는 것만으로 의사소통을 한다. (말을 할 수도 글을 쓸 수도 없다.)

철학자들 각자가 먹기 위해서 다음과 같은 알고리즘을 사용한다고 가정하자.

(i) 오른쪽 젓가락을 사용할 수 있을 때 그것을 집어 올린다. (오른쪽에 앉은 사람이 그것을 들고 있을 경우엔 기다린다).

(ii) 왼쪽 젓가락을 사용할 수 있을 때 그것을 집어 올린다. (왼쪽에 앉은 사람이 그것을 들고 있을 경우엔 기다린다).

(iii) 먹는다.

여기서 몇 가지 경우가 발생할 수 있다. 만일 모든 철학자들이 동시에 먹기 시작하려고 결심한다면 그들은 (i) 단계에는 모두 성공하겠지만 (ii) 단계에서는 영원히 기다려야만 하는 결과가 될 것이다. 이러한 상황을 '교착 (deadlock)' 이라 부른다.

동료 철학자들이 모두 한 개의 젓가락만을 들고 있는 것을 보면서 (ii) 단계에서 기다리고 있던 어떤 철학자가 자신의 오른쪽 젓가락을 내려놓고 잠깐 동안 조용히 앉아 오른쪽 사람이 먹는 것을 지켜볼 수 있다. 이렇게 되면 이타적인 철학자는 결코 먹지 못하게 될 가능성이 있다. 이러한 상황을 '기아 (starvation)' 라고 한다.

모든 철학자가 먹는다 하더라도 일부가 다른 사람들보다 많이 먹을 수 있다. 이러한 상황을 '공평성의 결여 (lack of fairness)' 라 부른다. 즉, 인생을 나타내는 것이다.

컴퓨터 네트워크에서는 만찬의 철학자들 문제의 다양한 변형들을 종종 볼 수 있다. 예를 들어, 근거리 통신망 내의 컴퓨터들은 흔히 한 번에 단 하나의 메시지만 보낼 수 있는 선이나 방송 채널을 공유한다. 만일 모든 사이트들이 동시에 전송을 시도할 경우 모두 실패하게 된다. 그리고 나서 곧바로 재시도를 하면 또 다시 실패하게 된다. 이것은 교착과 유사하다. 만일, 어느 하나의 사이트가 항상 우선권을 가진다면, 다른 사이트가 기아 상태에 놓이거나 혹은 프로토콜이 불공평하게 될 것이다.

마이클 라빈이 다음 장에서 보여 줄 것처럼, 철학자들이나 네트워크 양쪽 모두에 적용되는 한 가지 해법은 무작위화 (randomization) 이다. 어떤 한 철학자나 사이트가 필요로 하는 자원을 확보할 수 없을 경우, 다소 임의적인 과정 [예를 들면, 신틸레이션 (scintillation) 계수기] 에 의해 결정되는 일정한 양의 시간 동안 기다리고 나서 재시도를 하는 것이다. 이러한 구성 역시 그 과정이 규칙적인 것은 아니지만, 끊임없이 불운하게만 작용되어 여전히 기아 상태를 만들어 낼 수는 있다. 하지만 그런 사태가 발생할 가능성은 크지 않다.

다이크스트라는 만찬의 철학자들 문제를 제기하고 나서 몇 년이 지난 후, 그는 당시 존재하는 가장 복잡한 컴퓨터 시스템 가운데 하나였던 M.I.T. 의 멀틱스 (MULTIX) 설계자들이 교착에 대해 전혀 고려해 보지 않았으며, 그 시스템이 마치 아주 많은 철학자들이 각자 젓가락을 한 개씩만 들고 있는 경우처럼 이따금씩 갑자기 정지해 버릴 것이라는 사실을 알고 놀랐다. 다이크스트라는 깊이 생각하면서 완곡한 반어법을 사용해 이렇게 말한다.

미국의 다이크스트라

다이크스트라가 버로즈사 (Burroughs Corporation) 의 리서치 펠로우직을 받아들였을 때, 그는 그 지위를 이용하여 프로그래밍에서의 검증 가능성을 밀어 붙일 생각이었다. 하지만 그가 주창하는 규칙은 때로는 문화적 이유에서, 또 때로는 경제적 이유에서 명백하게 인기를 얻지 못하는 것으로 드러났다.

다이크스트라의 자극은 고급 소프트웨어에 대한 수요와 맞물리면서 소프트웨어 산업을 훨씬 더 단련되도록 만들어 왔다. 모든 프로그래머들에게 알려져 있는 다이크스트라의 신랄한 한 마디는 '해로운 것으로 여겨지는 GO TO' 이다. GO TO 는 프로그램이 하나의 작업을 수행하다가 첫 번째 작업으로의 복귀에 대한 계획 없이 전혀 다른 작업으로 옮겨 가도록 만든다. 많은 GO TO 명령을 가지고 있는 프로그램들은 거의 마르크스 형제의 영화에서 나오는 법률계약 만큼이나 따르기 쉬운 마르크스 형제의 영화에서 나오는 법률계약 만큼이나 따르기 쉬운 성향을 보여 준다. 그럼에도 불구하고, 많은 프로그래머들에게 창조적 자극이 절정에 달한 상태에서 자유로이 생각하며 해킹을 하는 것은 여전히 이상으로 남겨져 있다. 다이크스트라는 그런 식의 접근을 하나의 병리로 본다.

수학의 심연

1980 년대 초 다이크스트라와 그의 가족이 텍사스 주 오스틴으로 거처를 옮기면서 그는 텍사스 대학에서 컴퓨터 과학의 실럼버거 백주년 교수직 (Schlumberger Centennial Chair) 을 받았다. 이제는 아이들이 다 자라 그 부부는 자신들이 여행 기계라는 별명을 붙인 포크스바겐 캠핑용 자동차를 타고 여행을 즐긴다. 다이크스트라의 지적 여행에서 그는 자신의 엄격함에 대한 요구에 따라 수학으로 복귀하였다.

다이크스트라는 독자들에게 문제를 불러 일으키는 정의들에 대해 몹시 조바심을 한다. 한 번은 그가 윈스턴 처칠 (Winston Churchill) 의 『영어권 민족들의 역사 A History of the English Speaking Peoples』를 읽다가 중단한 적이 있다. 그 이유는 "그 책은 지나치게 난해했습니다. 그는 같은 민족을 각기 다른 이름들로 언급하려 했어요." 라는 것이었다. 다이크스트라에게 있어 훌륭한 정의와 숙련된 논쟁은 그 발상 자체만큼이나 중요한 요건이다.

다이크스트라가 최근에 컴퓨터 과학과 수학에서의 형식주의를 위해 추진한 운동은 『프로그램과 증명의 형식적 발전 Formal Development of Programs and Proofs』이라는 책을 탄생시켰다. 그의 중심적인 논제는 프로그램의 작성을 명료한 증명의 작성과 동일시한다. 이 논제와 고나련 주제들에 대한 연구는 각각 뮈니히 근교와 글래스고에서 열리는 두 곳의 여름 회의에서 이루어지고 있다. 그 회의 대부분에 대해 미국인들은 눈에 띌 만큼 참석을 꺼리고 있다.

다이크스트라는 간혹 나보코프 (Nabokovian) 적 성향을 지닌 인물, 말하자면 카우보이의 땅을 찾아 온 교양 있는 유럽인같은 모습을 보인다. 바로 그 때문에 그는 논쟁적인 인물이다. 한편, 그의 업적에 외경심을 느끼고 있는 젊은 컴퓨터 과학자들은 그가 여전히 문제가 되고 있는 사안들에 관심을 갖고 있는지를 의아하게 여긴다. 마찬가지로 다이크스트라는 그의 동료들이 선택한 주제들을 미심쩍게 바라본다. 예를 들어, 컴퓨터 과학 내에서 인공 지능이 어디에 적응되느냐로 물으면 그는 인상을 찌푸리며 "Not. (적응되지 않습니다)" 라는 답변을 할 뿐이다. 그는 인공 지능을 어느 정도까지는 미국인들 특유의 천진난만함의 표현이라고 여긴다.

다이크스트라는 양면을 가진 인물이다. 한쪽 면에서는 훌륭한 문제와 지속성 있는 해법들에 대한 사랑으로 컴퓨팅의 과학적 측면과 실용적 측면에 상당한 기여를 해 온 창조적 과학자의 모습을 볼 수 있다. 다른 한쪽 면에는 그가 가진 신랄한 펜 (대체로 몽블랑 펜이 쓰였음) 으로 인해 많은 동료들을 그에게서 멀어지게 만들어 온, 인간의 어리석음에 대해 좀처럼 참지 못하는 감시자의 모습이 있다. 다이크스트라는 자신이 이해하기 쉬운 사람이라고 주장한다.

다이크스트라의 연구 방법들을 간파해 보려고 하는 젊은 과학자들에게 그는 세 가지 황금률을 권한다.

1. 절대로 동료들과 경쟁을 하지 말라.

2. 자신이 할 수 있는 가장 어려운 것을 시도하라.

3. 과학적으로 건강하고 적절한 것을 선택하라. 과학적 통합성에 타협하지 말라.