English

共有メモリ分散システムのための分散アルゴリズム

複数の非同期プロセスとそれらに共有されるレジスタ群からなる共有メモリ分散システムのための 効率のよい分散アルゴリズムを研究しています。

分散アルゴリズムの性能は、アルゴリズムが終了するまでに各プロセスが共有レジスタにアクセスする回数(プロセスステップ計算量)や 全プロセスが共有レジスタにアクセスする回数(総ステップ計算量)などで評価します。 分散アルゴリズムの性能は、プロセスが動作するタイミングや共有レジスタのタイプなどに依存します。そこで、分散アルゴリズムの研究では、 プロセスが動作するタイミングに様々な仮定を設けて、それぞれの仮定の下で性能が評価されます。

プロセスの動作のタイミングに関する仮定には以下のようなものがあります。すべてのプロセスの実行速度が既知の定数で、 すべての局所時計が同期しているシステムを同期システムといい、同期システムでないシステムを非同期システムといいます。 あるプロセスが、プロセス内部の局所命令または共有メモリへの操作を実行しようとしたときに、有限時間内にその実行を行うことができるとき、 システムは公平であるといいます。

プロセスが実行を行う順序を決める仕組みをデーモン敵対スケジューラという抽象化した概念を用いて表します。 次に実行を行うプロセスを選択するスケジューラで、同時に高々1個のプロセスを選択するデーモンをC-デーモン、 複数のプロセスに同時実行を許すデーモンをD-デーモンと呼びます。敵対スケジューラは、スケジューラが知りうる情報により 分類され、アダプティブ敵対スケジューラは、全プロセスの内部状態や全共有メモリの値を知る最強のスケジューラであり、 分散アルゴリズムの最悪の場合の性能を評価するときに用いられます。対照的に、オブリビアススケジューラは、プロセスの内部状態や共有メモリの 値を利用しないスケジューラであり、分散アルゴリズムの平均的な性能を評価するのに用いられます。

共有メモリ分散システムでは、いくつかのタイプの共有レジスタが用いられます。 レジスタのタイプは、そのレジスタから値を読むことができるプロセス (reader) とそのレジスタに値を書くことのできるプロセス (writer) の個数によって分類されます。

共有メモリ分散システム

あるプロセスiの情報を2つのプロセスj,k に知らせるには、SRSWレジスタでは、jがreaderのレジスタとkがreaderのレジスタに値を書き込む必要がありますが、 MRSWレジスタを用いると、jもkも同じレジスタを読み出せば値を知ることができます。このように、レジスタのタイプは分散アルゴリズムの性能に大きく影響します。

プロセスiがある値vをプロセスjに伝えるには、プロセスiが値をvをあるレジスタRに書き込んだ後に、 プロセスjがレジスタRを読み出す必要があり、 プロセスの動作のタイミングによっては値を伝えることができません。 すなわり、同じアルゴリズムの実行であっても、プロセスの動作のタイミングによって進行状況が異なります。 分散アルゴリズムは、デーモンの仮定の範囲で、どのような場合も正しく動作することが求められます。

ディペンダブルシステム学研究室での取り組みについて

本研究室では、オブリビアス敵対スケジューラ下でのMRSWレジスタを用いた分散アルゴリズムを提案しています。

中島 悟, 井上 美智子,”オブリビアス敵対スケジューラ下でのMRSWレジスタを用いた乱択合意アルゴリズム ,” 信学技報, Vol. 113, No. 488, COMP2013-68, pp.53-60, Mar. 2014.

分散システム上で、全ての正常プロセスが同じ値で合意する問題は合意問題と呼ばれ、 分散アルゴリズムの基本問題としてよく研究されています。合意問題とは、各プロセスがそれぞれ初期値を持ち、 以下を満たす合意値を出力する問題です。

合意問題は、分散システムが非同期である場合、1つでも故障プロセスが存在すると 解くことができないことが知られています[1][2]。そこで、プロセスが故障して何も動作しなくなっても、 正常プロセスには停止性を確率的に保証する乱択合意問題が 考えられています。

要するに、乱択合意問題とは、いずれかのプロセスの初期値で全正常プロセスが合意に至る問題で、 プロセスが実行し続ければ、停止する確率が1に近づくことを保証する問題です。以下の図は、入力として 各プロセスが初期値54, 3, …, 100を持ち、出力値100で合意する例です。

