Virtual Time and Global States of Distributed Systems(1988)

#分散システム

April 22, 2023

分散システムのプロセス間で時刻が常に同期しているとは限らない。プロセスの時刻から判断すると、プロセスでは、ほかのプロセスのイベントと比べてどちらが先に起きたか分からないイベントが起きえる。 Lamportは、各プロセスに単調増加する論理的な時刻をもたせ、メッセージとともに時刻をプロセス間で交換することで、イベントの依存関係と矛盾せずにイベントを全順序に並べる手法を提案した。先行するイベントは、必ず後続のイベントよりも小さい時刻をもつ。しかし、逆は必ずしも成り立たない。先行する場合もあれば、前後関係がないこともある。 Virtual Time and Global States of Distributed Systemsは、各プロセスの時刻を、プロセス数とおなじ数の長さの配列で表現する。これにより、時刻の前後関係が定義されていることがイベント間に前後関係があることの必要十分条件であることを可能にした。

イベント$e$が$e'$に先行する関係を$<$と書くなら、Lamportのアルゴリズムは、イベントから時刻への関数を$C$として $$ e<e' \rightarrow C(e) < C(e') $$ が成立するようにイベントに時刻を割りあてられる。イベントが発生すると、プロセス$i$の時刻$C_i$が増加する。別のプロセスとやりとりしないイベントが発生すると、時刻が$d$増加する。 $$ C_i:=C_i+d\ (d>0) $$ プロセスがメッセージと一緒に送信時刻$t$を別のプロセス$i$に送ると、メッセージを受信した$i$は、送信元や自身の時刻よりも大きい時刻に更新する。 $$ c_i := \max(C_i,t)+ d\ (d>0) $$

Virtual Time and Global States of Distributed Systemsでは、$n$個のプロセスからなる分散システムのプロセス$i$の時刻を長さ$n$の配列で定義する。 $i$で別のプロセスと通信しないイベントが発生するとき、$C_i[i]:= C_i[i]+1$と時刻を更新する。プロセス$j$からメッセージと一緒に送信元の時刻$C_j$を受信したときは、$C_i:=\max(C_i, C_j)$として要素が$C_j$より小さくならないように更新する。時刻$u, v$の前後関係$\le, <$と順序関係の未定義$||$の定義は、 $$ u\le v\ \textit{iff}\ \forall i: u[i]\le v[i] $$ $$ u<v\ \textit{iff}\ u \le v\ \textrm{and}\ u\neq v $$ $$ u||v\ \textit{iff}\ \neg(u<v) \textrm{and}\ \neg (v<u) $$ である。

以下に論文中にある実行系列の例を示す。Lamportの手法の場合は、時刻を0で初期化し$d=1$とすると$\begin{pmatrix}0\\1\\0\\0\end{pmatrix}$と$\begin{pmatrix}0\\0\\0\\2\end{pmatrix}$のイベントの時刻はどちらも$\begin{pmatrix}2\\1\\2\\1\end{pmatrix}$より小さくなる。前者は前後関係があり、後者は未定義である。 example

雑記

Lamportの論文も以前解説した。

論文では、デバッグと分散システムのアルゴリズムの設計が応用先として提案されている。アルゴリズムの設計の応用例として、Distributed Snapshots: Determining Global States of Distributed Systemsを提案手法で再実装する方針の説明がある。ただし、もとのアルゴリズムとの比較がない。デバッグに役立つと語るならば、デバッグの容易さを比較するべきだろう。

また、デバッグとは別に、アルゴリズムの設計に役立つと主張するなら、Lamportの$e<e' \rightarrow C(e) < C(e')$が$e<e' \leftrightarrow C(e) < C(e')$になることで可能になるアルゴリズムがあることを主張すると説得力が増すだろうが、そのようなアルゴリズムの提案は論文中にはない。