PIMS-UManitoba Distinguished Lecture: Faith Ellen
- Date: 10/20/2016
- Time: 16:00
University of Manitoba
Asynchronous Consensus [video]
The consensus problem plays a central role in the theory of distributed computing. I will prove that consensus is impossible to solve in some asynchronous shared memory systems and I will present some algorithms for solving it in others, together with matching lower bounds on the amount of time and space needed. Consensus is universal: using consensus and read/write registers, I will show how to implement any shared object. The consensus hierarchy is used to classify the computational power of shared objects. I will conclude by discussing some limitations of this classification that have been recently discovered.
A video of this event is available on mathtube.org.
Location: Robert B. Schultz Lecture Theatre