An Arabic Slot Grammar parser
Michael C. McCord, Violetta Cavalli-Sforza
ACL 2007
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 Ω(log 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 Markov chains that may be of interest on its own and may have applications elsewhere. © 1998 Society for Industrial and Applied Mathematics.
Michael C. McCord, Violetta Cavalli-Sforza
ACL 2007
Yigal Hoffner, Simon Field, et al.
EDOC 2004
Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010
Victor Valls, Panagiotis Promponas, et al.
IEEE Communications Magazine