乱択合意問題

乱択合意問題

乱択合意問題は共有メモリ分散システムにおいて、様々なレジスタや敵対スケジューラのタイプに対して研究されてます。 以下の表に、主な既存の結果と本研究室での成果(「本論文」)を示します。nはシステム内の総プロセス数です。 問題の種類の「2値」は初期値が0と1の2値だけであること、「m値」は初期値がm種類あることを表します。 プロセスステップ計算量は、各プロセスが合意値を出力するまでに共有メモリへアクセスする回数の期待値、 総ステップ計算量は、全プロセスが合意値を出力するまでに共有メモリへアクセスする回数の期待値です。 乱択アルゴリズムは、必ず停止することは保証されていませんが、ステップ数を期待値で評価することは可能です。

乱択合意アルゴリズムの既知の結果と本研究での結果

さて、いろんな問題の設定、レジスタ、敵対スケジューラでアルゴリズムが提案されていると、 どのアルゴリズムがよいのか比較が難しくなります。そこで、表の右側には、MRSWレジスタを用いて m値の乱択合意問題を解いた場合の計算量を示しています。 詳細は論文を読んでほしいですが、 m値の乱択合意問題は、2値の乱択合意アルゴリズムを道具にして解くことができるし、 また、MRMWレジスタはMRSWレジスタを用いてシミュレートすることができるので、 このような換算が可能になっています。アダプティブ敵対スケジューラは、なんでも知っている敵対スケジューラ、つまり、 アルゴリズムが終わらないようにプロセスを選択するスケジューラですので、他のスケジューラに比べて計算量は悪くなります。 オブリビアスは、システムの状態をまったく知らない敵対スケジューラで計算量は他のスケジューラよりよくなることが期待できます。 ロケーションオブリビアス、コンテンツオブリビアスは、アダプティブとオブリビアスの間の能力を持つ スケジューラです。

表のMRSWレジスタモデル上でm値の乱択合意問題を解く場合のプロセスステップ計算量をみると、 「本論文」の計算量が一番良いことがわかります。これをどうやって導き出したかは長い話になるので、 ぜひ論文を読んでみてください。表はオーダーでの表記なので、本当に効率の良いアルゴリズムか 気になる人もいるかもしれません。下の図は、計算機シミュレーションによる既知の結果[5]と比較です。 プロセス数を2048として、 プロセスの動作タイミングを変えて3000回アルゴリズムの実行を試行した平均の総ステップ計算量を示しています。 横軸は合意確率、つまり、合意に至ったプロセスの割合です。本研究で提案するアルゴリズムの方が、100%の合意に達するには約3/8の ステップ数で済むなど、少ない総ステップ計算量で合意に至ることがわかります。

総ステップ計算量(プロセス数2048)

総ステップ計算量(プロセス数2048)

参考文献

[1] Michael J. Fischer, Nancy A, Lynch, and Michael S. Paterson, ”Impossibility of distributed consensus with one faulty process,” J.ACM, 32(2):374.382, April 1985.
[2] Murice Herlihy, ”Wait-Free Synchronization,” ACM Transactions on Programming Languages and Systems, Vol.11, No 1, January 1991.
[3] Hagit Attiya, Keren Censor, ”Tight bounds for asynchronous randomized consensus,” J.ACM, 55(5):20, October 2008.
[4] James Aspnes, Keren Censor, ”Approximate shared-memory counting despite a strong adversary,” TALG, Vol.6, No.25, 2010.
[5] James Aspnes, ”Faster randomized consensus with an oblivious adversary,” PODC 2012, pages 1.8, July 2012.
[8] James Aspnes, ”A modular approach to shared-memory consensus, with applications to the probabilistic-write model,” Distributed Computing, 25(2):179.188, May 2012.
[9] James Aspnes, Faith Ellen, ”Tight bounds for anonymous adoptcommit objects,” Proceedings of 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, pages 317.324, 2011.
[11] James Aspnes, ”Lower bounds for distributed coin-flipping and randomized consensus,” Journal of the ACM, 45(3):415.450, May 1998.