{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:58:24Z","timestamp":1760241504071,"version":"build-2065373602"},"reference-count":31,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2018,5,4]],"date-time":"2018-05-04T00:00:00Z","timestamp":1525392000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000930","name":"NSF","doi-asserted-by":"publisher","award":["1526725"],"award-info":[{"award-number":["1526725"]}],"id":[{"id":"10.13039\/501100000930","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In the quest for higher-performance shared data structures, weakening consistency conditions and relaxing the sequential specifications of data types are two of the primary tools available in the literature today. In this paper, we show that these two approaches are in many cases different ways to specify the same sets of allowed concurrent behaviors of a given shared data object. This equivalence allows us to use whichever description is clearer, simpler, or easier to achieve equivalent guarantees. Specifically, for three common data type relaxations, we define consistency conditions such that the combination of the new consistency condition and an unrelaxed type allows the same behaviors as Linearizability and the relaxed version of the data type. Conversely, for the consistency condition k-Atomicity, we define a new data type relaxation such that the behaviors allowed by the relaxed version of a data type, combined with Linearizability, are the same as those allowed by k-Atomicity and the original type. As an example of the possibilities opened by our new equivalence, we use standard techniques from the literature on consistency conditions to prove that the three data type relaxations we consider are not comparable to one another or to several similar known conditions. Finally, we show a particular class of data types where one of our newly-defined consistency conditions is comparable to, and stronger than, one of the known consistency conditions we consider.<\/jats:p>","DOI":"10.3390\/a11050061","type":"journal-article","created":{"date-parts":[[2018,5,7]],"date-time":"2018-05-07T03:12:21Z","timestamp":1525662741000},"page":"61","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Relaxed Data Types as Consistency Conditions \u2020"],"prefix":"10.3390","volume":"11","author":[{"given":"Edward","family":"Talmage","sequence":"first","affiliation":[{"name":"Department of Computer Science &amp; Engineering, Texas A&amp;M University, College Station, TX 77843, USA"}]},{"given":"Jennifer L.","family":"Welch","sequence":"additional","affiliation":[{"name":"Department of Computer Science &amp; Engineering, Texas A&amp;M University, College Station, TX 77843, USA"}]}],"member":"1968","published-online":{"date-parts":[[2018,5,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/78969.78972","article-title":"Linearizability: A Correctness Condition for Concurrent Objects","volume":"12","author":"Herlihy","year":"1990","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"ref_2","unstructured":"Ball, T., and Sagiv, M. (2011, January 26\u201328). Laws of order: Expensive synchronization in concurrent algorithms cannot be eliminated. Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1145\/176575.176576","article-title":"Sequential Consistency versus Linearizability","volume":"12","author":"Attiya","year":"1994","journal-title":"ACM Trans. Comput. Syst."},{"key":"ref_4","unstructured":"Lipton, R.J., and Sandberg, J.S. (1988). PRAM: A Scalable Shared Memory, Department of Computer Science, Princeton University. Technical Report CS-TR-180-88."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Wang, J., Talmage, E., Lee, H., and Welch, J.L. (2014, January 19\u201323). Improved Time Bounds for Linearizable Implementations of Abstract Data Types. Proceedings of the 2014 IEEE 28th International Parallel and Distributed Processing Symposium, IEEE Computer Society, Phoenix, AZ, USA.","DOI":"10.1109\/IPDPS.2014.77"},{"key":"ref_6","first-page":"421","article-title":"Improving Average Performance by Relaxing Distributed Data Structures","volume":"Volume 8784","author":"Kuhn","year":"2014","journal-title":"Proceedings of the 28th International Symposium on Distributed Computing, DISC 2014"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Viotti, P., and Vukolic, M. (2016). Consistency in Non-Transactional Distributed Storage Systems. ACM Comput. Surv., 49.","DOI":"10.1145\/2926965"},{"key":"ref_8","first-page":"386","article-title":"Conflict-Free Replicated Data Types","volume":"Volume 6976","author":"Petit","year":"2011","journal-title":"Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems"},{"key":"ref_9","first-page":"395","article-title":"Quasi-Linearizability: Relaxed Consistency for Improved Concurrency","volume":"Volume 6490","author":"Lu","year":"2010","journal-title":"Proceedings of the 14th International Conference on Principles of Distributed Systems, OPODIS 2010"},{"key":"ref_10","unstructured":"Giacobazzi, R., and Cousot, R. (2013, January 23\u201325). Quantitative relaxation of concurrent data structures. Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL\u201913, Rome, Italy."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Cohen, A., and Grove, D. (2015, January 7\u201311). The SprayList: A scalable relaxed priority queue. Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2015, San Francisco, CA, USA.","DOI":"10.1145\/2688500.2688523"},{"key":"ref_12","unstructured":"Kirsch, C.M., Lippautz, M., and Payer, H. (2012). Fast and Scalable k-FIFO Queues, Department of Computer Sciences, University of Salzburg. Technical Report 2012-04."},{"key":"ref_13","unstructured":"Blelloch, G.E., and Agrawal, K. (2015, January 13\u201315). Brief Announcement: MultiQueues: Simple Relaxed Concurrent Priority Queues. Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA."},{"key":"ref_14","unstructured":"Cohen, A., and Grove, D. (2015, January 7\u201311). The lock-free k-LSM relaxed priority queue. Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2015, San Francisco, CA, USA."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s00446-016-0272-0","article-title":"The computability of relaxed data structures: Queues and stacks as examples","volume":"29","author":"Shavit","year":"2016","journal-title":"Distrib. Comput."},{"key":"ref_16","unstructured":"Abbadi, A.E., and Garbinato, B. (2017, January 17\u201319). Anomalies and Similarities Among Consensus Numbers of Relaxed Queues. Proceedings of the 5th Edition of the International Conference on Networked Systems, NETYS 2017, Marrakech, Morocco. Lecture Notes in Computer Science."},{"key":"ref_17","unstructured":"Reed, D.A., and Sarkar, V. (2009, January 14\u201318). Idempotent work stealing. Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2009, Raleigh, NC, USA."},{"key":"ref_18","unstructured":"Gavoille, C., and Fraigniaud, P. (2011, January 6\u20138). Scalability versus semantics of concurrent FIFO queues. Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA, USA."},{"key":"ref_19","first-page":"175","article-title":"Consistency in Distributed Storage Systems - An Overview of Models, Metrics and Measurement Approaches","volume":"Volume 7853","author":"Gramoli","year":"2013","journal-title":"Proceedings of the First International Conference on Networked Systems, NETYS 2013"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/S0020-0190(02)00498-2","article-title":"On the composability of consistency conditions","volume":"86","author":"Friedman","year":"2003","journal-title":"Inf. Process. Lett."},{"key":"ref_21","first-page":"92","article-title":"On the Locality of Consistency Conditions","volume":"Volume 2848","author":"Vitenberg","year":"2003","journal-title":"Proceedings of the 17th International Conference on Distributed Computing, DISC 2003"},{"key":"ref_22","unstructured":"Spirakis, P., and Tsigas, P. (2017, January 5\u20138). Relaxed Data Types as Consistency Conditions. Proceedings of the 19th International Symposium on Stabilization, Boston, MA, USA. Lecture Notes in Computer Science."},{"key":"ref_23","unstructured":"Anderson, J.H., Peleg, D., and Borowsky, E. (1994, January 14\u201317). Set-Linearizability. Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, Los Angeles, CA, USA."},{"key":"ref_24","first-page":"420","article-title":"Specifying Concurrent Problems: Beyond Linearizability and up to Tasks\u2014(Extended Abstract)","volume":"Volume 9363","author":"Moses","year":"2015","journal-title":"Proceedings of the 29th International Symposium on Distributed Computing, DISC 2015"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1007\/11561927_6","article-title":"On the Availability of Non-strict Quorum Systems","volume":"Volume 3724","author":"Fraigniaud","year":"2005","journal-title":"Distributed Computing"},{"key":"ref_26","unstructured":"Halld\u00f3rsson, M.M., and Dolev, S. (2014, January 15\u201318). Brief announcement: Concurrency-Aware Linearizability. Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC\u201914, Paris, France."},{"key":"ref_27","first-page":"371","article-title":"Modular Verification of Concurrency-Aware Linearizability","volume":"Volume 9363","author":"Moses","year":"2015","journal-title":"Proceedings of the 29th International Symposium on Distributed Computing, DISC 2015"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/BF01786228","article-title":"On Interprocess Communication. Part II: Algorithms","volume":"1","author":"Lamport","year":"1986","journal-title":"Distrib. Comput."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/07071158X","article-title":"Multiwriter Consistency Conditions for Shared Memory Registers","volume":"40","author":"Shao","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_30","unstructured":"Kosa, M.J. (1999). Time Bounds for Strong and Hybrid Consistency for Arbitrary Abstract Data Types. Chicago J. Theor. Comput. Sci."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1637","DOI":"10.1137\/S0097539795289215","article-title":"A Correctness Condition for High-Performance Multiprocessors","volume":"27","author":"Attiya","year":"1998","journal-title":"SIAM J. Comput."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/5\/61\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:03:15Z","timestamp":1760194995000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/5\/61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,4]]},"references-count":31,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2018,5]]}},"alternative-id":["a11050061"],"URL":"https:\/\/doi.org\/10.3390\/a11050061","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,5,4]]}}}