{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T22:19:52Z","timestamp":1791238792914,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540201847","type":"print"},{"value":"9783540399896","type":"electronic"}],"license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39989-6_4","type":"book-chapter","created":{"date-parts":[[2011,1,8]],"date-time":"2011-01-08T02:01:57Z","timestamp":1294452117000},"page":"45-59","source":"Crossref","is-referenced-by-count":26,"title":["On the Uncontended Complexity of Consensus"],"prefix":"10.1007","author":[{"given":"Victor","family":"Luchangco","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Moir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nir","family":"Shavit","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Arora, N.S., Blumofe, R.D., Plaxton, C.G.: Thread scheduling for multipro-grammed multiprocessors. In: Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 119\u2013129 (1998)","DOI":"10.1145\/277651.277678"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Bershad, B.N.: Practical considerations for non-blocking concurrent objects. In: Proceedings 13th IEEE International Conference on Distributed Computing Systems, pp. 264\u2013273 (1993)","DOI":"10.1109\/ICDCS.1993.287700"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Garay, J., Hoepman, J., Moir, M.: Long-lived renaming made fast. In: Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing, pp. 194\u2013203 (1995)","DOI":"10.1145\/224964.224986"},{"issue":"5","key":"4_CR4","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1145\/290179.290183","volume":"45","author":"F. Fich","year":"1998","unstructured":"Fich, F., Herlihy, M., Shavit, N.: On the space complexity of randomized synchronization. Journal of the ACM\u00a045(5), 843\u2013862 (1998)","journal-title":"Journal of the ACM"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Fischer, M., Lynch, N., Paterson, M.: Impossibility of distributed consensus with one faulty process. Journal of the ACM, 374\u2013382 (1985)","DOI":"10.1145\/3149.214121"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Harris, T.L.: A pragmatic implementation of non-blocking linked lists. In: Proceedings of the 15th International Symposium on Distributed Computing (2001)","DOI":"10.1007\/3-540-45414-4_21"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Harris, T.L., Fraser, K., Pratt, I.A.: A practical multi-word compare-and-swap operation. In: Proceedings of 16th International Symposium on DIStributed Computing (2002)","DOI":"10.1007\/3-540-36108-1_18"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Hendler, D., Shavit, N.: Non-blocking steal-half work queues. In: Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing, pp. 280\u2013289 (2002)","DOI":"10.1145\/571873.571876"},{"issue":"1","key":"4_CR9","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/114005.102808","volume":"13","author":"M. Herlihy","year":"1991","unstructured":"Herlihy, M.: Wait-free synchronization. ACM Transactions on Programming Languages and Systems\u00a013(1), 124\u2013149 (1991)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"4_CR10","unstructured":"Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free software NCAS and transactional memory (2002) (unpublished manuscript)"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Luchangco, V., Moir, M.: The repeat offender problem: A mechanism for supporting lock-free dynamic-sized data structures. In: Proceedings of the 16th International Symposium on DIStributed Computing (2002); A improved version of this paper is in preparation for journal submission; please contact authors","DOI":"10.1007\/3-540-36108-1_23"},{"key":"4_CR12","unstructured":"Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: Double-ended queues as an example. In: Proceedings of the 23rd International Conference on Distributed Computing Systems (2003)"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Luchangco, V., Moir, M.: Space- and time-adaptive nonblocking algorithms. In: Proceedings of Computing: The Australasian Theory Symposium, CATS (2003)","DOI":"10.1016\/S1571-0661(04)81017-X"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Luchangco, V., Moir, M., Scherer III., W.N.: Software transactional memory of dynamic-sized data structures. In: Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing (2003)","DOI":"10.1145\/872035.872048"},{"issue":"3","key":"4_CR15","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"M. Herlihy","year":"1990","unstructured":"Herlihy, M., Wing, J.: Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems\u00a012(3), 463\u2013492 (1990)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Kawachiya, K., Koseki, A., Onodera, T.: Lock reservation: Java locks can mostly do without atomic operations. In: Proceedings of the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), pp. 130\u2013141 (2002)","DOI":"10.1145\/583854.582433"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"LaMarca, A.: A performance evaluation of lock-free synchronization protocols. In: Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, Los Angeles, CA, pp. 130\u2013140 (1994)","DOI":"10.1145\/197917.197975"},{"issue":"9","key":"4_CR18","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1109\/TC.1979.1675439","volume":"C-28","author":"L. Lamport","year":"1979","unstructured":"Lamport, L.: How to make a multiprocessor computer that correctly executes multiprocessor programs. IEEE Transactions on Computers\u00a0C-28(9), 690\u2013691 (1979)","journal-title":"IEEE Transactions on Computers"},{"issue":"1","key":"4_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/7351.7352","volume":"5","author":"L. Lamport","year":"1987","unstructured":"Lamport, L.: A fast mutual exclusion algorithm. ACM Transactions on Computer Systems\u00a05(1), 1\u201311 (1987)","journal-title":"ACM Transactions on Computer Systems"},{"key":"4_CR20","first-page":"163","volume-title":"Advances in Computing Research","author":"M.C. Loui","year":"1987","unstructured":"Loui, M.C., Abu-Amara, H.H.: Memory requirements for agreement among unreliable asynchronous processes. In: Preparata, F.P. (ed.) Advances in Computing Research, vol.\u00a04, pp. 163\u2013183. JAI Press, Greenwich (1987)"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"Luchangco, V., Moir, M., Shavit, N.: On the uncontended complexity of consensus (2002) (in preparation)","DOI":"10.1007\/978-3-540-39989-6_4"},{"issue":"2","key":"4_CR22","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1006\/inco.1995.1134","volume":"121","author":"N. Lynch","year":"1995","unstructured":"Lynch, N., Vaandrager, F.: Forward and backward simulations - part I: Untimed systems. Information and Computation\u00a0121(2), 214\u2013233 (1995)","journal-title":"Information and Computation"},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Michael, M.M.: High performance dynamic lock-free hash tables and list-based sets. In: Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 73\u201382 (2002)","DOI":"10.1145\/564870.564881"},{"key":"4_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0167-6423(95)00009-H","volume":"25","author":"M. Moir","year":"1995","unstructured":"Moir, M., Anderson, J.: Wait-free algorithms for fast, long-lived renaming. Science of Computer Programming\u00a025, 1\u201339 (1995); A preliminary version appeared in Proceedings of the 8th International Workshop on Distributed Algorithms, pp. 141\u2013155 (1994)","journal-title":"Science of Computer Programming"},{"key":"4_CR25","unstructured":"Saks, M., Shavit, N., Woll, H.: Optimal time randomized consensus \u2014 making resilient algorithms fast in practice. In: Proceedings of the Second Annual ACM-SIAM Symposium on Discrete algorithms, pp. 351\u2013362 (1991)"},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"Shalev, O., Shavit, N.: Split-ordered lists \u2014 lock-free resizable hash tables. In: Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing (2003)","DOI":"10.1145\/872035.872049"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39989-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T14:49:46Z","timestamp":1740840586000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39989-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540201847","9783540399896"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39989-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}