Colloquium Details
Faculty Search Colloquium: Lower Bounds in Distributed Computing
| Author: | Rui Fan University of Toronto |
|---|---|
| Date: | March 02, 2009 |
| Time: | 9:30 |
| Location: | 220 Deschutes |
| Host: | Jun Li |
Abstract
The recent transition to multicore personal computers has been a cause for both celebration and distress. On the one hand is the promise of multicore processors to extend Moore's Law into the next decade. On the other is the difficulty programmers have in taking full advantage of the concurrency that hardware provides. Theoretical distributed computing plays a key role in bridging this gap, by supplying both rigorous analyses and sound intuitions to deal with the difficulties underlying concurrency. This talk will focus on lower bounds for two fundamental problems in distributed computing. First, we describe a tight lower bound on the time complexity of mutual exclusion, resolving a longstanding open problem. Our proof uses a novel information theoretic technique with applications to other distributed computing problems. Second, we describe a new clock synchronization problem which captures the property of locality in radio networks. We describe a surprising lower bound for this problem, and its implications and extensions. Lastly, we will describe some ongoing work and interesting open problems.
Biography
Rui Fan received his Ph.D. in computer science from MIT in 2008, and is currently a postdoctoral fellow at the University of Toronto. His dissertation received the MIT Sprowls Award for best doctoral theses in computer science. He received his Bachelor of Science with honors in computer science and mathematics from Caltech. His research focuses on applying theoretical insights and techniques to practical problems in distributed computing. His work has been the recipient of two Best Student Paper awards from the ACM Principles of Distributed Computing conference.