broadcasting

Consider a broadcast scheme on a connected graph from an originator vertex v in a graph G consisting of a sequence of parallel calls starting from v. In each time step, every informed node (sender) can call at most one uninformed neighbor (receiver), corresponding to a directed edge. The process is iterated until every vertex in the network is informed, with the result being a directed spanning tree of G rooted at v called the broadcast tree of originator v. The minimum number of time steps required to broadcast from v to all vertices in the graph G is called the broadcast time of vertex v, denoted b(G;v). The maximum broadcast time over all originator vertices in G is called the broadcast time of G, denoted b(G) (Harutyunyan1 and Li 2019).

gossiping | graph bandwidth