Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial

June 26, 2022

サーバのレプリケーションによってフォールトトレランスを高めることができるが、レプリケーション間の合意形成のプロトコルが必要になる。 そこで、ステートマシンをモデルにプロトコルを定義する手法を、Fail Stopとビザンチン将軍問題で例示する。 ステートマシンは、状態変数を決定的に変更するコマンドからなり、入力系列のみから出力が決まる。 モデルは、複数のステートマシンを同じ初期状態から開始し、同じ入力を与え、出力の合意をはかる。

ここでは、ステートマシンが仕様を満たさない状態をフォールトとよぶ。 ステートマシンへのリクエストが遅延するとステートマシンはフォールトになりえる。 すべてのレプリカが同じリクエストの系列を受信し処理する要件は、2つに分解できる。 ひとつは、合意についての要件で、すべてのフォールトでないステートマシンがすべてのリクエストを受信することである。 もうひとつは、順序の要件で、すべてのフォールトでないステートマシンが、受信したリクエストと同じ順序で処理することである。

あるクライアントやステートマシンがほかのステートマシンを値を伝達する場合、伝達するステートマシンがフォールトでなければ、フォールトでないステートマシンが伝達された値に合意するとき、合意の要件は満たされる。 伝達するステートマシンがフォールトであれば、ある同じ値に合意できればいい。 ビザンチン将軍問題であれば、Strong, H.R. and D. DolevらのByzantine agreementが、この要件をみたす。 ただし、FLP帰結により、ビザンチン将軍問題があり、ステートマシンの処理やリクエストの遅延に有界を想定しなければ、これを実装することはできない。

順序の要件は、Lamportのlogical clockで実装できる。 これは、分散システムにおけるメッセージに全順序関係をあたえる。 ステートマシンはそれぞれ整数の時刻をもち、イベントにタイムスタンプを割り当てる。 ステートマシンは、ステートマシン上でイベントが起きる度に時刻をインクリメントする。 メッセージは、時刻とペアにして送信される。 メッセージを受信したステートマシンは、そのステートマシンがもつ時刻と添付された時刻のうち、大きい方をインクリメントした値に時刻を更新する。

論文のリンク