ベクトルクロック

ベクタークロックは、分散システム内のイベントの部分的な順序付けを決定し、因果関係違反を検出するために使用されるデータ構造です。Lamportタイムスタンプと同様に、プロセス間メッセージには送信プロセスの論理クロックの状態が含まれます。N個のプロセスからなるシステムのベクトルクロックは、プロセスごとに 1 つのクロック、 N 個の論理クロックの配列/ベクトルです。各プロセスには、グローバルクロック配列のローカルな「最大値」のコピーが保持されます。

プロセスによって維持されるベクトルクロックをと表記すると、クロックの更新は次のように進行します。^[1] $VC_{i}$ $i$

最初はすべてのクロックはゼロです。
プロセスが内部イベントを経験するたびに、ベクター内の独自の論理クロックが 1 ずつ増加します。たとえば、プロセスでイベントが発生すると、が更新されます。 $i$ $VC_{i}[i]\leftarrow VC_{i}[i]+1$
プロセスがメッセージを送信するたびに、ベクター内の独自の論理クロックが 1 つ増加します (上記の箇条書きと同じですが、同じイベントに対して 2 回ではありません)。次に、メッセージを独自のベクターのコピーとペアにして、最後にそのペアを送信します。
プロセスは、メッセージとベクトルのクロックのペアを受信するたびに、ベクトル内の自身の論理クロックを 1 ずつ増加し、自身のベクトルクロックの値と受信したペアのベクトルの値 (各要素について) の最大値を取得して、ベクトル内の各要素を更新します。たとえば、プロセスがからメッセージを受信すると、まずベクトル内の自身の論理クロックを 1 ずつ増加し、次にを設定してベクトル全体を更新します。 $P_{i}$ $(m,VC_{j})$ $P_{j}$ $VC_{i}[i]\leftarrow VC_{i}[i]+1$ $VC_{i}[k]\leftarrow \max(VC_{i}[k],VC_{j}[k]),\forall k$

歴史

ラムポートは1978 年に論理ラムポートクロックのアイデアを考案しました。^[2]しかし、その論文の論理クロックはスカラーであり、ベクトルではありませんでした。ベクトル時間への一般化は、1980 年代初頭に、明らかに独立して、異なる著者によって数回開発されました。^[3]少なくとも 6 つの論文にこの概念が含まれています。 ^[4]ベクトルクロックの参照として標準的に引用されている論文は、コリンフィッジとフリーデマンマターンの 1988 年の著作です。 ^[5]^[6]これらの論文は、(独立して)「ベクトルクロック」という名前とベクトルクロックの数学的特性を確立しました。^[3]

部分順序プロパティ

ベクトルクロックを使用すると、イベントの部分的な因果順序付けが可能になります。以下を定義します。

$VC(x)$ はイベントのベクトルクロックを表し、はプロセスのそのクロックの成分を表します。 $x$ $VC(x)_{z}$ $z$
$VC(x)<VC(y)\iff \forall z[VC(x)_{z}\leq VC(y)_{z}]\land \exists z'[VC(x)_{z'}}$ $VC(x)<VC(y)\iff \forall z[VC(x)_{z}\leq VC(y)_{z}]\land \exists z'[VC(x)_{z'}}$
- はより小さく、すべてのプロセスインデックスに対してが以下であり、それらの関係の少なくとも 1 つがより小さい場合（つまり）に限ります。 $VC(x)$ $VC(y)$ $VC(x)_{z}$ $VC(y)_{z}$ $z$ $VC(x)_{z'}<VC(y)_{z'}$
$x\to y\;$ は、イベントの前にイベントが発生したことを示します。これは次のように定義されます。 $x$ $y$ $x\to y\;$ $VC(x)<VC(y)$

プロパティ:

反対称性:ならば、¬ $VC(a)<VC(b)$ $(VC(b)<VC(a))$
推移性: かつならば、または、かつならば $VC(a)<VC(b)$ $VC(b)<VC(c)$ $VC(a)<VC(c)$ $a\to b\;$ $b\to c\;$ $a\to c\;$

他の注文との関係:

をイベントが発生した実際の時間とします。の場合、 $RT(x)$ $x$ $VC(a)<VC(b)$ $RT(a)<RT(b)$
をイベントのLamportタイムスタンプとします。の場合、 $C(x)$ $x$ $VC(a)<VC(b)$ $C(a)<C(b)$

その他のメカニズム

1999年に、Torres-RojasとAhamadはPlausible Clocks [ ^7]を開発しました。これはベクトルクロックよりもスペースをとらないメカニズムですが、場合によっては因果的に同時発生するイベントを完全に順序付けます。

2005年に、AgarwalとGargはChain Clocks ^[8]を開発しました。これは、プロセス数よりも小さいサイズのベクトルを使用して依存関係を追跡し、プロセス数が動的に変化するシステムに自動的に適応するシステムです。
2008年に、AlmeidaらはInterval Tree Clocksを導入しました。^[9]^[10]^[11]このメカニズムはVector Clocksを一般化し、計算におけるプロセスのIDと数が事前にわからない動的環境での動作を可能にします。

2019年、Lum Ramabajaはブルームフィルタに基づく確率的データ構造であるブルームクロックを提案した。^[12]^[13]^[14]ベクトルクロックと比較すると、ノードあたりの使用スペースは固定されており、システム内のノード数に依存しない。2つのクロックを比較すると、真陰性（クロックは比較できない）になるか、一方のクロックが他方のクロックに先行していることが示唆され、2つのクロックに関連がない場合には偽陽性の可能性がある。許可されるストレージが増えるにつれて、偽陽性率は低下する。

参照

参考文献

