この論文では以前の論文と同様にグラフ上の合意モデルと呼ばれるものを解析しています。合意モデルでは、各頂点が意見を持った無向連結グラフを考えます。各ラウンドで各頂点は隣接点と通信を行い、予め定められたプロトコルに従い意見を同時に更新します。プロトコルの目的は合意（つまり全頂点が同じ意見を持つ状態）に至ることで、それまでにかかるラウンド数が興味の対象となります。具体的にはpull voting, best-of-two, best-of-three などが非常に有名で、特に分散コンピューティングの文脈でよく研究されています。詳細はリンク先を参照してください。
幾つかの既存結果では best-of-two や best-of-three といった特定のモデルに対してそれぞれアドホックに解析がなされていましたが、本研究の最大の特徴はこれらのモデルを含む幅広い合意モデルのクラス quasi-majority functional voting と呼ばれる合意モデルを提案したことにあります。そして、この広いクラスに属する合意モデルがエキスパンダーグラフ上だと高速 ($O(\log n)$ ラウンド) に合意に至ることを証明しました。
簡単なアイデア
今回は各頂点が二種類$A,B$どちらかの意見を持つケースを考えています。このとき、合意モデルは $2^V$ 上のマルコフ連鎖と見なせます。しかし、完全グラフ上だと $A$の意見を持つ人数にだけ着目すればよくなるので、マルコフ連鎖の状態空間は $\{0,\ldots,|V(G)|\}$ とできるので解析が一気に簡単になります。エキスパンダーグラフ上の合意モデルは、厳密には $2^V$ 上のマルコフ連鎖ですが、実は $\{0,\ldots,|V(G)|\}$上のマルコフ連鎖に「近似」できることを証明しました。この話は best-of-two では既に知られており、Expander Mixing Lemma を用いることで証明できるのですが, この研究ではそれを拡張したいわば "Nonlinear Expander Mixing Lemma" のようなものを証明し、それを利用して幅広い合意モデルの解析に応用しました。
議論をするたびに共著者様がすごく非自明な式変形を涼しい顔で繰り出してこられたのがとても面白かったです（ありがとうございました）
0 件のコメント:
コメントを投稿