過去・現在・未来

【 アルゴリズムの標準モデル 】 分散・並列アルゴリズムに、「時間」の概念が必要であることは、ある意味わかりやすいことかもしれない。 計算アルゴリズムの標準的なモデルは、Turing マシンである。多くの人は、分散・並列アルゴリズムのモデルには、Turingマシンは使えないと感じると思う。確かに、Turingマシンには「時間」の概念はない。また、ローカルな「プロセス」という概念もない。そこでの「状態」の概念は、Turing マシン全体にとってグローバルなものだ。 ただ、そうではないと、ランポートは言う。 なぜなら、グローバルなシステムのある不変量という概念は、意味のある概念である。それは、すべての可能なグローバルな状態についての述語であり、特定のグローバルな状態には依存しない。分散システムを実装すると言う問題は、異なるプロセスを通じて、システム全体の不変量を維持することと見ることができる。 ランポートは、並列・分散システムも Turing マシンの標準モデルで記述できると言う。 それでは、前回見たような分散・並列アルゴリズムの記述に必要な「時間」概念は、どうなってしまうのだろうか？　今回 紹介した論文 " The temporal logic of actions "は、まさに、こうした疑問に応えるものだ。 分散・並列アルゴリズムで、ある状態 s が状態 t に変化したとする。これを、s -> t と表すことにしよう。状態 s で利用されている変数を x, y, z, ... とした時、状態 s から変化した状態 t で利用される変数を、状態 s で利用されている変数名にプライム（ダッシュ）を付けて、x', y', z', ... と表すことにする。ここで、状態というのは、変数への値の割り当てであることに留意しよう。 この時、プライムなしの変数とプライム付きの変数から構成される式を、状態の変化 s -> t の「アクション」と呼ぶ。次の式は、アクションの例である。 　　x' = x + 1 この式は、x  の値は、s -> t である状態 t では、状態 s での変数の値 xを使えば、x + 1に変わることを表している。（ s -> t  で変数xの値は、1 増えるということである。） 逆に

【  相対論とプログラミング 】 今回のセッションでは、ランポートの「分散システムにおける時間と時計とイベントの順序付け」という論文を紹介します。 プログラミングをしている時に、アインシュタインの相対性理論を意識している人は、ほとんど絶無だと思います。 ただこの論文は、並列・分散アルゴリズムを理解する上で、相対論的な時間概念が本質的に重要であることを示したものです。（重力理論としての一般相対性理論ではなく、特殊相対性理論の方です。） もっとも、ランポートは相対論を直接に、並列・分散アルゴリズムに応用しようとしたわけではありませんし、この論文を相対論の解説として書いているわけでもありません。 彼は、並列・分散アルゴリズムの「同期」の問題を考えることを通じて、独自に相対論的時間概念にたどり着いているのです。これは、とても興味深いことです。（もちろん、彼は、相対論をよく知っていたと思います。） 彼は、現実の時間を示すリアルな「物理的な時計」に変えて、複数のプロセス上で定義される「論理的な時計」を考えます。この時計は、イベントが起きた絶対的な時間ではなく、二つのイベントで「どちらのイベントが先に起きるか」という相対的な順序関係のみを示します。この「論理的な時計」では、ある場合には、二つのイベントの時間は比較ができない場合もあります。 「我々は、まず最初には、空間的に分離したコンピュータたちのシステムに関心を持つだろう。しかし、我々の見解の多くは、もっと一般的なものに適用可能である。 特に、単一プロセッサーのマルチ・プロセスのシステムは、これらの分散システムと同様の問題を抱えている。なぜなら、起こりうるイベントは予測できない順序で生起するからである。 分散システムでは、時には、二つのイベントのどちらかが先に起きるかをいうことが不可能となる。「先に起きる」という関係が、それゆえ唯一のシステムのイベントの半順序関係である。」 これは並列・分散アルゴリズムについて、本質的に重要な洞察だと思います。 先に、「プログラミングをしている時に、アインシュタインの相対性理論を意識している人は、ほとんど絶無」だと書きました。 ただ、これは本当は、いいことではないように思います。 少なくとも、分散・並列アルゴリズムでは、ミンコフスキーやアインシュタインらの相対論的時間概念に匹敵する、時には常識

