הרצאה פומבית - Broadcasting in Computer Networks

Abstract:

Broadcasting in a network is a method of information distribution in a network, in which one element, called the originator, has to distribute a message to all other elements by placing a series of calls among the communication lines of the network. This is assumed to take place in discrete time units. The broadcasting has to be completed within a minimal number of time units. In my lecture I will present our work on the following problems: 

1. Minimal Broadcast Graphs - finding a minimum broadcast graph, with minimum number of edges, such that the broadcast from any originator completes within log n discrete time units. In my lecture I will present a new efficient construction for minimal broadcast graphs.

2. Line-broadcasting in complete k-ary trees. In the line model a vertex can transmit the message to any vertex in the graph through a path of any length in just one time unit. The cost of each call is the number of edges in the path. The cumulative cost of the broadcast is the sum of the cost of all calls. In this work, we present lower and upper linear bounds for the cumulative cost to broadcast in a complete k-ary tree from any vertex using the line-broadcasting model. 

3. Gossiping and set-to-set broadcasting in weighted and non-weighted graphs. In this problem a set of vertices A, distribute messages to a set of vertices B, such that by the end of the broadcasting process each vertex in B has received the messages of all the the vertices in A. Each call takes place between two adjacent vertices, which share all the messages they have. Gossiping is a particular case of set-to-set broadcasting, where A=B=V. We presented bounds on the number of calls needed to complete the set-to-set broadcast in a connected weighted graph G.

The speaker is a PhD student at the School of Computer Science and is supervised by Prof. Yehuda Roditty and Prof. Michael Tarsi