Dynamic gossip
From MaRDI portal
Publication:2415893
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.
Recommendations
Cites work
- A Cure for the Telephone Disease
- A Problem with Telephones
- A survey of gossiping and broadcasting in communication networks
- Discovery through gossip
- Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
- Epistemic protocols for dynamic gossip
- Gossips and telephones
- scientific article; zbMATH DE number 7440211 (Why is no real title available?)
- scientific article; zbMATH DE number 6747860 (Why is no real title available?)
- scientific article; zbMATH DE number 3358479 (Why is no real title available?)
- scientific article; zbMATH DE number 3390098 (Why is no real title available?)
- New gossips and telephones
- Quasirandom rumor spreading
- Random exchanges of information
- Random exchanges of information
- Reachability and expectation in gossiping
- Resource discovery in distributed networks
- Simple, fast and deterministic gossip and rumor spreading
- The communication problem on graphs
- The pleasure of gossip
Cited in
(20)- Towards an analysis of dynamic gossip in Net\textsc{kat}
- Request-based gossiping without deadlocks
- Dealing with unreliable agents in dynamic gossip
- Confidential gossip
- The logic of gossiping
- Reachability of five gossip protocols
- scientific article; zbMATH DE number 1696679 (Why is no real title available?)
- scientific article; zbMATH DE number 3849231 (Why is no real title available?)
- Sub-linear universal spatial gossip protocols
- On gossip and populations
- Intelligent Gossip
- Open problems in a logic of gossips
- The dynamics of loose talk
- Tolerating malicious gossip
- Correctness of gossip-based membership under message loss
- Correctness of a gossip based membership protocol
- Gossip in dynamic networks
- Correctness of gossip-based membership under message loss
- Strengthening gossip protocols using protocol-dependent knowledge
- An online distributed gossiping protocol for mobile networks
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)
