Time, Clocks, and the Ordering of Events in a Distributed System
August 14, 2021分散システムの各プロセスにおける送受信の半順序関係をすべてのプロセスで起きた送受信の全順序関係に拡張するアルゴリズムを提案し、アルゴリズムを同期処理に応用できることを例示した。 分散システムではプロセスの時刻が同期しているとはかぎらない。 各プロセスで起きたメッセージの送受信をプロセスでの時刻順に並べられても、その計測時刻を信じて全プロセスで起きたイベントを正しく発生順に並べることはできない。
アルゴリズムは、プロセスごとに論理的なクロックをもたせる。 クロックは、メッセージを送信するときに時を進める。 メッセージを送信するプロセスは、送信時刻をメッセージにふくめる。 受信したプロセスは現在の時刻とメッセージにある送信元の時刻より先の時刻に時を進める。 以上の手続きで、異なるプロセス間の送受信であっても送信時刻が受信時刻より必ず前になり、全プロセスの送受信イベントに全順序関係を定義できる。
メッセージの送受信をイベントとし、イベントの「前に起きた」関係\(\rightarrow\)を以下で定義する。
- \(a, b\)が同じプロセスで起きたイベントであり\(a\)が\(b\)より前にあれば\(a\rightarrow b\)である。
- \(a\)があるプロセスからの送信であり、\(b\)がほかのプロセスによるそのメッセージの受信であれば、\(a\rightarrow b\)である。
- \(\rightarrow\)は推移律がなりたつ。異なる\(a, b\)において\(a\rightarrow b\)も\(b\rightarrow a\)も成立しなければ、\(a, b\)は並行である。
クロックをイベントを引数にとり時刻を返す関数とみなし、プロセス\(P_i\)のクロックを\(C_i\), システム全体のクロックを\(C\)とする。 \(b\)がプロセス\(P_j\)のイベントであれば\(C\langle b \rangle = C_j\langle b\rangle\)になる。 イベントの全順序関係を定義する上で\(C\)が正しい条件は、任意の\(a, b\)について\(a\rightarrow b\)であれば\(C\langle a \rangle < C\langle b \rangle\)となることである。 これは、次の1, 2が成り立てば十分であり、メッセージに送信元の送信時刻をふくめる冒頭の手続きでこれらをみたすことができる。
- \(a, b\)がプロセス\(P_i\)のイベントであり、\(a\)が\(b\)より前であれば\(C_i\langle a\rangle < C_i\langle b \rangle\)である。
- \(a\)が\(P_i\)による送信イベントであり、\(b\)が\(P_j\)による受信であるとき\(C_i\langle a\rangle < C_j\langle b\rangle\)である。
論文をこちらからダウンロードできます。
雑記
\(a\rightarrow b\)であれば\(C\langle a\rangle < C\langle b\rangle \)が成りたつが逆は成りたたない。 Virtual Time and Global States of Distributed Systems時刻をプロセス数と同数の長さのベクトルで表現すれば、\(a\rightarrow b \Leftrightarrow C’\langle a\rangle < C’\langle b\rangle \)が成りたつことを示した。 Virtual Time and Global States of Distributed Systemsを後日解説した。