分散計算の国際会議DISCに論文が採択されました

中央大学の白髪先生との共著論文が分散計算のトップカンファDISC2019に採択されました。会議は10月の半ばにハンガリーで行われたのですが, 台風19号の影響で私は学会に参加できませんでした (泣). 論文はfullverとproceedings から見れます. 50ページほどの超大作です！証明の気持ち等は少し長くなってしまうので, 結果だけ紹介させていただきたいと思います.

この研究では, グラフ上の合意モデルというものを考えます. 合意モデルでは, 各頂点が意見を持っており, それらが隣人と情報交換をしながら全員が同じ意見になるような状態を目指しています.  ここでは各頂点はAかBどちらかの意見を持つとし, 同期的な合意モデルを考えます. 同期的というのは, 下にある動画のように, 全ての頂点が意見を同時に更新するような合意モデルのことをさします. この研究ではBest-of-twoとBest-of-threeというモデルを考えます. この記事中の図や動画では, 二つの意見を赤色と緑色で表すこととします.

• Best-of-two (以下Bo2) では, 各頂点が隣人を2人ランダムに選び, 自分とその2人の持つ意見で多数決をとり, その意見で更新する.

図1. Bo2の挙動例 (矢印の先 = 選ばれた頂点)

• Best-of-three (以下Bo3) では, 各頂点が隣人を3人ランダムに選び, その3人の持つ意見で多数決をとる.

図2. Bo3の挙動例

 動画1. 完全グラフ $K_{500}$ 上でのBo2のシミュレーション

合意モデルの応用として, 次の設定を考えてみましょう: たくさんの計算ノードを持つシステムにおいては,  外部攻撃などの要因により, 計算途中で一部のノードのデータが破損してしまうことがあります. しかし各ノードは自分の保持するデータが破損しているかどうかは分かりません. そこで, 全頂点の意見の多数決をとることを考えるとき, 合意モデルを使えば良さそうな気がしてきませんか？

Bo2もBo3も, $n$頂点の完全グラフ上では任意の初期状態で $O(\log n)$ ステップで合意 (i.e. 全頂点が同じ意見を持つ状態) に高確率 (確率 $1-n^{-c}$ for some 定数 $c>0$) で至ることが知られています.  また, エキスパンダーグラフ上では, 初期バイアスの仮定 (初期状態で意見に人数差が $\Omega(\sqrt{n\log n})$ あるという仮定) の下では $O(\log n)$ ステップで多数決に合意することが知られています.

この研究では, より複雑な構造をしたグラフ上での合意モデルの挙動解析を究極的な目標と見据え, その第一ステップとして stochastic block model (以下SBM) と呼ばれるランダムグラフ上でBo2とBo3を解析しました. SBMとは, 次で構成されるランダムグラフ $G(2n,p,q)$ のことです: $2n$個の頂点からなるグラフで, 頂点集合が $n$ 個ずつ二つのグループ $V_1,V_2$ に分かれており, 同じグループに属する二頂点を結ぶ辺は確率 $p$ で辺を引き, 異なるグループ間では確率 $q$ で辺を引きます. 辺の有無は各頂点ペアで独立に定めます. 仮定として $p>q$ をおきます. つまり, 同じグループ間はより辺が引かれやすいため, $G(n,p,q)$ は下図のようなコミュニティ構造を持つことが分かります.

図3. $G(300,\,0.1,\,0.01)$

$p=q$のとき, $G(n,p,p)$はコミュニティが一つになりますが, $p$が小さすぎなければ, $G(n,p,p)$はエキスパンダーなので既存研究により, 初期バイアスの仮定の下では $O(\log n)$ステップでBo3とBo3ともに合意に至ることが直ぐ言えます.

下図のように, それぞれのコミュニティが違う意見を指示している初期状態からBo2, Bo3をスタートさせるとどうなるでしょうか？

図4. それぞれのコミュニティが違う意見を指示している.

$p=q$だと$G(n,p,q)$は単一コミュニティなのですぐ合意できますが, $p\gg q$だと喧嘩別れしたままの状態が続き, すぐには合意できなさそうですよね. 実際シミュレートしてみるとそうなることが (実験的に) 分かります.

 

動画2. $G(300,\, 0.1,\,0.04)$ 上の Bo2

動画3. $G(300,\,0.1,\,0.01)$上のBo2

私たちの論文では, 次の結果を証明しました.

定理1 (informal).

$G(n,p,q)$ 上の Bo2を考える. ただし $p\geq q>0$ は$n$ に依存しない定数. 

1. $q/p > \sqrt{5}-2$ ならば, 任意の初期状態に対して高確率で $O(\log n)$ ステップで合意.

2. $q/p < \sqrt{5}-2$ ならば, "喧嘩別れ"の初期状態から開始したとき, 高確率で, 合意に至るまで少なくとも指数時間 $2^{\Omega(n)}$ 時間かかる.

定理2 (informal)

$G(n,p,q)$ 上の Bo3 も定理1と同じことが成り立つ. ただし閾値は$\sqrt{5}-2$ではなく $1/7$.

定理1,2では $p\geq q>0$ は定数なので$G(n,p,q)$は非常にdenseなのですが, よりスパースな状況 ($p\geq q=\omega(\log n/n)$ も考えています. スパースな場合は, $q/p>$閾値かつ初期ギャップの仮定 (初期状態における意見の支持人数差が$\epsilon n$ある) の下で$O(\log\log n)$ ステップで合意に至るものの, $q/p<$閾値ならば初期ギャップの仮定の下でも指数時間かかりうる, という結果もしめしています.