Conference paper
Conference paper
Polylog randomized wait-free consensus
Abstract
I present the first randomized wait-free implementation of consensus from multiple writer multiple reader register in which each process takes polylog (O(log2n)) expected steps. To achieve this result, I assume a non-standard type of adversary (from [Abr88]). I argue that this type of adversary (which is more powerful than the oblivious adversary, but weaker than the strong adversary) is powerful enough to model practical systems.
Related
Conference paper
On the impossibility of group membership
Conference paper