분산 시스템의 고전들 — 분야를 만든 논문 10편

본문

Nicolae Vartolomei가 2017년에 공개하고 2022년 9월에 갱신한 이 글은 분산 시스템 연구를 형성한 시대를 초월한 영향력 있는 논문들을 선별한 목록입니다. 저자는 이 목록이 분산 시스템이라는 문제 공간을 더 잘 이해하기 위한 출발점이 되도록 의도했다고 밝히고 있습니다.

목록의 구성 — 1978년부터 2014년까지

목록은 연대순으로 구성되어 있으며, 첫 번째 논문은 Leslie Lamport의 1978년작 'Time, Clocks, and the Ordering of Events in a Distributed System'입니다. 분산 시스템에서 물리적 시계 없이 사건의 순서를 정의하는 논리 시계와 happens-before 관계를 제시한 이 분야의 출발점으로 꼽힙니다. 이어서 1982년 Lamport, Robert Shostak, Marshall Pease의 'The Byzantine Generals Problem'은 임의의 방식으로 실패할 수 있는 노드가 존재할 때 합의에 도달하는 문제를 형식화한 논문으로, 오늘날 Byzantine Fault Tolerance라 불리는 연구 흐름 전체의 뿌리입니다.

1985년에는 두 편의 중요한 결과가 나란히 수록되어 있습니다. K. Mani Chandy와 Lamport의 'Distributed Snapshots'는 실행 중인 분산 시스템의 일관된 전역 상태를 결정하는 알고리즘을 다루며, Michael J. Fischer, Nancy Lynch, Michael Paterson의 'Impossibility of Distributed Consensus with One Faulty Process'는 이른바 FLP 불가능성 정리로, 비동기 시스템에서 단 하나의 프로세스만 고장 나도 결정론적 합의가 불가능함을 증명한 결과입니다.

합의 알고리즘의 계보

1988년 Brian Oki와 Barbara Liskov의 'Viewstamped Replication'은 고가용성 분산 시스템을 위한 primary copy 방식을 제시하며 이후의 합의 프로토콜에 영향을 준 작업입니다. 이어 Lamport의 1998년 'The Part-Time Parliament'은 Paxos 알고리즘을 처음 제시한 원전이며, 2001년 'Paxos Made Simple'은 그 직관을 쉽게 설명하려는 후속 글입니다.

2008년 Satoshi Nakamoto의 'Bitcoin: A Peer-to-Peer Electronic Cash System'은 작업증명 기반 합의를 통해 비허가형 환경에서의 합의 문제를 실용적으로 풀어낸 논문으로 수록되었습니다. 2011년 Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski의 'Conflict-free Replicated Data Types'는 동시 업데이트를 수학적으로 충돌 없이 병합하는 CRDT를 다룹니다. 마지막으로 2014년 Diego Ongaro와 John Ousterhout의 'In Search of an Understandable Consensus Algorithm'은 이해 가능성을 설계 목표로 삼은 Raft 합의 알고리즘으로, 현재 많은 분산 시스템 구현에서 실질적인 표준으로 자리 잡았습니다.

이 목록이 고전으로 분류되는 이유는 각 논문이 단순한 기법 소개를 넘어 분산 시스템의 근본적인 한계와 가능성을 규정했기 때문입니다. 시간의 순서 정의, 장애 모델의 형식화, 합의의 불가능성과 실현 가능한 합의 알고리즘까지, 목록을 순서대로 읽으면 이 분야가 어떤 질문을 거쳐 발전해 왔는지 그 흐름 자체를 따라갈 수 있습니다.

Hacker News 반응

• @nesarkvechnep — 이런 목록에는 늘 빠지는 것이 Joe Armstrong의 박사 논문 'Making reliable distributed systems in the presence of software errors'라며 Erlang 설계의 토대가 된 이 논문을 꼽습니다.
• @Suhinnall27 — 알고 있는 다른 포함할 만한 작업이 있는지 질문합니다.
• @FabHK — 분산 합의를 공부하려는 사람에게 Tim Roughgarden의 YouTube 강의 'Foundations of Blockchains'를 추천합니다. 제목과 달리 12개 강의 85개 영상으로 엄밀하고 잘 설명되어 있으며 CS 기초를 전제로 합니다. 강의별 읽기 목록과 함께 Elaine Shi의 'Foundations of Distributed Consensus and Blockchains', Andrew Lewis-Pye의 'Consensus in 50 pages'도 지적합니다.
• @jermberj — Armstrong의 논문이 목록에 없는 것은 사실상 교과서이기 때문일 수 있다고 반박합니다. 295페이지 분량인데 원문 목록 논문들의 평균 분량은 대략 15페이지 수준이라는 것입니다.
• @vulcan01 — 그의 논문은 일반적인 박사 논문보다 조금 긴 정도라고 응수합니다.

원문: Hacker News / 번역·요약: Trawling