On the Importance of Having an Identity or, is Consensus really Universal?

Harry Buhrman, Alessandro Panconesi, Riccardo Silvestri +1

We show that Naming-- the existence of distinct IDs known to all-- is a hidden but necessary assumption of Herlihy's universality result for Consensus. We then show in a very preci…