关于gossip的网络的通信次数分析
gossip网络中,如果是图结构,
上面的图,假设每个人都掌握一个秘密,那么通过多少次交流过后,这些秘密能被所以人知道呢?
先1-4交流,这样1和4都掌握了1、4消息,同理,2和3交流,这样2和3节点都掌握2、3信息
然后通过1和3交流、2和4交流,这样通过4次交流,每个人掌握的秘密就可以被分享了
这有f(1) =0 ; f(2)=1; f(3)=2n - 3 n>=3
如果是树,
如果是树的话,先把2-4 2-5 通信 3-6 3-7 通信, 1-2 1-3 通信,
再把1-2 2-3 2-5 3-6 3-7 总结11次通信
总结f(1)=0; f(n) = 2n- 3 n>=2.
这样消息就可以被传播到所有节点了