{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,27]],"date-time":"2025-11-27T13:52:18Z","timestamp":1764251538447,"version":"3.41.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2017,11,29]],"date-time":"2017-11-29T00:00:00Z","timestamp":1511913600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,11,29]],"date-time":"2017-11-29T00:00:00Z","timestamp":1511913600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1320835","1420673"],"award-info":[{"award-number":["1320835","1420673"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00446-017-0318-y","type":"journal-article","created":{"date-parts":[[2018,9,5]],"date-time":"2018-09-05T07:20:58Z","timestamp":1536132058000},"page":"471-487","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Time-communication impossibility results for distributed transactional memory"],"prefix":"10.1007","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4381-4333","authenticated-orcid":false,"given":"Costas","family":"Busch","sequence":"first","affiliation":[]},{"given":"Maurice","family":"Herlihy","sequence":"additional","affiliation":[]},{"given":"Miroslav","family":"Popovic","sequence":"additional","affiliation":[]},{"given":"Gokarna","family":"Sharma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,29]]},"reference":[{"issue":"4","key":"318_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2411116.2411118","volume":"40","author":"MK Aguilera","year":"2012","unstructured":"Aguilera, M.K., Malkhi, D., Marzullo, K., Panconesi, A., Pelc, A., Wattenhofer, R.: Announcing the 2012 Edsger W. Dijkstra prize in distributed computing. SIGARCH Comput. Archit. News 40(4), 1\u20132 (2012)","journal-title":"SIGARCH Comput. Archit. News"},{"key":"318_CR2","doi-asserted-by":"crossref","unstructured":"Ansari, M., Luj\u00e1n, M., Kotselidis, C., Jarvis, K., Kirkham, C.C., Watson, I.: Steal-on-abort: improving transactional memory performance through dynamic transaction reordering. In: HiPEAC, pp. 4\u201318 (2009)","DOI":"10.1007\/978-3-540-92990-1_3"},{"key":"318_CR3","first-page":"38","volume":"112","author":"H Attiya","year":"2014","unstructured":"Attiya, H.: Lower bounds and impossibility results for transactional memory computing. Bull. EATCS 112, 38\u201352 (2014)","journal-title":"Bull. EATCS"},{"issue":"1","key":"318_CR4","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/s00453-008-9195-x","volume":"57","author":"H Attiya","year":"2010","unstructured":"Attiya, H., Epstein, L., Shachnai, H., Tamir, T.: Transactional contention management as a non-clairvoyant scheduling problem. Algorithmica 57(1), 44\u201361 (2010)","journal-title":"Algorithmica"},{"key":"318_CR5","first-page":"367","volume-title":"Transactional Memory, Volume 8913 of Lecture Notes in Computer Science","author":"H Attiya","year":"2015","unstructured":"Attiya, H., Gramoli, V., Milani, A.: Directory protocols for distributed transactional memory. In: Guerraoui, R., Romano, P. (eds.) Transactional Memory, Volume 8913 of Lecture Notes in Computer Science, pp. 367\u2013391. Springer, New York (2015)"},{"issue":"10","key":"318_CR6","doi-asserted-by":"publisher","first-page":"1386","DOI":"10.1016\/j.jpdc.2012.05.012","volume":"72","author":"H Attiya","year":"2012","unstructured":"Attiya, H., Milani, A.: Transactional scheduling for read-dominated workloads. J. Parallel Distrib. Comput. 72(10), 1386\u20131396 (2012)","journal-title":"J. Parallel Distrib. Comput."},{"key":"318_CR7","doi-asserted-by":"crossref","unstructured":"Bocchino, R.L., Adve, V.S., Chamberlain, B.L.: Software transactional memory for large scale clusters. In: PPoPP, pp. 247\u2013258 (2008)","DOI":"10.1145\/1345206.1345242"},{"key":"318_CR8","unstructured":"Busch, C., Herlihy, M., Popovic, M., Sharma, G.: Brief announcement: scheduling multiple objects in distributed transactional memory. In: DISC, pp. 538\u2013539 (2014)"},{"key":"318_CR9","doi-asserted-by":"crossref","unstructured":"Couceiro, M., Romano, P., Carvalho, N., Rodrigues, L.: D2STM: dependable distributed software transactional memory. In: PRDC, pp. 307\u2013313 (2009)","DOI":"10.1109\/PRDC.2009.55"},{"key":"318_CR10","doi-asserted-by":"crossref","unstructured":"Fahmy, S.F., Ravindran, B., Jensen, E.D.: Response time analysis of software transactional memory-based distributed real-time systems. In: Proceedings of the 2009 ACM Symposium on Applied Computing, SAC \u201909, pp. 334\u2013338. ACM, New York (2009)","DOI":"10.1145\/1529282.1529353"},{"key":"318_CR11","doi-asserted-by":"crossref","unstructured":"Fung, W.W.L., Singh, I., Brownsword, A., Aamodt, T.M.: Hardware transactional memory for GPU architectures. In: MICRO, pp. 296\u2013307 (2011)","DOI":"10.1145\/2155620.2155655"},{"key":"318_CR12","doi-asserted-by":"crossref","unstructured":"Guerraoui, R., Herlihy, M., Pochon, B.: Toward a theory of transactional contention managers. In: PODC, pp. 258\u2013264 (2005)","DOI":"10.1145\/1073814.1073863"},{"key":"318_CR13","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Kleinberg, R., Leighton, T.: Improved lower and upper bounds for universal TSP in planar metrics. In: SODA, pp. 649\u2013658 (2006)","DOI":"10.1145\/1109557.1109628"},{"issue":"2","key":"318_CR14","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1109\/MM.2011.108","volume":"32","author":"R Haring","year":"2012","unstructured":"Haring, R., Ohmacht, M., Fox, T., Gschwind, M., Satterfield, D., Sugavanam, K., Coteus, P., Heidelberger, P., Blumrich, M., Wisniewski, R., Chiu, G., Chiu, G., Boyle, P., Chist, N., Kim, C.: The IBM Blue Gene\/Q compute chip. IEEE Micro 32(2), 48\u201360 (2012)","journal-title":"IEEE Micro"},{"key":"318_CR15","doi-asserted-by":"crossref","unstructured":"Hendler, D., Naiman, A., Peluso, S., Quaglia, F., Romano, P., Suissa, A.: Exploiting locality in lease-based replicated transactional memory via task migration. In: DISC, pp. 121\u2013133 (2013)","DOI":"10.1007\/978-3-642-41527-2_9"},{"key":"318_CR16","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Moss, J.E.B: Transactional memory: architectural support for lock-free data structures. In: ISCA, pp. 289\u2013300 (1993)","DOI":"10.1145\/173682.165164"},{"issue":"3","key":"318_CR17","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s00446-007-0037-x","volume":"20","author":"M Herlihy","year":"2007","unstructured":"Herlihy, M., Sun, Y.: Distributed transactional memory for metric-space networks. Distrib. Comput. 20(3), 195\u2013208 (2007)","journal-title":"Distrib. Comput."},{"key":"318_CR18","doi-asserted-by":"crossref","unstructured":"Hirve, S., Palmieri, R., Ravindran, B.: Archie: a speculative replicated transactional system. In: Middleware, pp. 265\u2013276 (2014)","DOI":"10.1145\/2663165.2666090"},{"key":"318_CR19","unstructured":"Intel. http:\/\/software.intel.com\/en-us\/blogs\/2012\/02\/07\/transactional-synchronization-in-haswell"},{"key":"318_CR20","doi-asserted-by":"crossref","unstructured":"Jia, L., Lin, G., Noubir, G., Rajaraman, R., Sundaram, R.: Universal approximations for TSP, Steiner tree, and set cover. In: STOC, pp. 386\u2013395 (2005)","DOI":"10.1145\/1060590.1060649"},{"key":"318_CR21","first-page":"150","volume-title":"Transactional Memory, Volume 8913 of Lecture Notes in Computer Science","author":"I Keidar","year":"2015","unstructured":"Keidar, I., Perelman, D.: Multi-versioning in transactional memory. In: Guerraoui, R., Romano, P. (eds.) Transactional Memory, Volume 8913 of Lecture Notes in Computer Science, pp. 150\u2013165. Springer, New York (2015)"},{"key":"318_CR22","doi-asserted-by":"crossref","unstructured":"Kim, J., Ravindran, B.: Scheduling transactions in replicated distributed software transactional memory. In: CCGrid, pp. 227\u2013234 (2013)","DOI":"10.1109\/CCGrid.2013.88"},{"key":"318_CR23","doi-asserted-by":"crossref","unstructured":"Kim, J., Ravindran, B.: On transactional scheduling in distributed transactional memory systems. In: SSS, pp. 347\u2013361 (2010)","DOI":"10.1007\/978-3-642-16023-3_29"},{"key":"318_CR24","doi-asserted-by":"crossref","unstructured":"Kotselidis, C., Ansari, M., Jarvis, K., Luj\u00e1n, M., Kirkham, C., Watson, I.: DiSTM: a software transactional memory framework for clusters. In: ICPP, pp. 51\u201358 (2008)","DOI":"10.1109\/ICPP.2008.59"},{"key":"318_CR25","doi-asserted-by":"crossref","unstructured":"Manassiev, K., Mihailescu, M., Amza, C.: Exploiting distributed version concurrency in a transactional memory cluster. In: PPoPP, pp. 198\u2013208 (2006)","DOI":"10.1145\/1122971.1123002"},{"key":"318_CR26","first-page":"341","volume-title":"Transactional Memory, Volume 8913 Lecture Notes in Computer Science","author":"R Palmieri","year":"2015","unstructured":"Palmieri, R., Peluso, S., Ravindran, B.: Transaction execution models in partially replicated transactional memory: the case for data-flow and control-flow. In: Guerraoui, R., Romano, P. (eds.) Transactional Memory, Volume 8913 Lecture Notes in Computer Science, pp. 341\u2013366. Springer, New York (2015)"},{"key":"318_CR27","doi-asserted-by":"crossref","unstructured":"Palmieri, R., Quaglia, F., Romano, P.: ASAP: an aggressive speculative protocol for actively replicated transactional systems. In: NCA, pp. 203\u2013211 (2012)","DOI":"10.1109\/NCA.2012.45"},{"key":"318_CR28","doi-asserted-by":"crossref","unstructured":"Peluso, S., Romano, P., Quaglia, F.: Score: a scalable one-copy serializable partial replication protocol. In: Middleware, pp. 456\u2013475 (2012)","DOI":"10.1007\/978-3-642-35170-9_23"},{"key":"318_CR29","doi-asserted-by":"crossref","unstructured":"Peluso, S., Ruivo, P., Romano, P., Quaglia, F., Rodrigues, L.: When scalability meets consistency: genuine multiversion update-serializable partial data replication. In: ICDCS, pp. 455\u2013465 (2012)","DOI":"10.1109\/ICDCS.2012.55"},{"issue":"1","key":"318_CR30","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/j.jcss.2013.07.006","volume":"80","author":"P Romano","year":"2014","unstructured":"Romano, P., Palmieri, R., Quaglia, F., Carvalho, N., Rodrigues, L.: On speculative replication of transactional systems. J. Comput. Syst. Sci. 80(1), 257\u2013276 (2014)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"318_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1773912.1773914","volume":"44","author":"P Romano","year":"2010","unstructured":"Romano, P., Rodrigues, L., Carvalho, N., Cachopo, J.: Cloud-TM: harnessing the cloud with distributed transactional memories. ACM SIGOPS Oper. Syst. Rev. 44(2), 1\u20136 (2010)","journal-title":"ACM SIGOPS Oper. Syst. Rev."},{"key":"318_CR32","doi-asserted-by":"crossref","unstructured":"Saad, M.M, Ravindran, B.: Snake: control flow distributed software transactional memory. In: SSS, pp. 238\u2013252 (2011)","DOI":"10.1007\/978-3-642-24550-3_19"},{"key":"318_CR33","doi-asserted-by":"crossref","unstructured":"Scherer III, W.N., Scott, M.L.: Advanced contention management for dynamic software transactional memory. In: PODC, pp. 240\u2013248 (2005)","DOI":"10.1145\/1073814.1073861"},{"issue":"32","key":"318_CR34","doi-asserted-by":"publisher","first-page":"4151","DOI":"10.1016\/j.tcs.2010.10.010","volume":"412","author":"J Schneider","year":"2011","unstructured":"Schneider, J., Wattenhofer, R.: Bounds on contention management algorithms. Theor. Comput. Sci. 412(32), 4151\u20134160 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"318_CR35","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/s00453-011-9532-3","volume":"63","author":"G Sharma","year":"2012","unstructured":"Sharma, G., Busch, C.: A competitive analysis for balanced transactional memory workloads. Algorithmica 63(1\u20132), 296\u2013322 (2012)","journal-title":"Algorithmica"},{"issue":"3","key":"318_CR36","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s00446-012-0159-7","volume":"25","author":"G Sharma","year":"2012","unstructured":"Sharma, G., Busch, C.: Window-based greedy contention management for transactional memory: theory and practice. Distrib. Comput. 25(3), 225\u2013248 (2012)","journal-title":"Distrib. Comput."},{"issue":"5","key":"318_CR37","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s00446-014-0214-7","volume":"27","author":"G Sharma","year":"2014","unstructured":"Sharma, G., Busch, C.: Distributed transactional memory for general networks. Distrib. Comput. 27(5), 329\u2013362 (2014)","journal-title":"Distrib. Comput."},{"issue":"2","key":"318_CR38","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s004460050028","volume":"10","author":"N Shavit","year":"1997","unstructured":"Shavit, N., Touitou, D.: Software transactional memory. Distrib. Comput. 10(2), 99\u2013116 (1997)","journal-title":"Distrib. Comput."},{"key":"318_CR39","doi-asserted-by":"crossref","unstructured":"Wang, A., Gaudet, M., Wu, P., Amaral, J.N., Ohmacht, M., Barton, C., Silvera, R., Michael, M.: Evaluation of Blue Gene\/Q hardware support for transactional memories. In: PACT, pp. 127\u2013136 (2012)","DOI":"10.1145\/2370816.2370836"},{"key":"318_CR40","doi-asserted-by":"crossref","unstructured":"Yoo, R.M., Lee, H.-H.S: Adaptive transaction scheduling for transactional memory systems. In: SPAA, pp. 169\u2013178 (2008)","DOI":"10.1145\/1378533.1378564"},{"key":"318_CR41","doi-asserted-by":"crossref","unstructured":"Zhang, B., Ravindran, B.: Relay: a cache-coherence protocol for distributed transactional memory. In: OPODIS, pp. 48\u201353 (2009)","DOI":"10.1007\/978-3-642-10877-8_6"},{"key":"318_CR42","doi-asserted-by":"crossref","unstructured":"Zhang, B., Ravindran, B., Palmieri, R.: Distributed transactional contention management as the traveling salesman problem. In: SIROCCO, pp. 54\u201367 (2014)","DOI":"10.1007\/978-3-319-09620-9_6"},{"issue":"1","key":"318_CR43","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0318-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0318-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0318-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T21:35:32Z","timestamp":1751837732000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0318-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,29]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["318"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0318-y","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2017,11,29]]},"assertion":[{"value":"27 February 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}