Lower bounds for randomized mutual exclusion
Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman · 1993
We establish, for the first time, lower bounds for randomized mutual-exclusion algorithms (with a read-modify-write operation). Our main result is that a constant size shared-variable cannot guarantee strong fairness, even if randomization is allowed. In fact, we prove a lower bound of\\Omega\\Gamma/46 log n) bits on the size of the shared-variable, which is also tight. We investigate weaker fairness conditions and derive tight (upper and lower) bounds for them as well. Surprisingly, it turns out that slightly weakening the fairness condition results in an exponential reduction in the size of the required shared-variable. Our lower bounds rely on an analysis of Markovchains, that may be of interest on its own and may have applications elsewhere. Keywords: Mutual Exclusion, Randomized Distributed Algorithms, Markov-Chains, Lower-Bounds. 1 Introduction Randomization has played an important role in the design and understanding of distributed algorithms. It is a natural tool which is usual...