IUB Information Technology Events

CS Colloquium: Valerie King, Department of Computer Science, University of Victoria

The School of Informatics, Computing, and Engineering (SICE) CS Colloquium Series - Distinguished Speaker Series

Speaker:  Valerie King, Department of Computer Science, University of Victoria

Where:  Luddy Hall, Rm. 1106 (Dorsey Learning Hall)

When:  Friday, April 26, 2019, 3:00 pm

Topic:  The Challenge of Broadcast or How many messages does it take to build a phone tree?

Abstract: The problem of  broadcasting in a distributed network is to transmit a single message from one node to every other  node. We assume each node knows its neighbors, and communication is by message-passing. For many years, the simple flooding algorithm was considered optimal but this requires a transmission across every edge. Since 2015, there has been substantial progress on this problem. Monte Carlo algorithms, for  synchronous and asynchronous networks can build a spanning tree (or minimum spanning tree) with a number of messages sublinear in the number of edges, for dense graphs. But Monte Carlo algorithms have a probability of error. Is a deterministic algorithm possible?

In this talk I’ll focus on recent work about a simplified version of the problem. It has led to a surprising graph sampling lemma and a new method for determining a spanning tree in an MPC model like hadoop or map-reduce.

Brief bio:  Valerie King is professor of computer science at the University of Victoria in Canada. She received her PhD in computer science and a JD from UC Berkeley. In 2014, she received the distinction of ACM Fellow for her work on randomized algorithms, especially dynamic graph algorithms and Byzantine fault-tolerant distributed computing.




Friday April 26, 2019 03:00 PM
Friday April 26, 2019 04:00 PM
Funda Ergun
Contact Email