« 食事をする哲学者、ランポートのパン屋 | トップページ | アンケートというものに関するある興味 »

2018年11月10日 (土)

ランポートと時計(分散システムは相対性理論の心を持っている)

前の記事でランポートのパン屋は分散システムで利用可能と書いたのですが、それに関連して、分散システムの時計とランポートについて書きます。

たとえば make というコマンドは複数のファイルの作成順序に基づいて処理を実行しますが、その順序を(特殊な実装でない限り)タイムスタンプで判断しています。したがって、 make にはシステム全体に共通した時計が必要になります。 make が必要とする時刻の精度ならば、分散している各ノードの時計を合わせることは可能かも知れませんが、ここでは、もっと厳格に時間を扱うことを考えましょう。そうすると、もはや分散しているシステム全体に共通した時計は仮定できないことになります。

そこで、事象(ファイル作成)の順序を比較するものとして、タイムスタンプの代わりに論理クロックというものが考えられています。論理クロックは、事象の順序だけに注目した時計です。論理クロックについては 並列分散システムでの「クロック」 に解りやすい説明が有ります。そこでは、ベクター・クロックとランポート・クロックが説明されています。

分散システムにおいて、あるノードで発生した事象がネットワークを通って各ノードに到達する時間は、受け取るノードによって異なります。したがって、2つの事象の順序は、それを検出するノードに依存します。図において、2つの事象 a, b がノード1では a1・b1 の順序で発生し、ノード2では b2・a2 の順序で発生しています。

ノード1 ノード2 a1 c1 b1 c2 b2 a2

このような分散システムの時計の性質は(特殊)相対性理論に通じるものが有ることにランポートは気付きました(Lamport の論理クロック)。相対性理論でも、2つの事象の順序が観測者によって異なることが有ります。また、全ての観測者に共通した時計も有りません。分散システムはまるで相対性理論であるかのようにランポートには感じられたのではないでしょうか 。

« 食事をする哲学者、ランポートのパン屋 | トップページ | アンケートというものに関するある興味 »

プログラミング」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/584699/67367457

この記事へのトラックバック一覧です: ランポートと時計(分散システムは相対性理論の心を持っている):

« 食事をする哲学者、ランポートのパン屋 | トップページ | アンケートというものに関するある興味 »