PIMS-UManitoba Distinguished Lecture: Faith Ellen

  • Date: 10/20/2016
  • Time: 16:00
Faith Ellen (University of Toronto)

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.

Other Information: 


Location: Robert B. Schultz Lecture Theatre