^ 「分散システム第3版（2017年）」DISTRIBUTED-SYSTEMS.NET 。 2021年3月21日閲覧。
^ Lamport, L. (1978). 「分散システムにおける時間、クロック、およびイベントの順序付け」(PDF) . Communications of the ACM . 21 (7): 558–565. doi :10.1145/359545.359563. S2CID 215822405.
^ ab Schwarz , Reinhard ; Mattern, Friedemann (1994年3 月)。「分散コンピューティングにおける因果関係の検出: 聖杯の探求」。分散コンピューティング。7 (3): 149–174。doi :10.1007/BF02277859。S2CID 3065996。
^ Kuper, Lindsey (2023年4月8日). 「ベクトルクロックを発明したのは誰か?」. decomposition ∘ al .
論文は以下のとおりです（時系列順）：
- Fischer, Michael J.; Michael, Alan (1982)。「信頼性の低いネットワークでデータの高可用性を実現するために直列化可能性を犠牲にする」。データベースシステムの原理に関する第 1 回 ACM SIGACT-SIGMOD シンポジウム議事録 - PODS '82。p. 70。doi : 10.1145 / 588111.588124。ISBN 0897910702. S2CID 8774876。
- Parker, DS; Popek, GJ; Rudisin, G.; Stoughton, A.; Walker, BJ; Walton, E.; Chow, JM; Edwards, D.; Kiser, S.; Kline, C. (1983 年 5 月)。「分散システムにおける相互不整合の検出」。IEEE Transactions on Software Engineering。SE - 9 ( 3): 240–247。doi : 10.1109 /TSE.1983.236733。S2CID 2483222。
- Wuu, Gene TJ; Bernstein, Arthur J. (1984)。「複製ログと辞書の問題に対する効率的な解決法」。分散コンピューティングの原理に関する第 3 回 ACM シンポジウム議事録 - PODC '84。pp. 233–242。doi :10.1145/800222.806750。ISBN 0897911431. S2CID 2384672。
- Strom, Rob; Yemini, Shaula (1985 年 8 月)。「分散システムにおける楽観的回復」。ACM Transactions on Computer Systems。3 ( 3): 204–226。doi : 10.1145/ 3959.3962。S2CID 1941122 。
- Schmuck, Frank B. (1985 年 11 月)。ソフトウェアクロックと分散システムにおけるイベントの順序(未発表)。
- Liskov, Barbara; Ladin, Rivka (1986)。「高可用性分散サービスとフォールトトレラント分散ガベージコレクション」。第 5 回 ACM シンポジウム「分散コンピューティングの原理」の議事録 - PODC '86。pp. 29–39。doi : 10.1145 / 10590.10593。ISBN 0897911989. S2CID 16148617。
- Raynal, Michel (1987年2 月)。「n 個の論理クロック間の相互ドリフトを防ぐ分散アルゴリズム」。Information Processing Letters。24 ( 3): 199–202。doi :10.1016/0020-0190(87)90186-4。
^ Fidge, Colin J. (1988 年 2 月)。「部分的な順序を保持するメッセージパッシングシステムのタイムスタンプ」(PDF)。K. Raymond (編)。第 11 回オーストラリアコンピュータサイエンスカンファレンス (ACSC'88) の議事録。第 10 巻。pp. 56–66。2009年 2 月 13 日閲覧。
^ Mattern, Friedemann (1988 年 10 月)。「分散システムの仮想時間とグローバル状態」。Cosnard, M. (編)。並列および分散アルゴリズムに関するワークショップ議事録。Chateau de Bonas、フランス: Elsevier。pp. 215–226。
^ Francisco Torres-Rojas、Mustaque Ahamad (1999)、「妥当なクロック: 分散システム用の一定サイズの論理クロック」、Distributed Computing、12 (4): 179–195、doi :10.1007/s004460050065、S2CID 2936350
^ Agarwal, Anurag; Garg, Vijay K. (2005 年 7 月 17 日)。「共有メモリシステムにおける関連イベントの効率的な依存関係追跡」( PDF)。第 24 回 ACM シンポジウム「分散コンピューティングの原理」の議事録。Association for Computing Machinery。pp. 19–28。doi : 10.1145 /1073814.1073818。ISBN 1-58113-994-2. S2CID 11779779 . 2021年4月21日閲覧。
^ Almeida, Paulo; Baquero, Carlos; Fonte, Victor (2008)、「Interval Tree Clocks: A Logical Clock for Dynamic Systems」、Baker, Theodore P.; Bui, Alain; Tixeuil, Sébastien (eds.)、Principles of Distributed Systems (PDF)、Lecture Notes in Computer Science、vol. 5401、Springer-Verlag、Lecture Notes in Computer Science、pp. 259–274、Bibcode :2008LNCS.5401.....B、doi :10.1007/978-3-540-92221-6、ISBN 978-3-540-92220-9
^ Almeida, Paulo; Baquero, Carlos; Fonte, Victor (2008)、「Interval Tree Clocks: A Logical Clock for Dynamic Systems」、Lecture Notes in Computer Science、vol. 5401、p. 259、doi :10.1007/978-3-540-92221-6_18、hdl : 1822/37748、ISBN 978-3-540-92220-9
^ Zhang, Yi (2014)、「背景予備調査: 間隔木クロックの結果」、背景予備調査: 間隔木クロックの結果(PDF)
^ Pozzetti, Tommaso; Kshemkalyani, Ajay D. (2021年4月1日). 「因果関係分析のためのリセット可能なエンコードされたベクトルクロックと動的競合検出への応用」. IEEE Transactions on Parallel and Distributed Systems . 32 (4): 772–785. doi : 10.1109/TPDS.2020.3032293 . S2CID 220362525.
^ Lum Ramabaja (2019)、The Bloom Clock、arXiv : 1905.13064、Bibcode :2019arXiv190513064R
^ Kulkarni, Sandeep S; Appleton, Gabe; Nguyen, Duong (2022年1月4日 ) 。「物理クロックによる因果関係の実現」。第23回国際分散コンピューティングおよびネットワーク会議の議事録。pp. 97–106。arXiv : 2104.15099。doi : 10.1145 / 3491003.3491009。ISBN 9781450395601. S2CID 233476293。

外部リンク

論理クロックが簡単な理由 (因果履歴、ベクトルクロック、バージョンベクトルを比較)
ベクトルクロックの説明
Erlang でのタイムスタンプベースのベクトルクロックの実装
Objective-C でのベクタークロックの実装
Erlang でのベクトルクロックの実装
ベクトルクロックが難しい理由
Cassandra にベクタークロックが必要ない理由

[1] 「分散システム第3版（2017年）」DISTRIBUTED-SYSTEMS.NET 。 2021年3月21日閲覧。

[Lamport_1978-2] Lamport, L. (1978). 「分散システムにおける時間、クロック、およびイベントの順序付け」(PDF) . Communications of the ACM . 21 (7): 558–565. doi :10.1145/359545.359563. S2CID 215822405.

[Schwarz-3] Schwarz , Reinhard ; Mattern, Friedemann (1994年3 月)。「分散コンピューティングにおける因果関係の検出: 聖杯の探求」。分散コンピューティング。7 (3): 149–174。doi :10.1007/BF02277859。S2CID 3065996。

[4] Kuper, Lindsey (2023年4月8日). 「ベクトルクロックを発明したのは誰か?」. decomposition ∘ al .論文は以下のとおりです（時系列順）：
Fischer, Michael J.; Michael, Alan (1982)。「信頼性の低いネットワークでデータの高可用性を実現するために直列化可能性を犠牲にする」。データベースシステムの原理に関する第 1 回 ACM SIGACT-SIGMOD シンポジウム議事録 - PODS '82。p. 70。doi : 10.1145 / 588111.588124。ISBN 0897910702. S2CID 8774876。

Parker, DS; Popek, GJ; Rudisin, G.; Stoughton, A.; Walker, BJ; Walton, E.; Chow, JM; Edwards, D.; Kiser, S.; Kline, C. (1983 年 5 月)。「分散システムにおける相互不整合の検出」。IEEE Transactions on Software Engineering。SE - 9 ( 3): 240–247。doi : 10.1109 /TSE.1983.236733。S2CID 2483222。

Wuu, Gene TJ; Bernstein, Arthur J. (1984)。「複製ログと辞書の問題に対する効率的な解決法」。分散コンピューティングの原理に関する第 3 回 ACM シンポジウム議事録 - PODC '84。pp. 233–242。doi :10.1145/800222.806750。ISBN 0897911431. S2CID 2384672。

Strom, Rob; Yemini, Shaula (1985 年 8 月)。「分散システムにおける楽観的回復」。ACM Transactions on Computer Systems。3 ( 3): 204–226。doi : 10.1145/ 3959.3962。S2CID 1941122 。

Schmuck, Frank B. (1985 年 11 月)。ソフトウェアクロックと分散システムにおけるイベントの順序(未発表)。

Liskov, Barbara; Ladin, Rivka (1986)。「高可用性分散サービスとフォールトトレラント分散ガベージコレクション」。第 5 回 ACM シンポジウム「分散コンピューティングの原理」の議事録 - PODC '86。pp. 29–39。doi : 10.1145 / 10590.10593。ISBN 0897911989. S2CID 16148617。

Raynal, Michel (1987年2 月)。「n 個の論理クロック間の相互ドリフトを防ぐ分散アルゴリズム」。Information Processing Letters。24 ( 3): 199–202。doi :10.1016/0020-0190(87)90186-4。

[5] Fischer, Michael J.; Michael, Alan (1982)。「信頼性の低いネットワークでデータの高可用性を実現するために直列化可能性を犠牲にする」。データベースシステムの原理に関する第 1 回 ACM SIGACT-SIGMOD シンポジウム議事録 - PODS '82。p. 70。doi : 10.1145 / 588111.588124。ISBN 0897910702. S2CID 8774876。

[6] Parker, DS; Popek, GJ; Rudisin, G.; Stoughton, A.; Walker, BJ; Walton, E.; Chow, JM; Edwards, D.; Kiser, S.; Kline, C. (1983 年 5 月)。「分散システムにおける相互不整合の検出」。IEEE Transactions on Software Engineering。SE - 9 ( 3): 240–247。doi : 10.1109 /TSE.1983.236733。S2CID 2483222。

[7] Wuu, Gene TJ; Bernstein, Arthur J. (1984)。「複製ログと辞書の問題に対する効率的な解決法」。分散コンピューティングの原理に関する第 3 回 ACM シンポジウム議事録 - PODC '84。pp. 233–242。doi :10.1145/800222.806750。ISBN 0897911431. S2CID 2384672。

[8] Strom, Rob; Yemini, Shaula (1985 年 8 月)。「分散システムにおける楽観的回復」。ACM Transactions on Computer Systems。3 ( 3): 204–226。doi : 10.1145/ 3959.3962。S2CID 1941122 。

[9] Schmuck, Frank B. (1985 年 11 月)。ソフトウェアクロックと分散システムにおけるイベントの順序(未発表)。

[10] Liskov, Barbara; Ladin, Rivka (1986)。「高可用性分散サービスとフォールトトレラント分散ガベージコレクション」。第 5 回 ACM シンポジウム「分散コンピューティングの原理」の議事録 - PODC '86。pp. 29–39。doi : 10.1145 / 10590.10593。ISBN 0897911989. S2CID 16148617。

[11] Raynal, Michel (1987年2 月)。「n 個の論理クロック間の相互ドリフトを防ぐ分散アルゴリズム」。Information Processing Letters。24 ( 3): 199–202。doi :10.1016/0020-0190(87)90186-4。

[5] Fidge, Colin J. (1988 年 2 月)。「部分的な順序を保持するメッセージパッシングシステムのタイムスタンプ」(PDF)。K. Raymond (編)。第 11 回オーストラリアコンピュータサイエンスカンファレンス (ACSC'88) の議事録。第 10 巻。pp. 56–66。2009年 2 月 13 日閲覧。

[6] Mattern, Friedemann (1988 年 10 月)。「分散システムの仮想時間とグローバル状態」。Cosnard, M. (編)。並列および分散アルゴリズムに関するワークショップ議事録。Chateau de Bonas、フランス: Elsevier。pp. 215–226。

[7] Francisco Torres-Rojas、Mustaque Ahamad (1999)、「妥当なクロック: 分散システム用の一定サイズの論理クロック」、Distributed Computing、12 (4): 179–195、doi :10.1007/s004460050065、S2CID 2936350

[8] Agarwal, Anurag; Garg, Vijay K. (2005 年 7 月 17 日)。「共有メモリシステムにおける関連イベントの効率的な依存関係追跡」( PDF)。第 24 回 ACM シンポジウム「分散コンピューティングの原理」の議事録。Association for Computing Machinery。pp. 19–28。doi : 10.1145 /1073814.1073818。ISBN 1-58113-994-2. S2CID 11779779 . 2021年4月21日閲覧。

[9] Almeida, Paulo; Baquero, Carlos; Fonte, Victor (2008)、「Interval Tree Clocks: A Logical Clock for Dynamic Systems」、Baker, Theodore P.; Bui, Alain; Tixeuil, Sébastien (eds.)、Principles of Distributed Systems (PDF)、Lecture Notes in Computer Science、vol. 5401、Springer-Verlag、Lecture Notes in Computer Science、pp. 259–274、Bibcode :2008LNCS.5401.....B、doi :10.1007/978-3-540-92221-6、ISBN 978-3-540-92220-9

[10] Almeida, Paulo; Baquero, Carlos; Fonte, Victor (2008)、「Interval Tree Clocks: A Logical Clock for Dynamic Systems」、Lecture Notes in Computer Science、vol. 5401、p. 259、doi :10.1007/978-3-540-92221-6_18、hdl : 1822/37748、ISBN 978-3-540-92220-9

[11] Zhang, Yi (2014)、「背景予備調査: 間隔木クロックの結果」、背景予備調査: 間隔木クロックの結果(PDF)

[12] Pozzetti, Tommaso; Kshemkalyani, Ajay D. (2021年4月1日). 「因果関係分析のためのリセット可能なエンコードされたベクトルクロックと動的競合検出への応用」. IEEE Transactions on Parallel and Distributed Systems . 32 (4): 772–785. doi : 10.1109/TPDS.2020.3032293 . S2CID 220362525.

[13] Lum Ramabaja (2019)、The Bloom Clock、arXiv : 1905.13064、Bibcode :2019arXiv190513064R

[14] ^ Kulkarni, Sandeep S; Appleton, Gabe; Nguyen, Duong (2022年1月4日 ) 。「物理クロックによる因果関係の実現」。第23回国際分散コンピューティングおよびネットワーク会議の議事録。pp. 97–106。arXiv : 2104.15099。doi : 10.1145 / 3491003.3491009。ISBN 9781450395601. S2CID 233476293。