분산 시스템 필독 논문 10선
원제: Distributed Systems Classics (2017)
왜 중요한가
분산 시스템의 기초 이론을 10편으로 압축한 이 목록은, 클라우드 인프라 설계자나 데이터베이스 엔지니어가 이론적 토대를 쌓는 데 실용적인 출발점이 된다.
엔지니어 Nicolae Vartolomei가 2017년에 공개하고 2022년에 갱신한 이 목록에는, Lamport의 논문(1978)부터 Ongaro의 Raft(2014)까지 분산 시스템 연구의 기초를 이룬 10편의 논문이 정리되어 있다. Byzantine Generals Problem, Paxos, CRDT 등 핵심 개념을 망라한다.
분산 시스템을 공부하려는 엔지니어에게 어디서부터 시작해야 할지는 오랜 숙제다. Vartolomei가 정리한 이 목록은 그 입문점으로 설계되었다.
수록 논문은 총 10편이다. Leslie Lamport의 「Time, Clocks, and the Ordering of Events in a Distributed System」(1978)은 분산 시스템에서 시간 순서를 논리적으로 다루는 방법론을 제시했다. 1982년의 「Byzantine Generals Problem」は障害プロセスが존在하는 환경에서의 합의 불가능성を問い, 내결함성 연구에 결정적 영향을 주었다.
1985년에는 두 편의 주요 논문이 등장한다. Chandy·Lamport의 분산 스냅샷 알고리즘과, Fischer·Lynch·Paterson에 의한 FLP 불가능성 정리다. 후자는 단 하나의 장애 프로세스가 있어도 분산 합의가 보장되지 않는다는 사실을 증명한 것으로, 이후 합의 알고리즘 설계의 전제 조건이 되었다.
Lamport는 1998년과 2001년에 Paxos를 발표하고, 이를 쉽게 설명하는 「Paxos Made Simple」을 공개했다. 2008년에는 Satoshi Nakamoto의 Bitcoin 백서가 목록에 포함되어 있으며, 2011년에는 CRDT(Conflict-free Replicated Data Types)가 등장한다.
목록의 마지막은 2014년 Ongaro·Ousterhout의 Raft 논문이다. Paxos보다 이해하기 쉬운 합의 알고리즘을 목표로 설계된 Raft는 현재 etcd 등 주요 인프라에 광범위하게 채택되어 있다.