Broadcast and gossip in line-communication mode (Q1382273)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Broadcast and gossip in line-communication mode |
scientific article |
Statements
Broadcast and gossip in line-communication mode (English)
0 references
1 November 1998
0 references
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.
0 references
line-communication network
0 references
broadcast
0 references
gossip
0 references
trees
0 references