2019年度C&C賞受賞者

グループB

業績記

分散処理システムにおける基礎理論の確立に関する貢献

業績説明

　今日、コンピューティングシステムのアーキテクチャにおいては超分散化が急速に進展しています。1960年代に本格的な運用が始まった初期の集中型コンピューティングシステムでは全てのデータや処理は中央にある装置で集中的に実行されていました。そして処理規模の拡大に伴い進化した大型と小型コンピュータの連携による分散コンピューティングの時代を経て、21世紀にはインターネットの普及とともに超巨大なデータセンターによるクラウド化が急速に進みました。その後のインターネットの拡大、すなわち全てのものがつながるIoTの普及はさらなる超分散コンピューティング社会へのシフトを加速しています。特に、自動運転のように実世界の制御のためにリアルタイム性が重視される今日のコンピューティングシステムでは、超分散化された多種多数のデバイスと処理システムが一体となって、常に安定的で自律性の高い環境を構成することが必須となっています。  

　レスリー ランポート博士は、長年にわたる分散コンピューティングシステムに関する研究を通じて、その計算機処理環境に数学的な基礎を与え、特に分散システムで課題となる同期の問題を解決する多数のアルゴリズム群を提示しています。分散処理システムでの同期とは「プロセス同士が協調して動作するための手順や手段」を意味しますが、それらはマルチプロセッサシステム、データベース、フォールトトレランス等の非常に多くの、また身近な分野で広く応用されています。とりわけフォールトトレランスにおける合意形成アルゴリズムは、ネットワーク決済の一種であるブロックチェーンの基本的な考え方の出発点として認知されるなど、近年の同分野発展への貢献にも多大なものがあります。  

　博士がこれまで示した代表的な業績としては、１）論理時刻の導入とイベント順序付け、２）ブロックチェーンにも適用されるビザンチン故障とビザンチン将軍問題（The Byzantine Generals Problem）、３）共有メモリ型マルチプロセッサにおける逐次コンシステンシ、４）Bakery Algorithmを含む相互排除問題、５）時相論理、などがよく知られています。これらのアルゴリズムの発想の共通点は、いずれも物理時計のない分散処理システムにおいて、メッセージ送受信などのイベントに適切な番号付けと各プロセスでの判断基準（結果として合意形成されている）を定義し、曖昧性をもつ半順序を全順序に変換し、最終的に全体システムの実行に矛盾を起さない解を与えている点です。  

　なかでも「ランポートの論理クロック」として知られる、上記1)の業績は、複数のプロセッサ間での同期処理や分散データベースにおける一貫性維持制御など、多数応用がなされています。「物理的な」クロックをそろえることは現実的には困難であるため、実システムで重要なイベントの順序付けに着目し、発想したのがこの「ランポートの論理クロック」であり、1978年に発表された博士の代表的論文である、” Time, clocks, and the ordering of events in a distributed system “ の被引用数は11,000以上にも上っています。また、上記2)で示された分散システムにおける信頼性問題の提示、つまりビザンチンフォールトトレランスのあるシステムにおける合意形成条件の概念は、2010年代半ばに急速に普及が始まったブロックチェーンベースのビットコイン（仮想通貨の一種）等に利用されるようになり、社会的にも注目されています。具体的には、ビットコインにおける取引の改竄や、多重使用などのリスクは、博士が導いたビザンチン将軍問題内では裏切り者（分散環境における故障中の計算機に相当）として扱われており、この環境下で合意形成問題を解決することがビットコインの必須の成立条件となっています。一方、このような分散コンピューティングステムにおいてビザンチン将軍問題に帰結される故障をビザンチン故障（Byzantine Failure）と呼びます。本故障への対処を目的とし、信頼性が低いコンピュータネットワークにおける合意形成の問題を解決するプロトコルの集合は、Paxosアルゴリズムと呼ばれます。博士はコンピュータの故障と復旧問題を扱うPaxosアルゴリズムについても定式化を行い、その成果は今では複数のデータセンター間において複製されたデータを更新する際の合意形成プロトコルとして使用されています。以上のような分散システム研究に係る多数の業績に加え、博士のユニークな業績としては、数式の組版性能が非常に高く、学術領域の代表的論文執筆ツールである、LaTeXの生みの親であることも挙げられます。  

　情報通信社会ではインターネットや高速無線を基盤とし、超分散環境に対応するコンピューティングシステムが急速に普及、発展しつつあります。これらの実現において、分散処理システムに係る学術的な基礎理論の構築が果たしてきた役割は極めて大きく、ランポート博士が達成してきた数多くの研究成果とその応用を踏まえれば、C&C賞の受賞者としてふさわしいものと考えられます。