古代王国の人口調査問題

大学はまだしばらく夏休みですね。でも、そろそろ後期に向けて勉強、研究する頭を用意してはどうですか。

ということで、問題を出します。｢古代王国の人口調査｣です。これは現代では起こらない例ではありますが、Chandy-Lamport（1985年）が発表した有名な分散システムの論文の本質を例示するものと言われています。学部授業｢分散システム｣や大学院｢並列分散処理特論｣で取り上げるものなのですが、みなさんもちょっと考えてみてはいかがでしょうか。

• 古代のABC王国は、多数の村落（A村、B村、C村、...）から成る。
• 各村毎に適宜、人口を計算し、王国全体の総人口を得たい。
• しかし、人々はかなりひんぱんに、テントを持って別の村へ移住する。
• したがって、村の中の人口だけカウントしても、旅行中の人はカウントされない。
• そこで考え出されたのが、図中の｢赤帽の役人｣の送出である。
• この役人の役割は、各村の人口調査に勘定されない、旅行中の人をカウントすることにある。
• 村どうしは、2本の一方通行道路で結ばれている。村への入口と出口に扉がある。
• 道路はFIFO（First-In, First-Out）である。すなわち、道路で人を追い越すことはできない。

この図をにらんで、そして上記を元に、人口調査手順を構成してみて下さい！
非常に優れたアルゴリズムは、例外なく（分かってしまえば）単純明快なもので、しかも奥深いようです。Chandy-Lamportのアルゴリズムも、まさにそのようなものと言えるでしょう。