A time complexity lower bound for adaptive mutual exclusion

Afek, Y., Attiya, H., Fouren, A., Stupp, G., Touitou, D.: Long-lived renaming made adaptive. In: Proceedings of the 18th Annual ACM Symposium on Principles of Distributed Computing, pp. 91–103. ACM, May 1999

Afek, Y., Boxer, P., Touitou, D.: Bounds on the shared memory requirements for long-lived and adaptive objects. In: Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing, pp. 81–89. ACM, July 2000

Afek Y., Stupp G., Touitou D.: Long-lived adaptive splitter and applications. Distrib. Comput. 15(2), 67–86 (2002)

Anderson J., Kim Y.-J.: An improved lower bound for the time complexity of mutual exclusion. Distrib. Comput. 15(4), 221–253 (2003)

Anderson J., Kim Y.-J., Herman T.: Shared-memory mutual exclusion: major research trends since 1986. Distrib. Comput. 16, 75–110 (2003)

Anderson J., Yang J.-H.: Time/contention tradeoffs for multiprocessor synchronization. Inf. Comput. 124(1), 68–84 (1996)

Attiya H., Bortnikov V.: Adaptive and efficient mutual exclusion. Distrib. Comput. 15, 177–189 (2002)

Attiya H., Guerraoui R., Hendler D., Kuznetsov P.: The complexity of obstruction-free implementations. J. ACM. 56, 1–33 (2009) (article 24)

Attiya, H., Hendler, D., Woelfel, P.: Tight RMR lower bounds for mutual exclusion and other problems. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 217–226. ACM, May 2008

Bhatt, V., Huang, C.-C.: Group mutual exclusion in O(log n) RMR. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC ’10, pp. 45–54. ACM (2010)

Bhatt, V., Jayanti, P.: Constant RMR solutions to reader writer synchronization. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC ’10, pp. 468–477. ACM (2010)

Bhatt, V., Jayanti, P.: Specification and constant RMR algorithm for phase-fair reader-writer lock. In: Distributed Computing and Networking, vol. 6522 of Lecture Notes in Computer Science, pp. 119–130. Springer, Berlin (2011)

Burns, J., Lynch, N.: Mutual exclusion using indivisible reads and writes. In: Proceedings of the 18th Annual Allerton Conference on Communication, Control, and Computing, pp. 833–842 (1980)

Burns J., Lynch N.: Bounds on shared memory for mutual exclusion. Inf. Comput. 107(2), 171–184 (1993)

Choy M., Singh A.: Adaptive solutions to the mutual exclusion problem. Distrib. Comput. 8(1), 1–17 (1994)

Cypher, R.: The communication requirements of mutual exclusion. In: Proceedings of the Seventh Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 147–156. ACM, June 1995

Danek, R.: The k-bakery: local-spin k-exclusion using non-atomic reads and writes. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC ’10, pp. 36–44. ACM (2010)

Danek R., Golab W.: Closing the complexity gap between FCFS mutual exclusion and mutual exclusion. Distrib. Comput. 23, 87–111 (2010)

Danek, R., Hadzilacos, V.: Local-spin group mutual exclusion algorithms. In: Proceedings of the 18th International Symposium on Distributed Computing, vol. 3274 of Lecture Notes in Computer Science, pp. 71–85. Springer, Berlin (2004)

Fan, R., Lynch, N.: An Ω(n log n) lower bound on the cost of mutual exclusion. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, PODC ’06, pp. 275–284. ACM (2006)

Golab, W.: A complexity separation between the cache-coherent and distributed shared memory models. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, PODC ’11, pp. 109–118. ACM (2011)

Golab, W., Hadzilacos, V., Hendler, D., Woelfel, P.: Constant-RMR implementations of CAS and other synchronization primitives using read and write operations. In: Proceedings of the 26th annual ACM symposium on Principles of distributed computing, PODC ’07, pp. 3–12. ACM (2007)

Golab W., Hendler D., Woelfel P.: An O(1) RMRs leader election algorithm. SIAM J. Comput. 39(7), 2726–2760 (2010)

Hendler, D., Woelfel, P.: Adaptive randomized mutual exclusion in sub-logarithmic expected time. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC ’10, pp. 141–150. ACM (2010)

Hendler D., Woelfel P.: Randomized mutual exclusion with sub-logarithmic RMR-complexity. Distrib. Comput. 24, 3–19 (2011)

Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: double-ended queues as an example. In: Proceedings of the 23rd IEEE International Conference on Distributed Computing Systems, pp. 522–529, May 2003

Jayanti, P.: f-arrays: implementation and applications. In: Proceedings of the Twenty-first Annual Symposium on Principles of Distributed Computing, PODC ’02, pp. 270–279. ACM (2002)

Jayanti, P.: Adaptive and efficient abortable mutual exclusion. In: Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing, pp. 295–304. ACM (2003)

Keane, P., Moir, M.: A simple, local-spin group mutual exclusion algorithm. In: Proceedings of the 18th Annual ACM Symposium on Principles of Distributed Computing, pp. 23–32. ACM, May 1999

Kim, Y.-J., Anderson, J.: A time complexity bound for adaptive mutual exclusion. In: Proceedings of the 15th International Symposium on Distributed Computing, Lecture Notes in Computer Science, vol. 2180, pp. 1–15. Springer, October 2001

Kim Y.-J., Anderson J.: Adaptive mutual exclusion with local spinning. Distrib. Comput. 19(3), 197–236 (2007)

Lee, H.: Transformations of mutual exclusion algorithms from the cache-coherent model to the distributed shared memory model. In: Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, 2005. ICDCS 2005. pp. 261 –270, June 2005

Mellor-Crummey J., Scott M.: Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst. 9(1), 21–65 (1991)

Merritt M., Taubenfeld G.: Speeding Lamport’s fast mutual exclusion algorithm. Inf. Process. Lett. 45, 137–142 (1993)

Styer, E.: Improving fast mutual exclusion. In: Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing, pp. 159–168. ACM, August 1992

Styer, E., Peterson, G.: Tight bounds for shared memory symmetric mutual exclusion. In: Proceedings of the 8th Annual ACM Symposium on Principles of Distributed Computing, pp. 177–191. ACM, August 1989

Taubenfeld, G.: The black-white bakery algorithm and related bounded-space, adaptive, local-spinning and FIFO algorithms. In: Proceedings of the 18th International Symposium on Distributed Computing, vol. 3274 of Lecture Notes in Computer Science, pp. 56–70. Springer, Berlin (2004)

Turán P.: On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok 48, 436–452 (1941)

Yang J.-H., Anderson J.: A fast, scalable mutual exclusion algorithm. Distrib. Comput. 9(1), 51–60 (1995)