人狼ゲームの比喩で語る合意形成アルゴリズム
合意形成アルゴリズム
Paxos や Raft に代表される、耐障害性を持つ合意形成アルゴリズムが研究・実装されてきた。
近年では Kubernetes の Control plane として利用されている etcd において Raft が実装されていたり、Blockchain における Peer 間での合意形成としての Proof of Work (PoW), Proof of Stake (PoS) の話題に上がったりと、言葉だけでも聞いたことがある人は多いと思う。分散コンピューティングの業界では、古くから研究されてきた概念だ。コンピューターサイエンスを学ぶ過程で、ビザンティン将軍問題について聞いたことがある人もいるかも知れない。
実運用の叩き上げで学んできた場合、Elasticsearch Cluster を組むときに Split Brains 問題を避けるため、もしくは Amazon DynamoDB Accelerator (DAX) Cluster を組む時に 3 つ以上の nodes が必要と何故か言われたのでとりあえずそうした、という運用を経験したこともあるかもしれない。
アプリケーション開発者が、合意形成アルゴリズムを実装した ZooKeeper や etcd といったデータベースを利用することはそう頻繁にない。しかし、ZooKeeper は HBase, Hadoop YARN, OpenStack Nove, Kafka のバックグラウンドで動作している。実は間接的に使っていた、という場合は良くある。
合意形成アルゴリズムの実装は非常に難易度が高いとされ、特に合意形成アルゴリズムの一つである Paxos を理解または証明するのは更に困難だと言われているのだが、アナロジー思考を通じて、その片鱗に少しだけでも触れてみる。
人狼ゲーム
いきなりだが、「人狼ゲーム (Are You a Werewolf?)」というゲームを知っているだろうか。
私も人狼ゲームを何度か遊んだ経験がある。大学生時代にプログラミングを中高生に教えていたのだが、当時の若者の間で人気だったのがこのゲームだ。
人狼ゲームのルール
詳しいルールについては検索してほしいのだが、要約すると「村人陣営と人狼陣営による心理戦ゲーム」だ。Wikipedia によると、発祥はアメリカで発売されたボードゲームらしい。
汝は人狼なりや?（なんじはじんろうなりや、Are You a Werewolf?）は、アメリカのゲームメーカーLooney Labs.より2001年に発売された、会話と推理を中心にしたパーティーゲームである。このゲームのルールは、ドミトリー・ダビドフが1986年に制作した「Мафия Mafia」が元になっているとされる。 ... Wikipedia "汝は人狼なりや?" より
10 名前後で遊べるルールとされるが、極端なことを言うと 3 人から遊べる（ところで、「3」というのは、合意形成アルゴリズムをかじったことのある人にとっては、既視感のある数字ではないだろうか）。
人狼同士はお互い誰が人狼かを知ることができる。村人同士は誰が村人かは知らない。ここに情報格差がある。この情報格差を利用して、人狼陣営は村に混乱を招く。
人狼では、一日という単位でゲームが進行する。日中のターンでは、人狼は村人のふりをして過ごしているので、誰が村人で誰が人狼かは分からない。このターンに、村人同士誰が人狼か？について滔々と議論をする。もちろん人狼は「自分は村人だ」という嘘の主張をする。人狼同士は互いに誰が人狼かを知っているので、ある村人を「こいつは怪しい」と仕立て上げた演出をすることもできる。
夕方のターンで、村人＋人狼たちの投票によって "処刑" する人狼を選出する（そう、投票 "Election" だ）。多数決で指名されてしまった人は、その後のゲームに参加することはできない。
やがて、満月の夜のターンがやってくる。このターンで、人狼たちは狼の本性を表し、一夜に一人村人を "襲う"。翌朝、その襲われた村人はゲームから除外され、その後のゲームに参加することはできない（まるでネットワーク障害で切断されたノードがクラスターから除外されたかのようだ）。
そして、これをゲームがプレイを続行できなくなる人数に減るまで続ける。村人陣営は、すべての人狼を "処刑" できたら勝利。一方人狼陣営は、過半数を獲得したら勝利（なぜ過半数か、この記事を読み終わったらぜひ改めて考えてみてほしい）。
人狼ゲームとのアナロジー
ではここで、一つ思考実験をしてみる。一つの主張として、この人狼ゲームの過程は、合意形成アルゴリズムとのアナロジーとして語れる点が多いのではないか？という点について考察してみる。もちろんこのアナロジーは完璧では無いので、細かいところで不一致はするのだが、本質を掴むためには困らないであろう。
選出による合意形成と夕方のフェーズにおける "処刑"
人狼ゲームにおける人狼とは、いわゆる「故障した node」と捉えることができる。夕方のフェーズにおける "処刑" とは、「投票」命令のことである。そう考えると、夕方のフェーズは、「leader node が故障したときに、新しい leader の投票フェーズ」であると言い換えることができよう。
Raft になぞらえてみると、村人全員が Candidate となり、RequestVote RPC を発行している状態と言えようか。これによって Leader が選出される。そして、毎フェーズごとに leader が消えていくという点が、nodes が復元しうる実際の分散コンピューティングとは異なる点ではあるものの、翌日になると生き残った Follower たちが、新たな Leader を選出するために心理戦を続行する、という状況に見えてくる。
この前提で、次の例について考えてみよう。
最低 nodes 数と最低プレイ人数
例えば、人狼では 3 人以上メンバーがいないと遊べない。それはなぜか。
ここで etcd の documentation に記載されている、推奨される HA 構成の nodes 台数について紹介したい。Clusters を組む時、nodes の台数が 2 の場合を考えてみる。このケースでは過半数は 2 になるので、1 台でも故障すると過半数が成立しない。したがって、新しい leader を選出できない。そのため、耐障害性を持つとは言えない。
| Cluster Size | Majority | Failure Tolerance |
|---|---|---|
| 1 | 1 | 0 |
| 2 | 2 | 0 |
| 3 | 2 | 1 |
| 4 | 3 | 1 |
| 5 | 3 | 2 |
| 6 | 4 | 2 |
| 7 | 4 | 3 |
| 8 | 5 | 3 |
| 9 | 5 | 4 |
そう、耐障害性を保つためには、3 台以上の nodes が必要なのだ。同じようにして、人狼ゲームを続けるためには、3 人以上のプレーヤーが必要なのだ。
Failure Tolerancy と人狼の勝利条件
人狼の勝利条件については、｢人狼の生存数が村人の生存数と同じまた上回る」とされる。すなわち過半数だ。これについても、先程の図とともに考えてみるとわかる。
人狼は、人狼同士誰かを知っている。つまり、過半数以上の議決を獲得すると、一方的に村人を指定することができる。すなわち、この時点で村人側が勝利することはできない。そう、村の均衡は崩れてしまった。もう村を人狼から守ることはできない。
この現象は、Blockchain 界隈でも、Majority attack や 51% attack と呼ばれる。
分散コンピューティングにおいても同様に、半数以上の nodes が一気に故障すると、たちまち合意形成は機能しなくなり、耐障害性を失うことになる。
よく、合意形成アルゴリズムを実装するデータベースにおいて Clusters を組むときには、「5 台の nodes でクラスターを組むと良い」と言われるが、これはなぜか。先程の表にある通り、Cluster Size == 5 のときの Failure Tolerance == 2 だ。一気に 2 台以上 nodes が故障することはめったに無いであろう、という前提のもとの意見なのである。
そう、人狼ゲームも 3 人から遊べるとはいえ、面白くなるためには 5 人以上必要になってくるのと同じなのかも知れない。
ビザンティン将軍問題と "裏切り者" プレイヤー
ビザンティン将軍問題では、誰が裏切り者の将軍かが分からないため、包囲している都市を攻撃するのか、撤退するのかといった伝達情報に嘘の内容が含まれうるという条件が盛り込まれている。
実は人狼ゲームにも応用ルールが合って、「占い師」、「霊媒師」、更には「裏切り者」と行った追加の役割が存在する。それらの詳細については調べてほしいのだが、この 「裏切り者」プレイヤーが、まさにビザンティン将軍問題における裏切り者の役割に当たる。このプレイヤーは、村人陣営としてカウントされながら、人狼陣営に加担し、人狼陣営の利得のために行動する。いけすかないやつだ。
日中フェーズは皆村人である。ビザンティン将軍問題に置き換えると、みなビザンティン帝国の将軍である。しかし、誰か裏切り者が混じっている。その裏切り者の情報によって、村人同士の議論は大いに紛糾する。人間同士の争いというのは複雑だ。複数台のノードで構成されたクラスターの信頼性を保つ方が、よっぽど簡単かもしれない。
まとめ
以上、思考実験として、人狼ゲームを利用して、合意形成アルゴリズムとアナロジー思考を試みてみた。人狼ゲームに詳しいあなたは、きっと Paxos や Raft といった合意形成アルゴリズムも容易に理解できたことだろう（本当に？）。