The Complexity of Consensus and Set Agreement

演讲人: Faith Ellen University of Toronto
时间: 2019-11-20 15:00-2019-11-20 16:00
地点:FIT 1-222

Consensus is a fundamental problem in the theory of distributed computing. Research about consensus and its generalization, set agreement, has helped the theory of distributed computing community understand issues of computability and complexity, the power of randomness, and the importance of different termination conditions. This talk will survey a collection of classical and recent results about consensus and set agreement in shared-memory systems.


Faith Ellen is a Professor of Computer Science at the University of Toronto. Her research interest include the theory of distributed computing, data structures and complexity. She received her Ph.D. from the University of California, Berkeley, in 1982 under the supervision of Richard Karp. She joined the faculty of the University of Washington in 1983, and moved to Toronto in 1986. She became a Fellow of the Association for Computing Machinery in 2014. Faith  co-authored the book, “Impossibility Results for Distributed Computing”, which was published in 2014.