Dynamic gossip

DOI10.1007/S41980-018-0160-4zbMATH Open1421.68004arXiv1511.00867OpenAlexW2795812506MaRDI QIDQ2415893FDOQ2415893

Authors: Jan van Eijck, Pere Pardo, Rahim Ramezanian, François Schwarzentruber, Hans van Ditmarsch 

Publication date: 23 May 2019

Published in: Bulletin of the Iranian Mathematical Society (Search for Journal in Brave)

Abstract: A gossip protocol is a procedure for spreading secrets among a group of agents, using a connection graph. The goal is for all agents to get to know all secrets, in which case we call the execution of the protocol successful. We consider distributed and dynamic gossip protocols. In distributed gossip the agents themselves instead of a global scheduler determine whom to call. In dynamic gossip not only secrets are exchanged but also telephone numbers (agent identities). This results in increased graph connectivity. We define six such distributed dynamic gossip protocols, and we characterize them in terms of the topology of the graphs on which they are successful, wherein we distinguish strong success (the protocol always terminates, possibly assuming fair scheduling) from weak success (the protocol sometimes terminates). For five of these protocols strong (fair) and weak success are characterized by weakly connected graphs. This result is surprising because the protocols are fairly different. In the sixth protocol an agent may only call another agent if it does not know the other agent's secret. Strong success for this protocol is characterized by graphs for which the set of non-terminal nodes is strongly connected. Weak success for this protocol is characterized by weakly connected graphs satisfying further topological constraints that we define in the paper. One direction of this characterization is surprisingly harder to prove than the other results in this contribution.

Full work available at URL: https://arxiv.org/abs/1511.00867

Recommendations

• Gossip in dynamic networks
• Epistemic protocols for dynamic gossip
• scientific article; zbMATH DE number 7440211
• Reachability and expectation in gossiping

zbMATH Keywords

characterizationdistributed systemterminationgossip protocol

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Network protocols (68M12)

Cites Work

• Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
• A survey of gossiping and broadcasting in communication networks
• Title not available (Why is that?)
• New gossips and telephones
• The communication problem on graphs
• Title not available (Why is that?)
• Epistemic protocols for dynamic gossip
• Title not available (Why is that?)
• A Cure for the Telephone Disease
• Gossips and telephones
• A Problem with Telephones
• Resource discovery in distributed networks
• Simple, fast and deterministic gossip and rumor spreading
• Title not available (Why is that?)
• Discovery through gossip
• Reachability and expectation in gossiping
• The pleasure of gossip
• Quasirandom rumor spreading
• Random exchanges of information
• Random exchanges of information

Cited In (17)

• Gossip in dynamic networks
• On gossip and populations
• Towards an analysis of dynamic gossip in Net\textsc{kat}
• Title not available (Why is that?)
• The logic of gossiping
• Tolerating malicious gossip
• Sub-linear universal spatial gossip protocols
• Correctness of a gossip based membership protocol
• Correctness of gossip-based membership under message loss
• An online distributed gossiping protocol for mobile networks
• Request-based gossiping without deadlocks
• Correctness of gossip-based membership under message loss
• Title not available (Why is that?)
• The dynamics of loose talk
• Confidential gossip
• Title not available (Why is that?)
• Intelligent Gossip

This page was built for publication: Dynamic gossip

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2415893)