この記事は システム系論文紹介 Advent Calendar 2014 の25日目のエントリである。

注意点としては、私は分散システムの専門家とは言い難いので、読者自身で確信・確認できることから信じていってもらいたい（間違った知識を覚えないように。もちろん誤りのないよう努力はしている）。

はじめに

Advent Calendar 最終日だけど特に締めとしてシステム系とは何ぞやと語ることはせず、分散システムにおいて有名な論文を今回も短めに紹介する。 「システム系論文」の定義っぽいものや、それと思われる論文の調べ方・読み方については23日目のy_uukiさんのインフラエンジニア向けシステム系論文 - ゆううきブログがよくまとまっているので、そちらを読むのがオススメである（ハテブ数も多い！）。

本エントリで紹介するのはLamport先生の以下の論文となる。見ての通り1978年だ！　そのとき私はまだ生まれていない。

` Time, Clocks and the Ordering of Events in a Distributed System Communications of the ACM 21, 7 (July 1978), 558-565. Reprinted in several collections, including Distributed Computing: Concepts and Implementations, McEntire et al., ed. IEEE Press, 1984. ` http://research.microsoft.com/en-us/um/people/lamport/pubs/time-clocks.pdf

これを紹介するのに選んだきっかけは次のブログを読んだことにある。 私がこの論文を特にオススメしたかったわけではないが、The Art of Computer Programmingや構造化プログラミングの話題のように原典を探せばいずれたどり着くような古典であり、そういった点は紹介するのに良いかもと興味を惹かれた。

fogus: 10 Technical Papers Every Programmer Should Read (At Least Twice)

こちらのブログでは、分散システム・プロトコルにおけるイベントの順序の論拠、 冗長性のためのstate machineアプローチの2点をあげている。 また、分散システムの分野に強く影響を与えた論文として自身で読むことをすすめている。

とはいえ、論理クロック自体を学ぶことについては書籍や関連スライド・大学の講義資料などに解説は載っているし、正直にいうと改めて読む必要はないのかもしれない。

例えば、分散システムの教科書である（通称）タネンバウム本の”論理クロック”(Logical Clock)の節で参照、解説もされている（絶版のようだが）。 洋書で問題なければ、Distributed Systems Concepts and Designという本もオススメであり、こちらも論理クロックのところで参照されている。 ちなみに私はソフトカバーを持っているが、こちらKindle版もあるらしい。 ってy_uukiさんのエントリからのリンク先でも紹介されていましたね（http://home.att.ne.jp/sigma/satoh/diary/diary100331.html#20100102 ）。

参考となるスライドを探してみる

Raftの紹介と同様に、今回も先にウェブで発見できる資料を紹介することにする。 今回の論理クロックというのは、講義・教科書に載るようなトピック・アルゴリズムでもある。

  • 同期 「クロック、論理クロック」
    • http://www.hpcs.cs.tsukuba.ac.jp/~msato/lecture-note/dsys-2014/lecture-dist-clock.pdf
  • 分散システム読書会 06章-同期（前編）
    • http://www.slideshare.net/tichi73/06-22228174

まとめ

今回も論文を読み終えなかったので、雑であるが〆る。 先のブログや上のスライドで説明されているように、論文中では物ごとが起こった(happen)の順序関係について説明している。 そして、論理クロックの概念や、state machineベースの分散システムの構築について記述している（後半全然読めていないので、読むことができたら加筆したい）。

それから、Vector clockと呼ばれるものが発明されたらしいのはこの論文より未来に戻ってきた1988年, 1990年頃の話である。 前者ソースはWikipediaではあるが、次の論文らしい。後者の論文はタネンバウム本より。

` Timestamps in Message-Passing Systems That Preserve the Partial Ordering ` http://zoo.cs.yale.edu/classes/cs426/2012/lab/bib/fidge88timestamps.pdf

` The Concurrent Reading and Writing of Clocks ACM Transactions on Computer Systems 8, 4 (November 1990), 305-310. Also appeared as SRC Research Report 27. ` http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-concurrent-clocks.pdf