{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T16:53:41Z","timestamp":1761929621162},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642314230"},{"type":"electronic","value":"9783642314247"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31424-7_21","type":"book-chapter","created":{"date-parts":[[2012,6,21]],"date-time":"2012-06-21T14:26:49Z","timestamp":1340288809000},"page":"243-259","source":"Crossref","is-referenced-by-count":31,"title":["How to Prove Algorithms Linearisable"],"prefix":"10.1007","author":[{"given":"Gerhard","family":"Schellhorn","sequence":"first","affiliation":[]},{"given":"Heike","family":"Wehrheim","sequence":"additional","affiliation":[]},{"given":"John","family":"Derrick","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0304-3975(91)90224-P","volume":"2","author":"M. Abadi","year":"1991","unstructured":"Abadi, M., Lamport, L.: The existence of refinement mappings. Theoretical Computer Science\u00a02, 253\u2013284 (1991)","journal-title":"Theoretical Computer Science"},{"key":"21_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/978-3-540-73368-3_49","volume-title":"Computer Aided Verification","author":"D. Amit","year":"2007","unstructured":"Amit, D., Rinetzky, N., Reps, T.W., Sagiv, M., Yahav, E.: Comparison Under Abstraction for Verifying Linearizability. In: Damm, W., Hermanns, H. (eds.) CAV 2007. LNCS, vol.\u00a04590, pp. 477\u2013490. Springer, Heidelberg (2007)"},{"issue":"1","key":"21_CR3","first-page":"33","volume":"22","author":"R. Banach","year":"2010","unstructured":"Banach, R., Schellhorn, G.: Atomic Actions, and their Refinements to Isolated Protocols. FAC\u00a022(1), 33\u201361 (2010)","journal-title":"FAC"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Burckhardt, S., Dern, C., Musuvathi, M., Tan, R.: Line-up: a complete and automatic linearizability checker. In: Proceedings of PLDI, pp. 330\u2013340. ACM (2010)","DOI":"10.1145\/1809028.1806634"},{"key":"21_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-642-14295-6_41","volume-title":"Computer Aided Verification","author":"P. \u010cern\u00fd","year":"2010","unstructured":"\u010cern\u00fd, P., Radhakrishna, A., Zufferey, D., Chaudhuri, S., Alur, R.: Model Checking of Linearizability of Concurrent List Implementations. In: Touili, T., Cook, B., Jackson, P. (eds.) CAV 2010. LNCS, vol.\u00a06174, pp. 465\u2013479. Springer, Heidelberg (2010)"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"Derrick, J., Boiten, E.: Refinement in Z and Object-Z: Foundations and Advanced Applications. Springer (May 2001)","DOI":"10.1007\/978-1-4471-0257-1"},{"issue":"1","key":"21_CR7","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/1889997.1890001","volume":"33","author":"J. Derrick","year":"2011","unstructured":"Derrick, J., Schellhorn, G., Wehrheim, H.: Mechanically verified proof obligations for linearizability. ACM Trans. Program. Lang. Syst.\u00a033(1), 4 (2011)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"21_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-642-21437-0_25","volume-title":"FM 2011: Formal Methods","author":"J. Derrick","year":"2011","unstructured":"Derrick, J., Schellhorn, G., Wehrheim, H.: Verifying Linearisability with Potential Linearisation Points. In: Butler, M., Schulte, W. (eds.) FM 2011. LNCS, vol.\u00a06664, pp. 323\u2013337. Springer, Heidelberg (2011)"},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/978-3-540-30232-2_7","volume-title":"Formal Techniques for Networked and Distributed Systems \u2013 FORTE 2004","author":"S. Doherty","year":"2004","unstructured":"Doherty, S., Groves, L., Luchangco, V., Moir, M.: Formal Verification of a\u00a0Practical Lock-Free Queue Algorithm. In: de Frutos-Escrig, D., N\u00fa\u00f1ez, M. (eds.) FORTE 2004. LNCS, vol.\u00a03235, pp. 97\u2013114. Springer, Heidelberg (2004)"},{"issue":"51-52","key":"21_CR10","doi-asserted-by":"publisher","first-page":"4379","DOI":"10.1016\/j.tcs.2010.09.021","volume":"411","author":"I. Filipovic","year":"2010","unstructured":"Filipovic, I., O\u2019Hearn, P.W., Rinetzky, N., Yang, H.: Abstraction for concurrent objects. Theoretical Computer Science\u00a0411(51-52), 4379\u20134398 (2010)","journal-title":"Theoretical Computer Science"},{"key":"21_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/978-3-642-15375-4_27","volume-title":"CONCUR 2010 - Concurrency Theory","author":"M. Fu","year":"2010","unstructured":"Fu, M., Li, Y., Feng, X., Shao, Z., Zhang, Y.: Reasoning about Optimistic Concurrency Using a Program Logic for History. In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010. LNCS, vol.\u00a06269, pp. 388\u2013402. Springer, Heidelberg (2010)"},{"key":"21_CR12","first-page":"55","volume":"187","author":"L. Groves","year":"2007","unstructured":"Groves, L., Colvin, R.: Derivation of a scalable lock-free stack algorithm. ENTCS\u00a0187, 55\u201374 (2007)","journal-title":"ENTCS"},{"key":"21_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/11795490_3","volume-title":"Principles of Distributed Systems","author":"S. Heller","year":"2006","unstructured":"Heller, S., Herlihy, M., Luchangco, V., Moir, M., Scherer III, W.N., Shavit, N.: A Lazy Concurrent List-Based Set Algorithm. In: Anderson, J.H., Prencipe, G., Wattenhofer, R. (eds.) OPODIS 2005. LNCS, vol.\u00a03974, pp. 3\u201316. Springer, Heidelberg (2006)"},{"issue":"3","key":"21_CR14","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"M. Herlihy","year":"1990","unstructured":"Herlihy, M., Wing, J.M.: Linearizability: A correctness condition for concurrent objects. ACM TOPLAS\u00a012(3), 463\u2013492 (1990)","journal-title":"ACM TOPLAS"},{"key":"21_CR15","unstructured":"Jones, C.B.: Specification and design of (parallel) programs. In: Proceedings of IFIP 1983, pp. 321\u2013332. North-Holland (1983)"},{"key":"21_CR16","unstructured":"Web presentation of linearizability theory and the lazy set algorithm (2010), \n                    \n                      http:\/\/www.informatik.uni-augsburg.de\/swt\/projects\/possibilities.html"},{"key":"21_CR17","unstructured":"Web presentation of KIV proofs for this paper (2011), \n                    \n                      http:\/\/www.informatik.uni-augsburg.de\/swt\/projects\/Herlihy-Wing-queue.html"},{"key":"21_CR18","unstructured":"Lynch, N.: Distributed Algorithms. Morgan Kaufmann Publishers (1996)"},{"issue":"2","key":"21_CR19","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 \u2013 Part I: Untimed systems. Information and Computation\u00a0121(2), 214\u2013233 (1995)","journal-title":"Information and Computation"},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Michael, M.M., Scott, M.L.: Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In: Proc. 15th ACM Symp. on Principles of Distributed Computing, pp. 267\u2013275 (1996)","DOI":"10.1145\/248052.248106"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Moir, M., Nussbaum, D., Shalev, O., Shavit, N.: Using elimination to implement scalable and lock-free fifo queues. In: SPAA, pp. 253\u2013262. ACM (2005)","DOI":"10.1145\/1073970.1074013"},{"key":"21_CR22","doi-asserted-by":"crossref","unstructured":"O\u2019Hearn, P.W., Rinetzky, N., Vechev, M.T., Yahav, E., Yorsh, G.: Verifying linearizability with hindsight. In: 29th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 85\u201394 (2010)","DOI":"10.1145\/1835698.1835722"},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Reif, W., Schellhorn, G., Stenzel, K., Balser, M.: Structured specifications and interactive proofs with KIV. In: Automated Deduction\u2014A Basis for Applications, Interactive Theorem Proving, vol.\u00a0II, ch. 1, pp. 13\u201339. Kluwer (1998)","DOI":"10.1007\/978-94-017-0435-9_1"},{"key":"21_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/978-3-642-13321-3_21","volume-title":"Mathematics of Program Construction","author":"B. Tofan","year":"2010","unstructured":"Tofan, B., B\u00e4umler, S., Schellhorn, G., Reif, W.: Temporal Logic Verification of Lock-Freedom. In: Bolduc, C., Desharnais, J., Ktari, B. (eds.) MPC 2010. LNCS, vol.\u00a06120, pp. 377\u2013396. Springer, Heidelberg (2010)"},{"key":"21_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-642-23283-1_16","volume-title":"Theoretical Aspects of Computing \u2013 ICTAC 2011","author":"B. Tofan","year":"2011","unstructured":"Tofan, B., Schellhorn, G., Reif, W.: Formal Verification of a Lock-Free Stack with Hazard Pointers. In: Cerone, A., Pihlajasaari, P. (eds.) ICTAC 2011. LNCS, vol.\u00a06916, pp. 239\u2013255. Springer, Heidelberg (2011)"},{"key":"21_CR26","doi-asserted-by":"crossref","unstructured":"Turon, A., Wand, M.: A separation logic for refining concurrent objects. In: POPL, vol.\u00a046, pp. 247\u2013258. ACM (2011)","DOI":"10.1145\/1925844.1926415"},{"key":"21_CR27","unstructured":"Vafeiadis, V.: Modular fine-grained concurrency verification. PhD thesis, University of Cambridge (2007)"},{"key":"21_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1007\/978-3-642-14295-6_40","volume-title":"Computer Aided Verification","author":"V. Vafeiadis","year":"2010","unstructured":"Vafeiadis, V.: Automatically Proving Linearizability. In: Touili, T., Cook, B., Jackson, P. (eds.) CAV 2010. LNCS, vol.\u00a06174, pp. 450\u2013464. Springer, Heidelberg (2010)"},{"key":"21_CR29","doi-asserted-by":"crossref","unstructured":"Vafeiadis, V., Herlihy, M., Hoare, T., Shapiro, M.: Proving correctness of highly-concurrent linearisable objects. In: PPoPP 2006, pp. 129\u2013136. ACM (2006)","DOI":"10.1145\/1122971.1122992"}],"container-title":["Lecture Notes in Computer Science","Computer Aided Verification"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31424-7_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:59:51Z","timestamp":1620129591000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31424-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642314230","9783642314247"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31424-7_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}