Advertisement
Published in:
2017 | OriginalPaper | Chapter
Reachability and Expectation in Gossiping
Authors : Hans van Ditmarsch, Ioannis Kokkinis, Anders Stockmarr
Published in: PRIMA 2017: Principles and Practice of Multi-Agent Systems
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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}\).