Asynchronous Consensus

Faith Ellen
Thu, Oct 20, 2016
PIMS, University of Manitoba
PIMS-UManitoba Distinguished Lecture
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.