【 アルゴリズムの振る舞いを図解する 】 今回のセッションでは、Producer-Consumer同期のアルゴリズムの振る舞いを図解してみようと思います。（アルゴリズムの記述をみて、その振る舞いがわかった方は、読みとばしてもらって構いません。） ポイントは、ProducerのプロセスにもConsumerのプロセスにも登場するawait 命令です。正確にいうとawait の後ろの条件文が重要です。 await 条件文 命令は、条件文が真になるまで、次のブロックの実行をせずに待機し続けます。逆にいうと、条件文が偽になった時初めて、次のブロックを実行します。 Producerのawait 命令は、await Len(buf) < N という形をしています。Consumer のawait 命令は、await Len(buf) > 0　という形をしています。どちらの条件文にも、 使われているバッファーの長さを示す Len(buf) という式が含まれています。 このことは、ProducerのプロセスとConsumerのプロセスの同期に、この式の値が利用されていることを示しています。以下では、LB = Len(buf) と表すことにしましょう。 LB = N となるのは、どういう場合でしょうか？　それは N個の容量を持つバッファーが全て使われている場合です。この時、バッファーにはデータを受け入れる余裕がないので、データを入力 in からバッファー buf に送り込もうとするProducer は待機を続けます。 LB = 0 となるのは、どういう場合でしょうか？　それは バッファーが空の場合です。この時、バッファーには読みこむべきデータがないので、データをバッファー buf から読み込んで出力 out に送り込もうとする Consumer は待機を続けます。 結局、ProducerとConsumerの待機状態が解けて、それぞれのプロセスが本来の仕事をするのは、 0 < NB < N の場合だけであることがわかります。ProducerはNBの値を一つだけ増やし、ConsumerはNBの値を一つだけ減らします。 一つ注意したいことがあります。 以前に、「振る舞いは、状態の変化の系列だ」と述べたと思います。ただ、Produucer, Consumer プロセスが待

【 アルゴリズムの不変量 】 並列アルゴリズムを、状態の遷移として記述するアプローチを「状態モデル」と呼びます。 このアプローチとは別に、イベントの継起として並列アルゴリズムを記述するモデル「イベント・モデル」があるのですが、それについては後で述べます。 状態モデルでは、 　● 状態は、変数への値の割り当てです。 　● 状態の遷移の系列を「振る舞い Behavior」と呼びます。 　● 状態の遷移を引き起こすものを「アクション」と呼びます。 同一のFIFOアルゴリズムでも、可能なシステムの振る舞いは、多様です。それは無数に存在します。 ここでは状態の遷移を引き起こすアクションを並べて、振る舞いを記述してみます。先のセッションを参照ください。 システムの可能な振る舞いの例 1 　　P P P C P C P … システムの可能な振る舞いの例 2 　　P C P C P C … システムの可能な振る舞いの例 3 　　P P P C C C P … このアルゴリズムに基づく振る舞いは無限個存在するのですが、重要なことは、この状態モデルで全てのアクションの実行の全てのステップで成り立つ、状態についての論理式が存在刷ることです。 こうした状態についての論理式を、アルゴリズムの「不変式」「不変量」と呼びます。 次に見るbounded FIFO queue のアルゴリズムの「不変量」の存在は、このアルゴリズムがN個の容量のバッファを持つbounded FIFO queue の正しい仕様であることを示唆しています。 N個の容量のバッファを持つ bounded FIFO queueアルゴリズムの「不変量」は次のものです。 　　( Len(buf) ≦ N ) ∧ ( Input = out◦buf◦in ) ここで、記号◦は、リストの結合を表しています。 最初の項( Len(buf) ≦ N ) が成り立つのは、バッファーの容量は、高々N個であるという仮定から明らかです。 第二項 ( Input = out◦buf◦in ) については、初期状態では、Input=in で out=buf=<.> で成り立っています。 ある状態 st でこの式が成り立っていると仮定して、その次の状態 st’ でもこの式が成り立っていることを示せば、帰納法でこの式が不変量であることを示すこと

