論理クロック

論理クロックは、分散システムにおける時系列および因果関係を捉えるメカニズムです。多くの場合、分散システムには物理的に同期したグローバルクロックがありません。多くのアプリケーション（分散GNU makeなど）では、2つのプロセスが相互作用しない場合は同期の欠如は観測できず、これらのアプリケーションでは、プロセスが壁時計時間ではなくイベントの順序（つまり、論理クロック）に同意するだけで十分です。^[1]最初の論理クロックの実装であるLamportタイムスタンプは、1978年にLeslie Lamportによって提案されました（ 2013年にチューリング賞受賞）。

論理クロックシステムでは、各プロセスは論理ローカル時間と論理グローバル時間の2つのデータ構造を持ちます。論理ローカル時間はプロセスが自身のイベントをマークするために使用され、論理グローバル時間はグローバル時間に関するローカル情報です。各ローカルイベントの後に論理ローカル時間を更新し、プロセスがデータを交換するときに論理グローバル時間を更新するために特別なプロトコルが使用されます。^[2]

論理クロックは、計算分析、分散アルゴリズムの設計、個々のイベントの追跡、計算の進行状況の調査に役立ちます。

注目すべき論理クロック アルゴリズムは次のとおりです。

• 単調に増加するソフトウェア カウンターであるLamport タイムスタンプ。
• 分散システム内のイベントの部分的な順序付けを可能にするベクトル クロック。
• バージョン ベクトルは、楽観的複製システムで、更新に従ってレプリカを順序付けます。
• マトリックス クロックはベクター クロックの拡張であり、他のプロセスから見たシステムに関する情報も含まれています。

• 分散システム論理時間 // ロベルト バルドーニ、シルビア ボノミ。ローマ・サピエンツァ大学 MIDLAB
• 第 3 章: 論理時間 // Ajay Kshemkalyani および Mukesh Singhal、分散コンピューティング: 原理、アルゴリズム、システム、ケンブリッジ大学出版局、2008 年
• 分散システム 06. 論理クロック // Paul Krzyzanowski、ラトガース大学、2014 年秋