BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Deterministic Objects: Life Beyond Consensus Ellen, Faith


For all integers $m \geq 2$, we construct an infinite sequence of deterministic objects of consensus number $m$ with strictly increasing computational power. In particular, this refutes the Common2 Conjecture, which claimed that every deterministic object of consensus number 2 has a deterministic, wait-free implementation from 2-consensus objects and registers in a system with any finite number of processes.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International