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.