たとえば、キー値ストアの更新で更新の競合があるかどうかを判断するのに十分な情報を提供できないスカラー論理クロックの観点から、ベクトル クロックの必要性を理解しています。
しかし、どの問題がまだベクトル クロックによって解決されておらず、よりかさばるマトリックス クロックによって解決されているのかわかりません。
2668 次
2 に答える
5
結果整合性環境では、システムによって作成されたすべてのメッセージは、すべてのピアがメッセージを受信するまで保持する必要があります (== 結果整合性)。しかし、メッセージを永遠に保持したくないので、どのメッセージがすべてのノードで受信され、削除できるかを知る方法が必要です。これがマトリックスクロックを使用する理由です。
マトリックス クロックはベクトル クロックのリストであるため、システム内の各ノードの現在の状態がわかります。これに基づいて、どのピアがどのメッセージをすでに受信したかを知ることができます。システム内の別のノードとメッセージを交換するときは、マトリックス クロックを比較し、各ノードの最高値を常に記憶します。ノードはすでにメッセージを受信している必要があるため、以前に送信されたメッセージを後で削除できます。
これは、TSAE (タイムスタンプ付きアンチエントロピー) プロトコルの非常に簡単な説明です。これについては、1992 年に Richard Andrew Golding が執筆した論文プロジェクト Weak-consistency group communication and members で詳しく読むことができます ( http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.7385&rep=rep1&type= pdf ) 第 5 章から開始します。
于 2014-01-28T01:48:04.400 に答える
4
ランポート クロック (あなたの用語では、スカラー論理クロック)、ベクトル クロック、およびマトリックス クロックの違いは、それらが異なるレベルの知識を表すことにあります。
サイト $i$ のベクトル クロック $vt_i[1 \ldots n]$ のエントリ $vt_i[k]$ は、サイト $S_i$ がサイト $S_k$ について持っている知識を表します。知識は、「$i$ は、$\ldots$ という $k$ を知っている」という形をしています。
サイト $S_i$ のマトリックス クロック $mt_i[1 \ldots n, 1 \ldots n]$ の場合、エントリ $mt_i[k,l]$ は、サイト $S_i$ が $S_k$ の知識について持っている知識を表します。サイト $S_l$。ここでの知識は、「$i$ が $k$ を知っている $l$ を $\ldots$ を知っている」という形式です。
直感的に、より多くの知識があれば、より多くのことを行うことができます。
以下の説明は、主に [1] から引用されています。
ベクトル クロックとマトリックス クロックは、非同期分散メッセージ パッシング システムで広く使用されています。
ベクトル クロックを使用する領域の例としては、チェックポイント、原因メモリ、レプリケートされたファイルの一貫性の維持、グローバル スナップショット、グローバル時間の概算、終了検出、共有変数の制限付きマルチライター構築、相互排除、およびデバッグ (述語検出) があります。
マトリックス クロックを使用する領域の例として、フォールト トレラント プロトコルと分散データベース プロトコルの設計があります。これには、分散データベース内の古い情報を破棄するプロトコルや、複製されたログと複製された辞書の問題を解決するためのプロトコルが含まれます。
マトリックス クロックの場合、$min_k(mt_i[k,i]) \get$ は、サイト $S_i$ が、他のすべてのサイト $k$ がその現地時間 $t$ までの進行状況を知っていることを知っていることを意味します。
サイトがローカル タイム $\le t$ を持つ情報を送信しないようにしたり、古い情報を破棄したりできるようにするのは、このプロパティです。
于 2014-08-10T11:41:52.523 に答える