【 アルゴリズムとプログラムは違うものです 】 プログラムとアルゴリズムは似ています。 我々は、歴史的には、アルゴリズムの記述に、疑似的にプログラム言語を利用してきました。 だから、同じアルゴリズムの説明に、異なるプログラム言語が利用されていても -- 例えば、ある場合にはALGOLが、ある場合にはCが利用されていても --大きな違和感を感じることはなかったかもしれません。 なぜ、複数の異なるプログラム言語が、同一のアルゴリズムの記述に利用できるのでしょう？ それは、自然言語では普通のことです。同じ意味を、大抵の場合、日本語でも英語でもフランス語でも、異なる言語で表現できるからです。 プログラムとアルゴリズムは異なるものです。 プログラムは、具体的なコンピュータによって具体的に実行されるものですが、アルゴリズムは、その「具体的実行」の背後に存在する抽象的な「意味」に関わるものです。 そうしたプログラムの「意味」の記述としてのアルゴリズムの記述は、プログラム言語とは異なる形式が必要です。 ある意味当然のことですが、プログラムとアルゴリズムの違いの認識が生まれたことは重要なことです。さらには、一歩進んで、アルゴリズムを記述する言語の必要性の認識が生まれたことは、とても重要なことです。 ただし、残念なことは、こうした認識は、必ずしも多くの人に共有されていないと思います。 視点を変えましょう。 アルゴリズムとプログラムとの関係は、実践的には、「仕様」とその実装としての「プログラム」の関係としても考えることができます。 アルゴリズムの記述が「仕様」として与えられ、その実装が「プログラム」として与えられるということです。 ランポートによってアルゴリズム記述言語で与えられた、先に見た Algorithm PC は「仕様」です。bounded FIFO queueのプログラムは、この仕様としてのアルゴリズムを実装しなければなりません。 仕様は定義です。ある定義が正しいかと問うことは、形式的には意味がありません。 しかしながら、このアルゴリズムのいくつかの性質を証明することによって、我々はこのアルゴリズムがまさにbounded FIFO queueの仕様であることに確信を持つことができるのです。 我々があるアルゴリズムについて証明する最も重要な性質は、「

【 花咲く季節 】 今年は、サロベツも西海岸もエゾカンゾウ、当たり年でした。 去年は、サロベツの花は、この様子じゃいつか見られなくなるかもと落胆していたのですが。 サロベツだけじゃないんです。今年は、空き地にも道ばたにも、タンポポ、エゾタンポポ、マーガレットが沢山花を咲かせています。 昨日は、メグマ沼にアヤメの群生を、バッカイ（抜海）にスイレンを見に行きました。どちらの花も見事でした。そういえば、宗谷のクロユリの群生、見逃したこと残念です。これらの花、これまで僕は一度も見に行ったことなかったのですが。 鳥も鳴かず花も咲かない「沈黙の春」的な予想がはずれて、この「騒々しい未来」がおとずれたこと、嬉しいと思います。 今年は、花にとって、まるで、思いがけない何かが起きたようです。 最北の二つの島、利尻島と礼文島では、今年、全島でササの花が咲きました。120年に一度の出来事だと言われているようです。花を咲かせた後、ササは枯れて、その一生をおえるのだそうです。 今年の宗谷の花の大饗宴は、吉なのでしょうか？　それとも凶なのでしょうか？

【 なぜ、歴史を振り返るのか？ 】 このセミナーでは、一方では、ダイクストラらが登場し活躍した、ほぼ60年ぐらい昔の話を紹介しています。同時に、ランポートのTuring賞受賞記念講演をベースに、21世紀の視点から、並列アルゴリズムの "Early Days" を振り返ろうとしています。 なぜ、過去を振り返るのでしょう？ それには、意味があるのでしょうか？ 　 少なくともコンピュータのハードウェアに関しては、その過去を振り返ることは、技術史的興味や懐古趣味を別にすれば、あまり意味のあることのようには思えません。多分、60年前のコンピュータのハードウェアから、学べることは少ないと思います。 ただ、ハードウェアの進化・発展のまばゆい後光の奥には暗闇があります。 そこに目を凝らせば、別の様相が見えてきます。 一つには、並列・分散の「古典的」アルゴリズムは、この数十年大きな変化はないまま、多くの人に受け入れているように見えます。ただ、重要なことは、そのことは、こうしたアルゴリズムが「正しい」ものとしてしっかりと基礎付けられていることを意味しません。 もう一つには、もちろん、並列・分散のアルゴリズムを基礎づけようとする着実な試みが、存在することです。残念ながら、こうした取り組みの成果は、多くの人には届いていないように見えます。 こうした認識は「アカデミック」で「実践的」ではないと感じる人も多いでしょう。 でも、それは違うと僕は考えています。 何よりも、現代のコンピュータ・サイエンスを支えてきた最大のバックボーンである現実の世界でのコンピュータ技術の爆発的発展・普及が、新しい理論的枠組みを要求していると考えているからです。 高速化・高密度化するハードウェアのもとで、光の信号でさえ、ワン・クロックでも基板上数十センチしか進みません。こういう時、我々は「同期」の基礎である「同時性」をどのように考えればいいのでしょう？ 量子コンピュータのもとでの情報の「不確実性」だけではなく、量子エンタングルメントでの一見すると時空にとらわれない「因果関係」の登場、こうした問題は、情報処理技術の未来に深く結びついています。 あまり、顧みられていない探求の歴史から、学ぶことは多いと考えています。　 -------------------------------------------