{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:20Z","timestamp":1787337500051,"version":"build-2736575974"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>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 (\\log\\log n)$ bits on the size of the shared variable, which is also tight.<\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1137\/s009753979426513x","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1550-1563","source":"Crossref","is-referenced-by-count":1,"title":["Lower Bounds for Randomized Mutual Exclusion"],"prefix":"10.1137","volume":"27","author":[{"given":"Eyal","family":"Kushilevitz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael O.","family":"Rabin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Zuckerman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90002-G"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Ben\u2010Or,\n                      Another advantage of free choice: Complete asynchronous agreement protocols\n                      , in Proc. 6th ACM Symp. on Principles of Distributed Computing, 1983, pp. 27\u201330.","DOI":"10.1145\/800221.806707"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322302"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"G. Bracha,\n                      An O(logn) expected rounds randomized byzantine generals protocol\n                      , in Proc. 17th ACM Symp. on Theory of Computing, 1985, pp. 316\u2013326.","DOI":"10.1145\/22145.22180"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"B. Chor, A. Israeli, and M. Li,\n                      On process coordination using asynchronous hardware\n                      , in Proc. 6th ACM Symp. on Principles of Distributed Computing, 1987, pp. 86\u201397.","DOI":"10.1145\/41840.41848"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/365559.365617"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90033-3"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"P. Feldman and S. Micali,\n                      Optimal algorithms for byzantine agreement\n                      , in Proc. 20th ACM Symp. on Theory of Computing, 1985, pp. 148\u2013161.","DOI":"10.1145\/62212.62225"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"R. L. Graham and A. C. Yao,\n                      On the improbability of reaching byzantine agreements\n                      , in Proc. 21st ACM Symp. on Theory of Computing, 1989, pp. 467\u2013478.","DOI":"10.1145\/73007.73052"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"A. Itai and M. Rodeh,\n                      The lord of the ring, or probabilistic methods for breaking symmetry in distributed networks\n                      , in Proc. 22th IEEE Symp. on Foundations of Computer Science, 1981, pp. 150\u2013158.","DOI":"10.1109\/SFCS.1981.41"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and M. O. Rabin,\n                      Randomized mutual exclusion algorithms revisited\n                      , in Proc. 11th ACM Symp. on Principles of Distributed Computing, 1992, pp. 275\u2013283.","DOI":"10.1145\/135419.135468"},{"key":"R13","unstructured":"A. Karlin and A. C. Yao,\n                      Probabilistic Lower Bounds for Byzantine Agreement\n                      , unpublished manuscript, 1984."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"D. Lehman and M. O. Rabin,\n                      On the advantage of free choice: A symmetric and fully distributed solution to the dining philosophers problem\n                      , in Proc. 8th ACM Symp. on Principles of Programming Languages, 1981, pp. 133\u2013138.","DOI":"10.1145\/567532.567547"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90010-1"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"I. Saias,\n                      Proving probabilistic correctness statements: The case of Rabin`s algorithm for mutual exclusion\n                      , in Proc. 11th ACM Symp. on Principles of Distributed Computing, 1992, pp. 263\u2013272.","DOI":"10.1145\/135419.135466"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"A. C. Yao,\n                      Probabilistic computations: Toward a unified measure of complexity\n                      , in Proc. 18th IEEE Symp. on Foundations of Computer Science, 1977, pp. 222\u2013227.","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S009753979426513X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:11Z","timestamp":1787336051000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S009753979426513X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":17,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S009753979426513X"],"URL":"https:\/\/doi.org\/10.1137\/s009753979426513x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}