こんにちは、ヘルスケア事業部のちょうです。最近並列処理の勉強で「 The Art of Multiprocessor Programming」という本をひたすら読んでいます。どうやらこの本はコンピューターサイエンス修士の教科書として使われるらしく、宿題も付いています。第一章の練習問題の中で、一問を選び、みなさんと一緒に検討しようと思います。
第一章なので、何を前提に学ばないと解けない程度ではなく、かつ選んだ一問は並列処理に詳しくなくても問題ないのでご安心ください。
練習問題4
You are one of P recently arrested prisoners. The warden, a deranged computer scientist, makes the following announcement:
- You may meet together today and plan a strategy, but after today you will be in isolated cells and have no communication with one another.
- I have set up a “switch room” which contains a light switch, which is either on or off. The switch is not connected to anything.
- Every now and then, I will select one prisoner at random to enter the “switch room.” This prisoner may throw the switch (from on to off, or vice-versa), or may leave the switch unchanged. Nobody else will ever enter this room.
- Each prisoner will visit the switch room arbitrarily often. More precisely, for any N, eventually each of you will visit the switch room at least N times.
- At any time, any of you may declare: “we have all visited the switch room at least once.” If the claim is correct, I will set you free. If the claim is incorrect, I will feed all of you to the crocodiles. Choose wisely!
- Devise a winning strategy when you know that the initial state of the switch is off.
- Devise a winning strategy when you do not know whether the initial state of the switch is on or off.
Hint: not all prisoners need to do the same thing.
訳して
君は最近逮捕されたP人の囚人の一人です。看守長は危険なコンピューター科学者でこのようなアナウンスをしました。
- 今日で君はほかの囚人と会い、策を考える。今日以降君が隔離された監房に居て他の囚人とコミニュケーションできない。
- 私は一つのスイッチルームを準備した。ルームの中ではライトのスイッチがあります。そのスイッチはONかOFFかの状態です。スイッチは何とも繋がってないです。
- 時々私はランダムで一人の囚人を選び、スイッチルームに入らせる。囚人はスイッチを入れる（もしくはOFFにする）か、スイッチをそのままにしてルームから去る。（選べられた囚人）以外の人はこのルームは入れない。
- 囚人の一人一人は何回でもルームを訪ねる。もっと精確にいえば、どんなNでも、最終的に君らの一人一人はすくなくともN回以上訪ねる。
- いつでも、君らの一人はこんな宣言をできる。「私達は全員一人一人すくなくとも１回以上スイッチルームを訪ねた」。もしその宣言は正しければ、私はあなたを自由にする。そうでなければ、あなたをワニの餌とする。賢く選べ！
- 最初スイッチがOFFの状態を知った上で勝利できる策を考えよう
- 最初スイッチの状態を知らずで勝利できる策を考えよう
ヒント：すべての囚人は同じことをやる必要がない
まず問題の条件をまとめよう
- 直接通信の手段はない
- スイッチルーム、毎回一人しか入れない、できることは：ON -> OFF、OFF -> ON、何もしない
- 一人一人はルームに何回でも訪ねる
- 全員１回以上ルームを訪ねたら宣言する
並列処理の言葉で言い換えれば
スイッチ：シェアされた変数
ルーム：クリティカルセクション
ON -> OFF、OFF -> ON：書き込み
何回でも訪ねる：何回でも参照できる
になりますが、これら知らなくても問題ないです。
ヒントからそれぞれ同じことをやる必要がないから、すくなくとも二種類にあることがわかりました。
そしてすべての囚人がルームを訪ねたというのを証明できる方法の中で、一番簡単なのは、カウンターです。つまり、P人がいるので、P人が数えたということです。
この２つ合わせて、P人の中で
- 一人はカウンター役
- ほかの人は数字を増やす
になります。
もちろん、スイッチなので、数字を増やせないです。
Pは偶数か奇数によって、スイッチの状態を確認すれば？残念ですが、カウンター役の前に何人が訪ねたのがわからないです、間違って宣言する可能性があります。
例えば、Pは偶数として、最初スイッチの状態はOFF。カウンター役以外の人はスイッチを切り替える。そうするとカウンター役の前に１人、３人がルームを訪ねた状態は区別がつかないです（共にONになる）。
ではとうすればいいですか。ここのポイントは多分スイッチの状態ではなく、スイッチは何回状態を変えたことです。言い換えれば、ONになった回数です。
具体的にカウンター役の人は、スイッチがONだと、OFFにします。ほかの人はOFFだと、ONにして、ONだと、何もしない。重複計算しないように、ほかの人は最初の一回だけ、OFFからONにします。このあと、OFFだろうか、ONだろうか、何もしません。こうすると、カウンター役はONの場合、OFFにして、プラス１、カウンターがP - 1になったら宣言します。Pではなく、P - 1の理由はカウンター役自身はカウンターに入りません。まとめてみると
- カウンター役一人、スイッチがONだと、OFFにして、プラス１、カウンターがP - 1になると宣言する
- ほかの人、最初の一回だけ、OFFだと、ONにする
もちろん、この策は最初からスイッチの状態を知る必要があります。問１で最初スイッチはOFFの前提にすると、カウンターがP - 1になる時点で宣言できます。もし最初スイッチがONだと、正しいカウンターはPになるのです。なので、問２はこの方法では解決できません。
最初スイッチがONでも、OFFの数をカウンターすればP - 1になった時点で宣言できますが、最初の状態はわかりません。分かってもカウンター役と通信できないし、ルームに入る順番も決められません。ではどうすればいいでしょうか。
正直自分がここで詰まったので、解答を見てしまったんです。ソリューションは二回カウンター：
- カウンター役は一人、スイッチがONだと、OFFにして、プラス１、カウンターが2P - 2になると宣言する
- ほかの人、最初の二回だけ、OFFだと、ONにする
単なる問１の解答を２倍にするだけではないか。と思ったら、最初スイッチがONとOFFのケースを別々考えましょう。
最初OFFだと、２回カウンターだけです。（P - 1）* 2 => 2P - 2です。
最初ONだと、全てのカウンターが終わったら、P + P - 1 => 2P - 1になります。ここで、2P - 2になった時点で、ある人がルームを訪ねてないケースがありますか。
- まず、カウンター役は訪ねてないケースがありえないです。カウンター役は宣言する人です。訪ねてない限り、宣言はしません。
- ほかの人の中にいる人、もしこの人が訪ねてないと、最大カウンターはP - 1 + P - 2 => 2P - 3になります。つまり、2P - 2になる時点で、必ずこの人が訪ねました。
なので、そういうケースがありません。2P - 2になった時点で、すべての人が訪ねた。
よって、二回カウンターが正しいです。
これで問題解決しました。
いかがでしょうか。たまにはこういうクイズを解いてみませんか。毎日のプログラミングと違い、頭を動かして、新しい発想が見つかるかもしれません。
