Gossiping and Set-to-Set Broadcasting in Weighted Graphs

Abstract

Set-to-Set Broadcasting is an information distribution problem in a connected graph, $G=(V,E)$, in which a set of vertices $A$, called originators, distributes messages to a set of vertices $B$ called receivers, such that by the end of the broadcasting process each receiver has received the messages of all the originators. This is done by placing a series of calls among the communication lines of the graph. Each call takes place between two adjacent vertices, which share all the messages they have. Gossiping is a special case of set-to-set broadcasting, where $A=B=V$. We use $F(A,B,G)$ to denote the length of the shortest sequence of calls that completes the set-to-set broadcast from a set $A$ of originators to a set $B$ of receivers, within a connected graph $G$. $F(A,B,G)$ is also called the cost of an algorithm. We present bounds on $F(A,B,G)$ for weighted and for non-weighted graphs.