Lamport の論理クロック

Lamport さん自身のページ (in microsoft research) の中で、自分の論文についてコメントを付けてあるので、論理クロックの論文についての箇所をいくつか読んでみる。

まずは、Einstein の特殊相対論に影響をうけたことについての箇所。

The Writings of Leslie Lamport
I happen to have a solid, visceral understanding of special relativity (see [4]). This enabled me to grasp immediately the essence of what they were trying to do. Special relativity teaches us that there is no invariant total ordering of events in space-time; different observers can disagree about which of two events happened first. There is only a partial order in which an event e1 precedes an event e2 iff e1 can causally affect e2.

特殊相対論のしっかりとした、本能的な理解に偶然たどりついた。[...]特殊相対論は、時空で起きるイベントについて、不変の全順序が存在しないことを教えてくれる、異なる観測者は、2 つのイベントのどちらが先に起きたかについて、食い違っても良いのだ。そこには、半順序しか存在しない、それは イベント e1 が e2 に因果的に影響を与えるときに限り、e1 は e2 に先立って起きるというものだ。

http://research.microsoft.com/users/lamport/pubs/pubs.html#time-clocks

もうひとつ、因果性に矛盾しない全順序の持つ含みについて。

The Writings of Leslie Lamport
It didn't take me long to realize that an algorithm for totally ordering events could be used to implement any distributed system. A distributed system can be described as a particular sequential state machine that is implemented with a network of processors. The ability to totally order the input requests leads immediately to an algorithm to implement an arbitrary state machine by a network of processors, and hence to implement any distributed system. So, I wrote this paper, which is about how to implement an arbitrary distributed state machine. As an illustration, I used the simplest example of a distributed system I could think of--a distributed mutual exclusion algorithm.

イベントの全順序付けアルゴリズムが、任意の分散システムを実装するために利用できることに程なく気がついた。分散システムは、プロセッサのネットワークとして実装されている、特定の連続状態機械として記述できる。入力リクエストの全順序可能性は、直ちに、プロセッサのネットワークによる任意の状態機械を実装するアルゴリズムへと繋がり、従って、任意の分散システムを実装するアルゴリズムへと繋がる。なので私はこの、任意の分散状態機械を実装する方法に関する論文を書いたのだ。例として、考えつく最も単純な分散システムの例である、分散相互排除アルゴリズムを使った。

http://research.microsoft.com/users/lamport/pubs/pubs.html#time-clocks

「任意の分散システムを実装するために利用できる」のところが分かっていない。もう一回読み返してみよう。