Broadcast and gossip in line-communication mode

DOI10.1016/S0166-218X(97)00054-1MaRDI QIDQ1382273zbMATH OpenFDO

Authors Christian Laforest

Publication date 1 November 1998

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

broadcastgossipline-communication networktrees

Mathematics Subject Classification ID

Trees (05C05) Applications of graph theory (05C90)

Review text

In a line-communication network, two nodes can communicate directly via a path in a single time step and different pairs of nodes can do so provided edge-disjoint paths are used. In the broadcast problem one node has a piece of information which is to be transmitted to all nodes; in the gossip problem each node has a distinct piece of information and all such pieces are to be transmitted to all nodes. The paper gives a simple proof of Farley's result that the broadcast time is \(\lceil \log_2 n\rceil\) steps in a connected network with \(n\) nodes. For the gossip problem upper and lower bounds are given for the gossip time for connected graphs and for trees. Gossip algorithms are constructed for trees and are shown to be optimal or asymptotically optimal. Also trees are constructed in which gossip is possible in \(\lceil \log_2n \rceil\) steps.

Recommendations

• Optimal algorithms for broadcast and gossip in the edge-disjoint path modes
• Optimal algorithms for broadcast and gossip in the edge-disjoint modes
• A survey of gossiping and broadcasting in communication networks
• Gossiping in Minimal Time

Cites work

• A survey of gossiping and broadcasting in communication networks
• Graph theory with applications
• Line broadcasting in cycles
• Methods and problems of communication in usual networks
• Minimum-time line broadcast networks
• New gossips and telephones
• Optimal algorithms for broadcast and gossip in the edge-disjoint path modes

Cited in

(30)

• The addition game: An abstraction of a communication problem
• Set to set broadcasting in communication networks
• Fast information sharing in a complete network
• Methods and problems of communication in usual networks
• Periodic gossiping on trees
• Note on optimal gossiping in some weak-connected graphs
• Periodic gossiping in back-to-back trees
• Better bounds for perpetual gossiping
• Gossiping and broadcasting versus computing functions in networks.
• Hierarchical broadcast and gossip networks
• On linear-time data dissemination in dynamic rooted trees
• Faster gossiping on butterfly networks
• A study of minimum gossip graphs
• Gossip Latin square and the meet-all gossipers problem
• Minimum linear gossip graphs and maximal linear \((\Delta,k)\)-gossip graphs
• Neighborhood Communications in Networks
• Information spreading by mobile particles on a line
• A survey of gossiping and broadcasting in communication networks
• Fast Gossiping for the Hypercube
• All-to-all broadcast problem of some classes of graphs under the half duplex all-port model
• Time and Cost Trade-Offs in Gossiping
• Line-broadcasting in complete k-ary trees
• Fast gossiping by short messages
• Lower Bounds on the Broadcasting and Gossiping Time of Restricted Protocols
• scientific article; zbMATH DE number 2146643 (Why is no real title available?)
• Minimum gossip bus networks
• Convergence of periodic gossiping algorithms
• Odd gossiping
• Gossiping in chordal rings under the line model
• Label-connected graphs and the gossip problem

This page was built for publication: Broadcast and gossip in line-communication mode

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