囚人とスイッチ問題
有名な問題
P人の囚人がそれぞれの独房に収監されている.
それ以外に１つだけスイッチのある部屋が存在する.スイッチはon/off以外の状態を持たない.
無作為にスケジュールされて毎日、囚人nがスイッチ部屋に入れられる.
囚人はスイッチのon/offを切り替えても切り替えなくてもよい.
いつかは必ずP人がスイッチ部屋にN回以上入ることは保証されている（一様分布の乱数で決めるということ.）
「P人全員がスイッチ部屋に一度は入った」ことを囚人は全員宣言できる権利がある.
正解すれば全員釈放
まだ入ったことのない囚人がいれば全員処刑.
この最初の一日を除いて囚人たちは戦略（協調プロトコル）を相談することはできない.
いかにして解決するか？
ヒント
全員の役割を同じにしなくてもよい
全員の役割が完全に同じで解けると、自律・分散・協調的で耐障害性が高いとみなせる
この制約をクリアする解法は無い気がするnikezono.icon
シングルコアのマルチスレッドで、1bitのbool変数bだけがある状況だと置き換えられる.
スレッドローカル変数はいくらでも宣言してよいが、共有メモリには b 以外宣言できない.
全スレッドが値をメモリに確認しに行ったことはスレッドローカル変数だけで証明できるだろうか？
Pが数人でいいなら、役割わけでなんとかできそうな気がする shokai.icon
「ONの時だけOFFにする人」「OFFの時だけONにする人」「何もしない人」「トグルする人」など
役割分けをすると、「OFFを観測したら一回だけONにする人たち」「OFFにできる人(ONの回数をカウントする人）」の役割分けで解決ですnikezono.icon
役割を完全に同じにしたら多分解けない. 逆に、最低限必要なスイッチの数が計算可能かも