バージョンベクトル

バージョンベクトルは、分散システムにおいて複数のエージェントが異なるタイミングでデータを更新する場合、データの変更を追跡するためのメカニズムです。バージョンベクトルによって、参加者はある更新が別の更新より先に発生したのか（先行）、後に発生したのか、あるいは2つの更新が同時に発生したのか（したがって互いに競合する可能性があるのか​​）を判断できます。このように、バージョンベクトルはデータレプリカ間の因果関係の追跡を可能にし、楽観的レプリケーションの基本的なメカニズムとなります。数学的に言えば、バージョンベクトルは、後続の更新に先行し、影響を与える可能性のあるイベントを追跡する順序関係を生成します。

バージョンベクトルはベクトルクロックと同じ状態を維持しますが、更新ルールが若干異なります。この例では、レプリカはローカル更新（たとえば、ユーザーがローカルノードでファイルを編集する）を受けるか、別のレプリカと同期することができます。

• 初期状態では、すべてのベクトルカウンタはゼロです。
• レプリカがローカル更新イベントを経験するたびに、ベクター内の自身のカウンターを1つ増やします。
• 2つのレプリカaとbが同期するたびに、両者はそれぞれのコピーのベクトル内の要素を、両方のカウンタにおける要素の最大値に設定します。 ${\displaystyle V_{a}[x]=V_{b}[x]=\max(V_{a}[x],V_{b}[x])}$同期後、2つのレプリカは同一のバージョンベクトルを持つ。

レプリカのペアa、bは、バージョンベクトルを検査して比較し、以下のいずれかであると判断できます。同一 (${\displaystyle a=b}$）、同時（${\displaystyle a\parallel b}$)、または注文した (${\displaystyle a<b}$または${\displaystyle b<a}$) 順序関係は次のように定義されます: ベクトル${\displaystyle a<b}$すべての要素が${\displaystyle V_{a}}$対応する要素以下である${\displaystyle V_{b}}$、かつ、少なくとも１つの要素が厳密により小さい。どちらも${\displaystyle a<b}$または${\displaystyle b<a}$しかし、ベクトルが同一でない場合、2つのベクトルは一点で交わらなければならない。

バージョンベクトル^{[ 1 ]}またはバリアントは、Coda（ファイルシステム）やFicusなどの多くの分散ファイルシステムで更新を追跡するために使用され 、楽観的レプリケーションの背後にある主要なデータ構造です。^{[ 2 ]}

• ハッシュ履歴^{[ 3 ]}は、更新された各バージョンのハッシュのセットを保持し、それらのセットをセット包含によって比較することで、カウンターの使用を回避します。ただし、このメカニズムは確率的な保証しか提供できません。
• 簡潔バージョンベクトル^{[ 4 ]}は、ファイルシステムのディレクトリ構造など、複数の複製されたアイテムを処理する際に、大幅なスペース節約を可能にします。
• バージョンスタンプ^{[ 5 ]}は可変数のレプリカの追跡を可能にし、カウンターに頼ることはありません。このメカニズムは一部の設定でスケーラビリティの問題を示す可能性がありますが、インターバルツリークロックに置き換えることができます。
• インターバルツリークロック^{[ 6 ]}はバージョンベクトルとベクトルクロックを一般化し、レプリカ/プロセスの動的な数を可能にします。
• 制限付きバージョンベクトル ^{[ 7 ]}は、レプリカペアがアトミックに同期できる限り、制限付きサイズカウンタを備えた制限付き実装を可能にします。
• ドットバージョンベクトル^{[ 8 ]}は、多数の同時クライアントによるレプリカアクセスを仲介する少数のサーバーでスケーラビリティに対応します。

• 論理クロックが簡単な理由（因果履歴、ベクトルクロック、バージョンベクトルの比較）