{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T09:10:33Z","timestamp":1720775433819},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2011,12,1]],"date-time":"2011-12-01T00:00:00Z","timestamp":1322697600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2012,1]]},"DOI":"10.1007\/s00446-011-0152-6","type":"journal-article","created":{"date-parts":[[2011,12,1]],"date-time":"2011-12-01T20:03:33Z","timestamp":1322769813000},"page":"271-297","source":"Crossref","is-referenced-by-count":6,"title":["A time complexity lower bound for adaptive mutual exclusion"],"prefix":"10.1007","volume":"24","author":[{"given":"Yong-Jik","family":"Kim","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James H.","family":"Anderson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,12,1]]},"reference":[{"key":"152_CR1","doi-asserted-by":"crossref","unstructured":"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\u2013103. ACM, May 1999","DOI":"10.1145\/301308.301335"},{"key":"152_CR2","doi-asserted-by":"crossref","unstructured":"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\u201389. ACM, July 2000","DOI":"10.1145\/343477.343523"},{"issue":"2","key":"152_CR3","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/s004460100060","volume":"15","author":"Y. Afek","year":"2002","unstructured":"Afek Y., Stupp G., Touitou D.: Long-lived adaptive splitter and applications. Distrib. Comput. 15(2), 67\u201386 (2002)","journal-title":"Distrib. Comput."},{"issue":"4","key":"152_CR4","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s00446-002-0084-2","volume":"15","author":"J. Anderson","year":"2003","unstructured":"Anderson J., Kim Y.-J.: An improved lower bound for the time complexity of mutual exclusion. Distrib. Comput. 15(4), 221\u2013253 (2003)","journal-title":"Distrib. Comput."},{"key":"152_CR5","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s00446-003-0088-6","volume":"16","author":"J. Anderson","year":"2003","unstructured":"Anderson J., Kim Y.-J., Herman T.: Shared-memory mutual exclusion: major research trends since 1986. Distrib. Comput. 16, 75\u2013110 (2003)","journal-title":"Distrib. Comput."},{"issue":"1","key":"152_CR6","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1006\/inco.1996.0006","volume":"124","author":"J. Anderson","year":"1996","unstructured":"Anderson J., Yang J.-H.: Time\/contention tradeoffs for multiprocessor synchronization. Inf. Comput. 124(1), 68\u201384 (1996)","journal-title":"Inf. Comput."},{"key":"152_CR7","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s004460100068","volume":"15","author":"H. Attiya","year":"2002","unstructured":"Attiya H., Bortnikov V.: Adaptive and efficient mutual exclusion. Distrib. Comput. 15, 177\u2013189 (2002)","journal-title":"Distrib. Comput."},{"key":"152_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1538902.1538908","volume":"56","author":"H. Attiya","year":"2009","unstructured":"Attiya H., Guerraoui R., Hendler D., Kuznetsov P.: The complexity of obstruction-free implementations. J. ACM. 56, 1\u201333 (2009) (article 24)","journal-title":"J. ACM."},{"key":"152_CR9","doi-asserted-by":"crossref","unstructured":"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\u2013226. ACM, May 2008","DOI":"10.1145\/1374376.1374410"},{"key":"152_CR10","doi-asserted-by":"crossref","unstructured":"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 \u201910, pp. 45\u201354. ACM (2010)","DOI":"10.1145\/1835698.1835708"},{"key":"152_CR11","doi-asserted-by":"crossref","unstructured":"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 \u201910, pp. 468\u2013477. ACM (2010)","DOI":"10.1145\/1835698.1835803"},{"key":"152_CR12","doi-asserted-by":"crossref","unstructured":"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\u2013130. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-17679-1_11"},{"key":"152_CR13","unstructured":"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\u2013842 (1980)"},{"issue":"2","key":"152_CR14","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1006\/inco.1993.1065","volume":"107","author":"J. Burns","year":"1993","unstructured":"Burns J., Lynch N.: Bounds on shared memory for mutual exclusion. Inf. Comput. 107(2), 171\u2013184 (1993)","journal-title":"Inf. Comput."},{"issue":"1","key":"152_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02283567","volume":"8","author":"M. Choy","year":"1994","unstructured":"Choy M., Singh A.: Adaptive solutions to the mutual exclusion problem. Distrib. Comput. 8(1), 1\u201317 (1994)","journal-title":"Distrib. Comput."},{"key":"152_CR16","doi-asserted-by":"crossref","unstructured":"Cypher, R.: The communication requirements of mutual exclusion. In: Proceedings of the Seventh Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 147\u2013156. ACM, June 1995","DOI":"10.1145\/215399.215434"},{"key":"152_CR17","doi-asserted-by":"crossref","unstructured":"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 \u201910, pp. 36\u201344. ACM (2010)","DOI":"10.1145\/1835698.1835707"},{"key":"152_CR18","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s00446-010-0096-2","volume":"23","author":"R. Danek","year":"2010","unstructured":"Danek R., Golab W.: Closing the complexity gap between FCFS mutual exclusion and mutual exclusion. Distrib. Comput. 23, 87\u2013111 (2010)","journal-title":"Distrib. Comput."},{"key":"152_CR19","doi-asserted-by":"crossref","unstructured":"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\u201385. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-30186-8_6"},{"key":"152_CR20","doi-asserted-by":"crossref","unstructured":"Fan, R., Lynch, N.: An \u03a9(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 \u201906, pp. 275\u2013284. ACM (2006)","DOI":"10.1145\/1146381.1146423"},{"key":"152_CR21","doi-asserted-by":"crossref","unstructured":"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 \u201911, pp. 109\u2013118. ACM (2011)","DOI":"10.1145\/1993806.1993822"},{"key":"152_CR22","doi-asserted-by":"crossref","unstructured":"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 \u201907, pp. 3\u201312. ACM (2007)","DOI":"10.1145\/1281100.1281105"},{"issue":"7","key":"152_CR23","doi-asserted-by":"crossref","first-page":"2726","DOI":"10.1137\/070686445","volume":"39","author":"W. Golab","year":"2010","unstructured":"Golab W., Hendler D., Woelfel P.: An O(1) RMRs leader election algorithm. SIAM J. Comput. 39(7), 2726\u20132760 (2010)","journal-title":"SIAM J. Comput."},{"key":"152_CR24","doi-asserted-by":"crossref","unstructured":"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 \u201910, pp. 141\u2013150. ACM (2010)","DOI":"10.1145\/1835698.1835737"},{"key":"152_CR25","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00446-011-0128-6","volume":"24","author":"D. Hendler","year":"2011","unstructured":"Hendler D., Woelfel P.: Randomized mutual exclusion with sub-logarithmic RMR-complexity. Distrib. Comput. 24, 3\u201319 (2011)","journal-title":"Distrib. Comput."},{"key":"152_CR26","unstructured":"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\u2013529, May 2003"},{"key":"152_CR27","doi-asserted-by":"crossref","unstructured":"Jayanti, P.: f-arrays: implementation and applications. In: Proceedings of the Twenty-first Annual Symposium on Principles of Distributed Computing, PODC \u201902, pp. 270\u2013279. ACM (2002)","DOI":"10.1145\/571873.571875"},{"key":"152_CR28","doi-asserted-by":"crossref","unstructured":"Jayanti, P.: Adaptive and efficient abortable mutual exclusion. In: Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing, pp. 295\u2013304. ACM (2003)","DOI":"10.1145\/872035.872079"},{"key":"152_CR29","doi-asserted-by":"crossref","unstructured":"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\u201332. ACM, May 1999","DOI":"10.1145\/301308.301319"},{"key":"152_CR30","doi-asserted-by":"crossref","unstructured":"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\u201315. Springer, October 2001","DOI":"10.1007\/3-540-45414-4_1"},{"issue":"3","key":"152_CR31","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/s00446-006-0009-6","volume":"19","author":"Y.-J. Kim","year":"2007","unstructured":"Kim Y.-J., Anderson J.: Adaptive mutual exclusion with local spinning. Distrib. Comput. 19(3), 197\u2013236 (2007)","journal-title":"Distrib. Comput."},{"key":"152_CR32","unstructured":"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 \u2013270, June 2005"},{"issue":"1","key":"152_CR33","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1145\/103727.103729","volume":"9","author":"J. Mellor-Crummey","year":"1991","unstructured":"Mellor-Crummey J., Scott M.: Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst. 9(1), 21\u201365 (1991)","journal-title":"ACM Trans. Comput. Syst."},{"key":"152_CR34","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0020-0190(93)90015-2","volume":"45","author":"M. Merritt","year":"1993","unstructured":"Merritt M., Taubenfeld G.: Speeding Lamport\u2019s fast mutual exclusion algorithm. Inf. Process. Lett. 45, 137\u2013142 (1993)","journal-title":"Inf. Process. Lett."},{"key":"152_CR35","doi-asserted-by":"crossref","unstructured":"Styer, E.: Improving fast mutual exclusion. In: Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing, pp. 159\u2013168. ACM, August 1992","DOI":"10.1145\/135419.135453"},{"key":"152_CR36","doi-asserted-by":"crossref","unstructured":"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\u2013191. ACM, August 1989","DOI":"10.1145\/72981.72993"},{"key":"152_CR37","doi-asserted-by":"crossref","unstructured":"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\u201370. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-30186-8_5"},{"key":"152_CR38","first-page":"436","volume":"48","author":"P. Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n P.: On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok 48, 436\u2013452 (1941)","journal-title":"Mat. Fiz. Lapok"},{"issue":"1","key":"152_CR39","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF01784242","volume":"9","author":"J.-H. Yang","year":"1995","unstructured":"Yang J.-H., Anderson J.: A fast, scalable mutual exclusion algorithm. Distrib. Comput. 9(1), 51\u201360 (1995)","journal-title":"Distrib. Comput."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-011-0152-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-011-0152-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-011-0152-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T04:58:14Z","timestamp":1561006694000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-011-0152-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12,1]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["152"],"URL":"https:\/\/doi.org\/10.1007\/s00446-011-0152-6","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12,1]]}}}