Polylog randomized wait-free consensus
Tushar Deepak Chandra · 1996
I present the first randomized wait-free implementation of consensus from multiple writer zmltiple reader register in which each process takes polylog (0(log2 n)) 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.Even though different processes may concurrently access a shared object, it is desirable that the object behave as if all these accesses occur in some sequential order.More precisely, the behavior of a shared object must be keaTizab/e [H W90].one way to ensure