{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:10:08Z","timestamp":1750209008921,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,12,12]],"date-time":"2018-12-12T00:00:00Z","timestamp":1544572800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ARISTEIA Action of the Operational Program Education and Lifelong Learning"},{"DOI":"10.13039\/501100004895","name":"European Social Fund","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004895","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Resources through the GreenVM project"},{"name":"European Commission under the 7th Framework Program through the TransForm","award":["FP7-MC-ITN-238639"],"award-info":[{"award-number":["FP7-MC-ITN-238639"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,2,28]]},"abstract":"<jats:p>\n            We establish a theorem called the PCL theorem, which states that it is impossible to design a transactional memory algorithm that ensures (1)\n            <jats:bold>parallelism<\/jats:bold>\n            , i.e., transactions do not need to synchronize unless they access the same application objects, (2) very little\n            <jats:bold>consistency<\/jats:bold>\n            , i.e., a consistency condition, called\n            <jats:italic>weak adaptive consistency<\/jats:italic>\n            , introduced here and that is weaker than snapshot isolation, processor consistency, and any other consistency condition stronger than them (such as opacity, serializability, causal serializability, etc.), and (3) very little\n            <jats:bold>liveness<\/jats:bold>\n            , i.e., which transactions eventually commit if they run solo.\n          <\/jats:p>","DOI":"10.1145\/3266141","type":"journal-article","created":{"date-parts":[[2018,12,12]],"date-time":"2018-12-12T12:49:32Z","timestamp":1544618972000},"page":"1-66","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The PCL Theorem"],"prefix":"10.1145","volume":"66","author":[{"given":"Victor","family":"Bushkov","sequence":"first","affiliation":[{"name":"EPFL,Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dmytro","family":"Dziuma","sequence":"additional","affiliation":[{"name":"FORTH ICS, Heraklion, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panagiota","family":"Fatourou","sequence":"additional","affiliation":[{"name":"University of Crete 8 FORTH ICS, Heraklion, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rachid","family":"Guerraoui","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,12,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225271"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/259380.259431"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/165231.165264"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90056-0"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of WTTM.","author":"Ardekani Masoud Saeida","year":"2011","unstructured":"Masoud Saeida Ardekani , Pierre Sutra , and Marc Shapiro . 2011 . The impossibility of ensuring snapshot isolation in genuine replicated STMs . In Proceedings of WTTM. Masoud Saeida Ardekani, Pierre Sutra, and Marc Shapiro. 2011. The impossibility of ensuring snapshot isolation in genuine replicated STMs. In Proceedings of WTTM."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40047-6_39"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/248052.248097"},{"volume-title":"Transactional Memory. Foundations, Algorithms, Tools, and Applications","author":"Attiya Hagit","key":"e_1_2_1_8_1","unstructured":"Hagit Attiya and Panagiota Fatourou . 2015. Disjoint-access parallelism in software transactional memory . In Transactional Memory. Foundations, Algorithms, Tools, and Applications . Springer International Publishing . Hagit Attiya and Panagiota Fatourou. 2015. Disjoint-access parallelism in software transactional memory. In Transactional Memory. Foundations, Algorithms, Tools, and Applications. Springer International Publishing."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11864219_3"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of ICDCN--11","author":"Attiya Hagit","year":"2011","unstructured":"Hagit Attiya and Eshcar Hillel . 2011 . Single-version STMs can be multi-version permissive . In Proceedings of ICDCN--11 . Springer-Verlag. Hagit Attiya and Eshcar Hillel. 2011. Single-version STMs can be multi-version permissive. In Proceedings of ICDCN--11. Springer-Verlag."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584015"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9304-5"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/165231.165265"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/568271.223785"},{"volume-title":"Concurrency Control and Recovery in Database Systems","author":"Bernstein Philip A.","key":"e_1_2_1_16_1","unstructured":"Philip A. Bernstein , Vassco Hadzilacos , and Nathan Goodman . 1987. Concurrency Control and Recovery in Database Systems . Addison-Wesley Longman Publishing Co., Inc. Philip A. Bernstein, Vassco Hadzilacos, and Nathan Goodman. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley Longman Publishing Co., Inc."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332435"},{"key":"e_1_2_1_18_1","volume-title":"Louren\u00e7o","author":"Dias Ricardo J.","year":"2010","unstructured":"Ricardo J. Dias , Jo\u00e3o Seco , and Jo\u00e3o M . Louren\u00e7o . 2010 . Snapshot isolation anomalies detection in software transactional memory. In Proceedings of InForum-- 10. Ricardo J. Dias, Jo\u00e3o Seco, and Jo\u00e3o M. Louren\u00e7o. 2010. Snapshot isolation anomalies detection in software transactional memory. In Proceedings of InForum--10."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of TRANSACT--06","author":"Dice Dave","year":"2006","unstructured":"Dave Dice and Nir Shavit . 2006 . What really makes transactions faster? In Proceedings of TRANSACT--06 . Dave Dice and Nir Shavit. 2006. What really makes transactions faster? In Proceedings of TRANSACT--06."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332457"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-015-0261-8"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071615"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1345206.1345241"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233307.1233309"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/325164.325102"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/564585.564601"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/646234.682401"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378587"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1345206.1345233"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480931"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Rachid Guerraoui and Michal Kapalka. 2010. Principles of Transactional Memory. Morgan and Claypool.   Rachid Guerraoui and Michal Kapalka. 2010. Principles of Transactional Memory. Morgan and Claypool.","DOI":"10.1007\/978-3-031-02002-5"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/99164.99185"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872048"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/173682.165164"},{"volume-title":"Proceedings of ICDCS--90","author":"Hutto P. W.","key":"e_1_2_1_37_1","unstructured":"P. W. Hutto and M. Ahamad . 1990. Slow memory: Weakening consistency to enhance concurrency in distributed shared memories . In Proceedings of ICDCS--90 . IEEE, 302--309. P. W. Hutto and M. Ahamad. 1990. Slow memory: Weakening consistency to enhance concurrency in distributed shared memories. In Proceedings of ICDCS--90. IEEE, 302--309."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11476-2_21"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/197917.198079"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684464.2684473"},{"key":"e_1_2_1_41_1","volume-title":"Pram: A Scalable Shared Memory. Technical Report CS-TR-180-88","author":"Lipton R. J.","year":"1988","unstructured":"R. J. Lipton and J. S. Sandberg . 1988 . Pram: A Scalable Shared Memory. Technical Report CS-TR-180-88 . Princeton University . R. J. Lipton and J. S. Sandberg. 1988. Pram: A Scalable Shared Memory. Technical Report CS-TR-180-88. Princeton University."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2541940.2541952"},{"volume-title":"Distributed Algorithms","author":"Lynch Nancy A.","key":"e_1_2_1_43_1","unstructured":"Nancy A. Lynch . 1996. Distributed Algorithms . Morgan Kaufmann Publishers Inc . Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann Publishers Inc."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561927_26"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357178"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322158"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767438"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835704"},{"volume-title":"Proceedings of EUROMICRO--97","author":"Raynal M.","key":"e_1_2_1_49_1","unstructured":"M. Raynal , G. Thia-Kime , and M. Ahamad . 1997. From serializable to causal transactions for collaborative applications . In Proceedings of EUROMICRO--97 . M. Raynal, G. Thia-Kime, and M. Ahamad. 1997. From serializable to causal transactions for collaborative applications. In Proceedings of EUROMICRO--97."},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of ACM TRANSACT--06","author":"Riegel Torvald","year":"2006","unstructured":"Torvald Riegel , Christof Fetzer , and Pascal Felber . 2006 . Snapshot isolation for software transactional memory . In Proceedings of ACM TRANSACT--06 . Torvald Riegel, Christof Fetzer, and Pascal Felber. 2006. Snapshot isolation for software transactional memory. In Proceedings of ACM TRANSACT--06."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/224964.224987"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584048"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137873"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3266141","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3266141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:44:40Z","timestamp":1750207480000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3266141"}},"subtitle":["Transactions cannot be Parallel, Consistent, and Live"],"short-title":[],"issued":{"date-parts":[[2018,12,12]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,2,28]]}},"alternative-id":["10.1145\/3266141"],"URL":"https:\/\/doi.org\/10.1145\/3266141","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2018,12,12]]},"assertion":[{"value":"2015-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}