Asynchronous Consensus

Speaker: Faith Ellen

Date: Thu, Oct 20, 2016

Location: PIMS, University of Manitoba

Conference: PIMS-UManitoba Distinguished Lecture

Subject: Mathematics

Class: Scientific


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.