Title: Algorithms for Broadcast and Multicast
Speaker:  Yong-Chun Justin Wan
Google


Date: Friday,  March 24, 2006
Time 11-12 
Venue: Room 3464 , HKUST   


Abstract:
  
Broadcasting is a classical problem that has been widely studied for
decades. One source node wishes to broadcast a message to every other
node. We study generalizations of broadcasting to the situation when
the source node has several pieces of data to broadcast or multicast.
Moreover, each piece of data may have a different destination
set. Communication typically proceeds in rounds, and in each round
each node can send (receive) a message to (from) one other node. The
objective is to minimize the number of rounds. We present a near
optimal algorithm for this problem.

In addition we develop broadcast and multicast algorithms for a more
complex communication model, where the nodes are arranged in clusters.
In this model, sending a message from one node to another node in the
same cluster takes one round, and sending a message to a node in a
different cluster takes C rounds. We develop a simple and efficient
approximation algorithm for this model. We then extend the model to
more complex models where we remove the assumption that an unbounded
amount of simultaneous communication may happen using the global
network. Finally, we discuss broadcasting algorithms for the postal
model where the sending node does not block for C rounds when the
message is in transit.

Bio:
Dr. Yung-Chun Justin Wan received his Ph.D. and M.Sc. degree in
Computer Science from the University of Maryland at College Park in
2005 and 2001, respectively, and received his B.Sc. degree from the
Chinese University of Hong Kong. He is interested in designing
algorithms with applications in networks, and specifically algorithms
for data transfer problems arising in communication networks. He
interned at Xerox PARC and Bell Labs, and is now working at Google
Inc., focusing on web-spam fighting.