タイムワープアルゴリズム

昨日の日記で、タイムワープアルゴリズムのことを楽観的ロックと書きましたが、違うようです。今日、「コンピュータプログラムの概念・技法・モデル」(ガウディ本)をようやく買うことが出来て、ちょっと関係するところを読んでみました。残念がながらタイムワープアルゴリズムについては書いていないのですが、並列性制御の方法として、ロックとタイムスタンプがあると書かれていて(P618)、タイムワープアルゴリズムはタイムスタンプベースの並列性制御といえそうです。

Googleでタイムワープアルゴリズムを調べてもタイムワープアルゴリズムを解説したページが見つかりませんでした。昔学校で習ったきり復習もしていないし、資料も持っていないので*1、記憶が曖昧です。そこで、自分の確認も兼ねてここにアルゴリズムの概要を書いてみたいと思います。多分間違えが一杯と思いますので、突っ込みたくなったら、どうか遠慮なく突っ込んでください。

何をするアルゴリズム？

分散システムで使うアルゴリズムです。たくさんのコンピュータがネットワークでつながっていて１つの仕事をするという感じのシステムが対象になります。仕事としては、主に分散シミュレーションが多いのですが、コンピュータで行う仕事は結局はシミュレーションなわけなんで、汎用性は十分あると思います。
タイムワープアルゴリズムは前に書いたように並列性制御のアルゴリズムです。たくさんのコンピュータが１つの仕事をすると当然足並みをそろえる必要があるわけですが、その足並みをそろえるアルゴリズムです。その足並みのそろえ方が結構すごいです。

具体的にどうするのか

1. 各コンピュータにそれぞれ固有の時間(クロック)を持たせます。この時間は何か仕事をするたびにちょこちょこ進めていきます。
2. コンピュータ間はメッセージによって通信します。メッセージには送信するコンピュータの時間をタイムスタンプとして含めておきます。
3. メッセージのやり取りが無いうちは他のコンピュータの事は考えず好き勝手に仕事を進めていきます。
4. もし、メッセージを受信したとき含まれているタイムスタンプが受信したコンピュータの時間より古い場合は、タイムスタンプの時間から今までの処理は全部無かったことにします。もし、他のコンピュータにメッセージを送ってしまった場合はキャンセルしてねというメッセージを送ってそれも無かったことにします。
5. こんなことが出来るためには、古い状態も全部取っておかなければなりません。
6. でも、永久に全部取っておく必要は無いです。すべてのコンピュータのうち一番古い時間より前の状態は当然取っておかなくてもよいです。古い状態を破棄してメモリを節約することを化石採集(Fossil collection)というようです。
7. では一番古い時間ってのはどうやて求めるかというと・・・、結構面倒なのですが出来ます。いろいろやり方が提唱されています。

効率悪そー

効率悪そーってはじめ聞いたときは思ったのですが、ある程度の規模になると回りに気を使って時間を進めるような方針のアルゴリズムよりすごーく効率がいいようです。

*1:確か「モデルと表現」に載っていたと思います。今は絶版のようなので、図書館とかで読める人は是非読んでみてください。