{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T16:28:06Z","timestamp":1742920086600,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319690834"},{"type":"electronic","value":"9783319690841"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-69084-1_10","type":"book-chapter","created":{"date-parts":[[2017,10,6]],"date-time":"2017-10-06T03:30:06Z","timestamp":1507260606000},"page":"142-156","source":"Crossref","is-referenced-by-count":0,"title":["Relaxed Data Types as Consistency Conditions"],"prefix":"10.1007","author":[{"given":"Edward","family":"Talmage","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jennifer L.","family":"Welch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,10,7]]},"reference":[{"key":"10_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-642-17653-1_29","volume-title":"Principles of Distributed Systems","author":"Y Afek","year":"2010","unstructured":"Afek, Y., Korland, G., Yanovsky, E.: Quasi-linearizability: relaxed consistency for improved concurrency. In: Lu, C., Masuzawa, T., Mosbah, M. (eds.) OPODIS 2010. LNCS, vol. 6490, pp. 395\u2013410. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-17653-1_29"},{"key":"10_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/11561927_6","volume-title":"Distributed Computing","author":"A Aiyer","year":"2005","unstructured":"Aiyer, A., Alvisi, L., Bazzi, R.A.: On the availability of non-strict quorum systems. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol. 3724, pp. 48\u201362. Springer, Heidelberg (2005). doi: 10.1007\/11561927_6"},{"issue":"8","key":"10_CR3","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/2858788.2688523","volume":"50","author":"Dan Alistarh","year":"2015","unstructured":"Alistarh, D., Kopinsky, J., Li, J., Shavit, N.: The spraylist: a scalable relaxed priority queue. In: Cohen and Grove [9], pp. 11\u201320","journal-title":"ACM SIGPLAN Notices"},{"issue":"6","key":"10_CR4","doi-asserted-by":"publisher","first-page":"1637","DOI":"10.1137\/S0097539795289215","volume":"27","author":"H Attiya","year":"1998","unstructured":"Attiya, H., Friedman, R.: A correctness condition for high-performance multiprocessors. SIAM J. Comput. 27(6), 1637\u20131670 (1998)","journal-title":"SIAM J. Comput."},{"key":"10_CR5","first-page":"487","volume-title":"POPL","author":"H Attiya","year":"2011","unstructured":"Attiya, H., Guerraoui, R., Hendler, D., Kuznetsov, P., Michael, M.M., Vechev, M.T.: Laws of order: expensive synchronization in concurrent algorithms cannot be eliminated. In: Ball, T., Sagiv, M. (eds.) POPL, pp. 487\u2013498. ACM, New York (2011)"},{"issue":"2","key":"10_CR6","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/176575.176576","volume":"12","author":"H Attiya","year":"1994","unstructured":"Attiya, H., Welch, J.L.: Sequential consistency versus linearizability. ACM Trans. Comput. Syst. 12(2), 91\u2013122 (1994)","journal-title":"ACM Trans. Comput. Syst."},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-642-40148-0_13","volume-title":"Networked Systems","author":"D Bermbach","year":"2013","unstructured":"Bermbach, D., Kuhlenkamp, J.: Consistency in distributed storage systems. In: Gramoli, V., Guerraoui, R. (eds.) NETYS 2013. LNCS, vol. 7853, pp. 175\u2013189. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40148-0_13"},{"key":"10_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/978-3-662-48653-5_28","volume-title":"Distributed Computing","author":"A Casta\u00f1eda","year":"2015","unstructured":"Casta\u00f1eda, A., Rajsbaum, S., Raynal, M.: Specifying concurrent problems: beyond linearizability and up to tasks. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 420\u2013435. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-48653-5_28"},{"key":"10_CR9","unstructured":"Cohen, A., Grove, D. (eds): Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOP 2015, San Francisco, CA, USA, 7\u201311 February 2015. ACM (2015)"},{"issue":"4","key":"10_CR10","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/S0020-0190(02)00498-2","volume":"86","author":"R Friedman","year":"2003","unstructured":"Friedman, R., Vitenberg, R., Chockler, G.V.: On the composability of consistency conditions. Inf. Process. Lett. 86(4), 169\u2013176 (2003)","journal-title":"Inf. Process. Lett."},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Hemed, N., Rinetzky, N.: Brief announcement: concurrency-aware linearizability. In: Halld\u00f3rsson, M.M., Dolev, S. (eds) ACM Symposium on Principles of Distributed Computing, PODC 2014, Paris, France, 15\u201318 July 2014, pp. 209\u2013211. ACM (2014)","DOI":"10.1145\/2611462.2611513"},{"key":"10_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-662-48653-5_25","volume-title":"Distributed Computing","author":"N Hemed","year":"2015","unstructured":"Hemed, N., Rinetzky, N., Vafeiadis, V.: Modular verification of concurrency-aware linearizability. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 371\u2013387. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-48653-5_25"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Henzinger, T.A., Kirsch, C.M., Payer, H., Sezgin, A., Sokolova, A.: Quantitative relaxation of concurrent data structures. In: Giacobazzi, R., Cousot, R. (eds) The 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2013, Rome, Italy, 23\u201325 January 2013, pp. 317\u2013328. ACM (2013)","DOI":"10.1145\/2429069.2429109"},{"issue":"3","key":"10_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 Trans. Program. Lang. Syst. 12(3), 463\u2013492 (1990)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Kirsch, C.M., Lippautz, M., Payer, H.: Fast and scalable k-FIFO queues. Technical report 2012\u201304, Department of Computer Sciences, University of Salzburg June 2012","DOI":"10.1007\/978-3-642-39958-9_18"},{"key":"10_CR16","unstructured":"Kosa, M.J.: Time bounds for strong and hybrid consistency for arbitrary abstract data types. Chicago J. Theor. Comput. Sci. 1999, paper 9, (1999)"},{"issue":"2","key":"10_CR17","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/BF01786228","volume":"1","author":"L Lamport","year":"1986","unstructured":"Lamport, L.: On interprocess communication. part II: algorithms. Distrib. Comput. 1(2), 86\u2013101 (1986)","journal-title":"Distrib. Comput."},{"key":"10_CR18","unstructured":"Lipton, R.J., Sandberg, J.S.: PRAM: a scalable shared memory. Technical report CS-TR-180-88, Department of Computer Science, Princeton University, September 1988"},{"key":"10_CR19","series-title":"Lecture Notes in Computer Science","volume-title":"Distributed Computing","year":"2015","unstructured":"Moses, Y. (ed.): DISC 2015. LNCS, vol. 9363. Springer, Heidelberg (2015)"},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"Neiger, G.: Set-linearizability. In: Anderson, J.H., Peleg, D., Borowsky, E. (eds) Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, Los Angeles, California, USA, 14\u201317 August 1994, p. 396. ACM (1994)","DOI":"10.1145\/197917.198176"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Rihani, H., Sanders, P., Dementiev, R.: Brief announcement: multiqueues: simple relaxed concurrent priority queues. In: Blelloch, G.E., Agrawal, K. (eds) Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, 13\u201315 June 2015, pp. 80\u201382. ACM (2015)","DOI":"10.1145\/2755573.2755616"},{"issue":"1","key":"10_CR22","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/07071158X","volume":"40","author":"C Shao","year":"2011","unstructured":"Shao, C., Welch, J.L., Pierce, E., Lee, H.: Multiwriter consistency conditions for shared memory registers. SIAM J. Comput. 40(1), 28\u201362 (2011)","journal-title":"SIAM J. Comput."},{"key":"10_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/978-3-642-24550-3_29","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"M Shapiro","year":"2011","unstructured":"Shapiro, M., Pregui\u00e7a, N., Baquero, C., Zawirski, M.: Conflict-free replicated data types. In: D\u00e9fago, X., Petit, F., Villain, V. (eds.) SSS 2011. LNCS, vol. 6976, pp. 386\u2013400. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-24550-3_29"},{"key":"10_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/978-3-319-25258-2_29","volume-title":"Structural Information and Communication Complexity","author":"N Shavit","year":"2015","unstructured":"Shavit, N., Taubenfeld, G.: The computability of relaxed data structures: queues and stacks as examples. In: Scheideler, C. (ed.) Structural Information and Communication Complexity. LNCS, vol. 9439, pp. 414\u2013428. Springer, Cham (2015). doi: 10.1007\/978-3-319-25258-2_29"},{"key":"10_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/978-3-662-45174-8_29","volume-title":"Distributed Computing","author":"E Talmage","year":"2014","unstructured":"Talmage, E., Welch, J.L.: Improving average performance by relaxing distributed data structures. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 421\u2013438. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-45174-8_29"},{"key":"10_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/978-3-319-59647-1_15","volume-title":"Networked Systems","author":"E Talmage","year":"2017","unstructured":"Talmage, E., Welch, J.L.: Anomalies and similarities among consensus numbers of variously-relaxed queues. In: El Abbadi, A., Garbinato, B. (eds.) NETYS 2017. LNCS, vol. 10299, pp. 191\u2013205. Springer, Cham (2017). doi: 10.1007\/978-3-319-59647-1_15"},{"issue":"1","key":"10_CR27","doi-asserted-by":"publisher","first-page":"19:1","DOI":"10.1145\/2926965","volume":"49","author":"P Viotti","year":"2016","unstructured":"Viotti, P., Vukolic, M.: Consistency in non-transactional distributed storage systems. ACM Comput. Surv. 49(1), 19:1\u201319:34 (2016)","journal-title":"ACM Comput. Surv."},{"key":"10_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-540-39989-6_7","volume-title":"Distributed Computing","author":"R Vitenberg","year":"2003","unstructured":"Vitenberg, R., Friedman, R.: On the locality of consistency conditions. In: Fich, F.E. (ed.) DISC 2003. LNCS, vol. 2848, pp. 92\u2013105. Springer, Heidelberg (2003). doi: 10.1007\/978-3-540-39989-6_7"},{"key":"10_CR29","doi-asserted-by":"crossref","unstructured":"Wang, J., Talmage, E., Lee, H., Welch, J.L.: Improved time bounds for linearizable implementations of abstract data types. In: 2014 IEEE 28th International Parallel and Distributed Processing Symposium, Phoenix, AZ, USA, 19\u201323 May 2014, pp. 691\u2013701. IEEE Computer Society (2014)","DOI":"10.1109\/IPDPS.2014.77"},{"issue":"8","key":"10_CR30","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/2858788.2688547","volume":"50","author":"Martin Wimmer","year":"2015","unstructured":"Wimmer, M., Gruber, J., Tr\u00e4ff, J.L., Tsigas, P.: The lock-free k-LSM relaxed priority queue. In: Cohen and Grove [9], pp. 277\u2013278 (2015)","journal-title":"ACM SIGPLAN Notices"}],"container-title":["Lecture Notes in Computer Science","Stabilization, Safety, and Security of Distributed Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-69084-1_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,27]],"date-time":"2024-06-27T15:08:10Z","timestamp":1719500890000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-69084-1_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319690834","9783319690841"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-69084-1_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}