Reachability and Expectation in Gossiping
Reachability and Expectation in Gossiping
复制标题
八卦中的可达性和期望
DOI：
10.1007/978-3-319-69131-2_6
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Stockmarr
中科院分区：
文献类型：
--
作者：
H. V. Ditmarsch;Ioannis Kokkinis;A. Stockmarr
我们给出了在完全连接网络上用于八卦的著名分布式协议的组合、计算和仿真结果。协议包括：进行任何呼叫（\(\mathsf {ANY}\)），只呼叫您不知道秘密的代理（“学习新秘密”\(\mathsf {LNS}\)），以及从不重复呼叫（“呼叫一次”\(\mathsf {CO}\)）。首先，我们将展示这些协议的不同之处在于它们的执行可以访问哪些机密分布。接下来，我们将\(\mathsf {ANY}\)和\(\mathsf {LNS}\)表示为马尔可夫链。我们提出了一种算法来生成这些马尔可夫链的状态，并计算协议预期持续时间的确切值。最后，我们通过模拟研究了\(\mathsf {LNS}\)的渐近行为，并将其与\(\mathsf {ANY}\)的已知结果进行了比较。
We give combinatorial, computational and simulation results for well-known distributed protocols for gossiping on completely connected networks. The protocols consist of: making any call (\(\mathsf {ANY}\)), only calling agents whose secret you do not know (“learn new secrets” \(\mathsf {LNS}\)), and never repeating calls (“call once” \(\mathsf {CO}\)). First, we show that these protocols all differ in what distributions of secrets are reachable by their execution. Next, we formulate \(\mathsf {ANY}\) and \(\mathsf {LNS}\) as Markov chains. We present an algorithm that generates the states of these Markov chains and computes the exact value of the expected duration of the protocols. Finally, we study the asymptotic behaviour of \(\mathsf {LNS}\) via simulations, and compare this to the known result for \(\mathsf {ANY}\).