Zenn
🐡

TupleSpaces の論文 Generative Communication in Linda 読んだ

2021/03/10に公開
#
linda
#
tuplespace
#
javaspaces
tech

David Gelernter. 1985. Generative communication in Linda. ACM Trans. Program. Lang. Syst. 7, 1 (Jan. 1985), 80–112. DOI:https://doi.org/10.1145/2363.2433

JavaSpace, GigaSpaces, dRubyやRinda（Rubyばっかりだ）に影響を与えた Tuple Space という概念について、最近興味を持ったので元論文を読んだ。読む前の雑なイメージだと並行プログラミングにおける黒板モデルとメッセージパッシングの間の子のようなものか？という雑な印象を持っていたが、思っていたものとちょっと違っていて興味深かったのでまとめる。まとめると、

  • Tuple Space に対する3つの操作 in(), out(), read() とその実行モデルを定義した
  • 定義すると面白いことにセマフォやタイマーやRPCなど、計算論上の様々な機構を実装できる
  • これでカーネルからシステムを作ろうとしているが、どんな実装上の課題に当たるかは未知数

といったところだろうか。Tuple Space ありきで話が進むが、Tuple Spaceは

  • out(+t) によってタプルtを入れることができる。すでに t がある場合はブロック
  • in(-t) によってタプルtを取り出すことができる。 t がまだない場合はブロック
  • read(t) によってタプルtを取り出さずに読むことができる
  • 上記の操作を複数のプロセスから並行して行うことができる、無限の空間

と定義されている。 out() で渡すのは基本的に即値であるが、 in() で取り出すものは変数（のようなもの、formalと文中で呼ばれている）に代入することで記述できる。 in() に即値を渡すとパターンマッチになって、たとえば in("his/key", v:string) と書くと ("his/key", "boooblah") というタプルがあったときに、これをマッチして取り出すことができる（＝誰か別のプロセスがこの値を過去にout()していたということ）。で、ここでのポイントは 1. 誰がout()したか 2. 誰がin()したか 3. いつ in/out されたか　はいずれも関係がなく自由であり、これを Communication Orthogonality と呼んでいる。
あと興味深いのは、継続渡しも in/out できるといっている。この in, out, read を並べて構造化したものがLindaという言語とその処理系である。

論文を読んでいるとin, outがごちゃごちゃになって混乱するので out=TSに対するput, in=TSからpop と読み替えるといいかもしれない。

できること

これによって、空間的にタプルを分散計算するだけでなく、時間的にもタプルを分散計算することができる概念なので面白い。分散しているけど共有できている。で、 Tuple Space を実装したLindaがあると何でも作れる（と主張している）。並べると、

  • RPC
  • Distributed Semaphores
  • ワーカープール
  • 同期メッセージ交換
  • 排他制御によるリソース管理（IOスケジューラの例が掲載されている、この例で継続渡しを使えているから簡単に書けるんだ、みたいなことが書かれいているがよくわからなかった）
  • Node Allocation
  • タイマー
  • Global黒板

などが作れる。具体的な作り方に関してはそんなに難しくないので、実際に論文をみてほしい。特にRPCなんかは容易に想像できるだろう。

Lindaの記法と例

  • s ... statement

順番に実行

s_1; s_2; ....; s_j

and-statement: 並行に実行

s_1 \& s_2 \& .... \& s_j

変数宣言

i:integer \& [s_1; s_2; .. in(P, var \ i); .. s_j]

or-statement: 排他的に実行する（どれが実行されるかわからない）

s_1| s_2| ....| s_j

0回以上の繰り返し: *s

実際には他にも関数定義とかいろいろあるっぽいが、単なる代入の模様。 if もあるけどよくわからない。。。

これでRPCを表現すると

呼び出し側:

out(P , me , args); in(me, results)

サービス側:

*[in(P, who, args); \\ body \ of \ procedure \ P; \\ out (who, values)]

みたいに簡単に書ける。

実装

本当ならハードウェアで実装したいけど、まだないので、ソフトウェア実装(virtual Linda Machine, VLM)で考える。

The VLM is required to simulate Linda’s infinite global buffer.

とか

A system in which reliable delivery is critical may implement (in Linda) one of the handshake protocols that allow reliable communication over unreliable channels.

当時は無理だろうし、今になっても無理だろうという話がかいてある。あと、故障についてもかなり楽観的にかかれていて、壊れた場合は in/out/read が失敗するので大丈夫と書かれているのだが、具体的なケースに関する考察はあまりない。

雑感

わたしなんかは汚れた大人なので Clockworks Orange に出てくる "in, out, in, out, in, out..." というセリフを思い出してしまうし、そもそも Linda という名前が Ada から発想してポルノ女優の名前をつけたとか、なんか子供には見せられない技術だけどいいのか・・・ってなった。

真面目な話をすると、この突飛な計算モデルについて論文中でも「これを真面目に実装するとネットワークが輻輳して大変なことができる、でもモデルの話をしているのだから、現在（当時）実装できるかどうかは大して問題じゃない、面白いかどうかだ」と言及している。1985年のことだから実際その通りだと思う。

実は 1978年にLamportによって "Time, clocks, and the ordering of events in a distributed system." が既に発表されていたわけで、これとの対比を考えると非常に興味深い。歴史はLamportが正しかったことを証明したわけだが、Lamportの相対論的な考え方（時空は歪んでいる）が "Network is unreliable" という考え方に発展したのに対して、 Gelernter はネットワークは "Network is reliable" という、時空が等方的であるという思想に拠っていたと考えると、20世紀初頭に物理の世界で起きたような対立が20世紀末にコンピュータの世界でも起きていたんだなあとエモい気持ちになることができる。

Leslie Lamport. 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558–565. DOI:https://doi.org/10.1145/359545.359563

しかも、さらに奇しくも皮肉なことに、今では批判も多いFLP不可能性定理もこの論文と同じ1985年に提案されていた。

Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (April 1985), 374–382. DOI:https://doi.org/10.1145/3149.214121

Refs

Discussion