Lazy consensus と Consensus の違い

Chandra&Touegの合意問題では、全てのプロセスが合意処理が始まるときに提案する

ための値（以下、初期値と呼ぶ）を計算する。これは、プロセスの計算処理コストを多く 消費する。一方、Lazy consensusでは、プロセスの計算処理コストを低くするためにコー ディネータープロセスだけが初期値を計算する。次に、故障が発生した場合の２つの合意 問題の操作について考える。Chandra&Touegの合意問題では、コーディネーターリスト により、合意処理の各ラウンドでの唯一のコーディネーターを決定している。しかし、こ のコーディネーターリストのプロセスの構成順序は、いつも同じである。もし、連続した 合意処理が発生した場合に、コーディネータリストの1番目にあるプロセスが故障してい ると仮定する。毎回の合意処理において、ラウンド２以降でしか、合意処理は終了しな い。つまり、最初ののラウンドは無駄なのである。この無駄を省くためにLazy consensus では、毎回の合意実行のラウンド１で合意問題を終了させるために、値の合意処理を行 うさいに、次の合意実行のためのコーディネータリストの合意も行っている（以下、この コーディネータリストのことをPVと呼ぶ）。¹

表4.1の中の、プロセス数の部分で１つとは、コーディネータープロセスだけを指し、

全てとは、合意問題に参加する全てのプロセスを指す。

4.3 Neko について

Nekoは、P.Urb´anらによって開発された分散アルゴリズム実装のためのプラットホーム である。Nekoは次の場所で手にいれることができる。

http://lsrwww.epfl.ch/neko/

図4.7は、Nekoの環境を簡単に表したものである。図4.7を見ると分かるようにNeko は、実装した分散アルゴリズムを使ってシミュレーション実行、実ネットワーク実行の２ つの評価環境で実装した分散アルゴリズムの性能評価が行うことができる。

図4.7: Nekoについて

また、Nekoの中には、分散アルゴリズムを実装するときに役に立つ豊富コンポーネン トが揃っている。第３章で説明した複製技術を実装するときに必要な合意問題に関する コンポーネントや、Faliure detector, Reliable broadcastなども揃っている。これらの、メ リットは一人で分散アルゴリズムを実装するときには、時間もしくは、労力を軽減するこ

ン実行できるので、もし、分散あリゴリズムを実装しているプログラムに間違いがある 場合には、すぐに変更できる。今回、このNekoを使って複製技術を実装したことで、分 散アルゴリズムを実装するときに何が大切なのかということを経験した。それは、ただ、

本で複製技術の概念を理解しているときには、わからなかったことである。Semi-passive

replicationのコンポーネント実装を通して感じたことは、Nekoは、分散アルゴリズムを実

装するには、大変便利なプラットホームである。それは、単に分散アルゴリズムを実装す るときに役に立つコンポーネントが豊富にあるだけではない。Nekoの中にあるコンポー ネント実装したjavaプログラムを読むことで、アルゴリズムと実装プログラムの違いが 発見できる。この発見したことを通して、アルゴリズムとプログラムのギャップを埋めた プログラムを勉強できる。また、nekoのシミュレーション機能が、プログラム開発環境 においてはもっとも役に立ったと思う。