理系学生日記

おまえはいつまで学生気分なのか

ConsulやSerfのGosippingにより情報はどれだけ速く伝わるのか

protocol

Consul や Serf でも、Gossiping と呼ばれる通信方式が良く使われます。

Gossiping というのはなにかというのは wikipedia:en:Gossip_protocol にもまとめられています。 オフィスにおいては、情報を持っている人がウォータークーラーの前で会った人にランダムでその情報を伝え、それがまた他の人に伝わっていくという情報の流れを模したものになります。 置き換えると、任意のノードがランダムに情報を伝えるノードを選び、情報を伝えながら伝搬するという流れになります。

情報を全ノードに伝搬させたいのにも関わらず、ランダムに選ぶだけでその目的が達成させられるのか。そして、達成させられるのだとすればどのくらいの時間で達成させられるのかは、Gossiping を行う以上は気になるところだと思います。

このあたりを明確に伝えるためには、数理モデルを構築して、その上で解析をかけなければいけません。

SWIM の論文ではそのあたりはサクっと説明されています。 ただ、ぼくも「これってどういうことなんだっけ？？？」ってなったので、色々と調べてみました。 専門家ではないので、間違ってるところがあれば指摘してもらえるとうれしい。

Gossping の数理モデルは伝染病の伝搬モデル

Gossiping の数理モデルとして使われるのは、病気が人に伝染っていくモデルになります。実際に、Gossiping 系のプロトコルのことを epidemic (伝染性の) protocol と呼ぶこともあり、 このあたりの類似性は有名です。

この伝染病の数理モデルには結構色んなパターンがあります。 たとえば、病気に感染するけれど感染した人は一定時間で治り抗体を持つ、というのが wikipedia:SIRモデル です。 一方、感染して直った後にまた感染するような伝染病は SIS モデルと言われます。 ここでは、S:感受性者(Susceptible)、I:感染者(Infections)、R:除去者(Removed)を指すようです。

では、通信で Gossiping を使うときはどういうモデルになるのか。この場合、情報を持っている Agent が I (感染者)、持っていない人は S (感受性者) です。 情報を持つとそこで終わり (情報を敢えて揮発させることもあるでしょうが、ここではそれには与しません) なので、これは SI モデルと呼ばれるモデルで表現されます。

SI モデル

伝染病の数理モデルは、他の多くの数理モデルと同様に、微分方程式で表現されます。

時間 t における I (情報を持つ Agent) の数を I(t) で表すと、時間が進むことによるその数の変化はどう表されるでしょうか。

当然、感染者数 I(t) はその時点での感染者数 I(t) に比例します。だって、インフルエンザに罹った人が多いほど流行しますよね。 また、その時点で感染していない人の数 S(t) にも比例するでしょう。 というわけで、比例定数を \beta とすると、その数は

  • \frac{dI(t)}{dt}=\beta I(t)S(t)

で表現できることになります。また、全 Agent の数を N とすると、任意の時間 t で

  • N=S(t)+I(t)

が成立することは自明ですので、結果として、

  • \frac{dI(t)}{dt}=\beta I(t)(N-I(t))

と表現できます。I(t) の微分が定数と I(t) のみで表現されているので、解けそうですね。

では解いてみます

先の式 \frac{dI(t)}{dt}=\beta I(t)(N-I(t)) を式変異すると、

  • \frac{1}{I(t)\left(N-I(t)\right)}\frac{dI}{dt} = \beta dt

となり、変数分離で解ける形であることが分かります。というわけで両辺を積分します。

  • \int_{0}^{t} \frac{1}{I(t)\left(N-I(t)\right)}\frac{dI}{dt} = \int \beta dt

ここで、I(t)=u とおくと、\frac{dI(t)}{dt}=\frac{du}{dt} になります。 このとき、u の積分区間も I(0)\rightarrow I(t) となります。 これを先の式に代入すると、

  • \int_{I(0)}^{I(t)} \frac{1}{u(N-u)}\frac{du}{dt} = \int \beta dt

になります。(なんか右辺の積分区間を書くと数式として表示されない…)

左辺の分数部分は \frac{1}{N}\left(\frac{1}{u}+\frac{1}{N-u}\right) に分解できるので、これを鑑みると上の式は 以下のようになります。

  • \frac{1}{N}\left(\ln u-\ln(N-u)\right)_{I(u)}^{I(t)} = \beta t
    • \frac{1}{N}\left(\ln(I(t))-\ln(N-I(t))-\ln(I(0))+\ln(N-I(0))\right) = \beta t
    • \ln\left(\frac{I(t)}{I(0)}\frac{N-I(0)}{N-I(t)}\right)=\beta tN
    • \frac{I(t)}{I(0)}\frac{N-I(0)}{N-I(t)}=e^{\beta tN}

あとはこれを I(t) について解けば、

  • I(t)=\frac{I(0)N}{\left(N-I(0)\right)e^{-\beta tN}+I(0)}

という解が導けます。

ここで、一番最初に情報を持っている agent が 1 台であれば、I(0)=1 であるので、

  • I(t)=\frac{N}{\left(N-1\right)e^{-\beta tN}+1}

になります。

結果

これを N=100 の元でグラフ化してみます。 ぼくは理解できなかったのですが、論文中では \beta = 1-\left(1-\frac{1}{N}\right)^{2} になっているので、これをあてはめた結果が以下になります。

N=100

f:id:kiririmode:20180805103222p:plain

N=10000

f:id:kiririmode:20180805103235p:plain

まぁあたりまえですが、t\rightarrow \infty とすれば、感染者というか情報を受信する agent 数 I(t) は N に収束します。 I(t) の値の立ち上がりも結構はやくて、ちょっとだけ待てば 10,000 台の agent にも結構はやめに伝搬することがわかります。

というわけで

感染予防には気をつけましょう。