{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T04:27:25Z","timestamp":1778732845172,"version":"3.51.4"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,2,2]],"date-time":"2012-02-02T00:00:00Z","timestamp":1328140800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00446-012-0159-7","type":"journal-article","created":{"date-parts":[[2012,2,1]],"date-time":"2012-02-01T16:25:09Z","timestamp":1328113509000},"page":"225-248","source":"Crossref","is-referenced-by-count":15,"title":["Window-based greedy contention management for transactional memory: theory and practice"],"prefix":"10.1007","volume":"25","author":[{"given":"Gokarna","family":"Sharma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Costas","family":"Busch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,2,2]]},"reference":[{"key":"159_CR1","doi-asserted-by":"crossref","unstructured":"Ansari, M., Kotselidis, C., Lujan, M., Kirkham, C., Watson, I.: On the performance of contention managers for complex transactional memory benchmarks. In: Proceedings of the 8th International Symposium on Parallel and Distributed Computing (ISPDC), pp. 83\u201390 (2009)","DOI":"10.1109\/ISPDC.2009.18"},{"key":"159_CR2","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1007\/978-3-540-92990-1_3","volume-title":"High Performance Embedded Architectures and Compilers, Lecture Notes in Computer Science, vol. 5409","author":"M. Ansari","year":"2009","unstructured":"Ansari M., Luj\u00e1n M., Kotselidis C., Jarvis K., Kirkham C., Watson I.: Steal-on-abort: Improving transactional memory performance through dynamic transaction reordering. In: Seznec, A., Emer, J., O\u2019Boyle, M., Martonosi, M., Ungerer, T. (eds) High Performance Embedded Architectures and Compilers, Lecture Notes in Computer Science, vol. 5409, pp. 4\u201318. Springer, Berlin, Heidelberg (2009)"},{"issue":"1","key":"159_CR3","doi-asserted-by":"crossref","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\u00e91a\u00e91non-clairvoyant scheduling problem. Algorithmica 57(1), 44\u201361 (2010)","journal-title":"Algorithmica"},{"key":"159_CR4","first-page":"3","volume-title":"Principles of Distributed Systems, Lecture Notes in Computer Science, vol. 5923","author":"H. Attiya","year":"2009","unstructured":"Attiya H., Milani A.: Transactional scheduling for read-dominated workloads. In: Abdelzaher, T., Raynal, M., Santoro, N. (eds) Principles of Distributed Systems, Lecture Notes in Computer Science, vol. 5923, pp. 3\u201317. Springer, Berlin, Heidelberg (2009)"},{"key":"159_CR5","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Saks, M.: A dining philosophers algorithm with polynomial response time. In: Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS), vol. 1, pp. 65\u201374. IEEE Computer Society, Washington, DC, USA (1990)","DOI":"10.1109\/FSCS.1990.89525"},{"issue":"2","key":"159_CR6","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0304-3975(96)00031-X","volume":"162","author":"B.S. Baker","year":"1996","unstructured":"Baker B.S., Coffman E.G. Jr: Mutual exclusion scheduling. Theor. Comput. Sci. 162(2), 225\u2013243 (1996)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"159_CR7","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0304-3975(95)00057-4","volume":"148","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender H.L., Jansen K.: Restrictions of graph partition problems, part I. Theor. Comput. Sci. 148(1), 93\u2013109 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"159_CR8","doi-asserted-by":"crossref","unstructured":"Cao Minh, C., Chung, J., Kozyrakis, C., Olukotun, K.: STAMP: Stanford transactional applications for multi-processing. In: Proceedings of The IEEE International Symposium on Workload Characterization (IISWC), pp. 35\u201346 (2008)","DOI":"10.1109\/IISWC.2008.4636089"},{"key":"159_CR9","doi-asserted-by":"crossref","unstructured":"Damron, P., Fedorova, A., Lev, Y., Luchangco, V., Moir, M., Nussbaum, D.: Hybrid transactional memory. In: Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-XII), pp. 336\u2013346. ACM, New York, NY, USA (2006)","DOI":"10.1145\/1168857.1168900"},{"key":"159_CR10","first-page":"194","volume-title":"Distributed Computing, Lecture Notes in Computer Science, vol. 4167","author":"D. Dice","year":"2006","unstructured":"Dice D., Shalev O., Shavit N.: Transactional locking II. In: Dolev, S. (ed) Distributed Computing, Lecture Notes in Computer Science, vol. 4167, pp. 194\u2013208. Springer, Berlin, Heidelberg (2006)"},{"key":"159_CR11","doi-asserted-by":"crossref","unstructured":"Dolev, S., Hendler, D., Suissa, A.: CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory. In: Proceedings of the 27th Annual ACM symposium on Principles of Distributed Computing (PODC), pp. 125\u2013134 (2008)","DOI":"10.1145\/1400751.1400769"},{"key":"159_CR12","doi-asserted-by":"crossref","unstructured":"Dragojevi\u0107, A., Guerraoui, R., Singh, A.V., Singh, V.: Preventing versus curing: avoiding conflicts in transactional memories. In: Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 7\u201316 (2009)","DOI":"10.1145\/1582716.1582725"},{"issue":"2","key":"159_CR13","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s10951-008-0089-1","volume":"12","author":"G. Even","year":"2009","unstructured":"Even G., Halld\u00f3rsson M.M., Kaplan L., Ron D.: Scheduling with conflicts: online and offline algorithms. J. Sched. 12(2), 199\u2013224 (2009)","journal-title":"J. Sched."},{"key":"159_CR14","doi-asserted-by":"crossref","unstructured":"Felber, P., Fetzer, C., Riegel, T.: Dynamic performance tuning of word-based software transactional memory. In: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 237\u2013246 (2008)","DOI":"10.1145\/1345206.1345241"},{"issue":"2","key":"159_CR15","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1137\/0204015","volume":"4","author":"M.R. Garey","year":"1975","unstructured":"Garey M.R., Grahams R.L.: Bounds for multiprocessor scheduling with resource constraints. SIAM J. Comput. 4(2), 187\u2013200 (1975)","journal-title":"SIAM J. Comput."},{"key":"159_CR16","unstructured":"Guerraoui, R., Herlihy, M., Kapalka, M., Pochon, B.: Robust contention management in software transactional memory. In: Proceedings of the OOPSLA 2005 Workshop on Synchronization and Concurrency on Object-Oriented Languages (SCOOL) (2005)"},{"key":"159_CR17","first-page":"303","volume-title":"Distributed Computing, Lecture Notes in Computer Science, vol. 3724","author":"R. Guerraoui","year":"2005","unstructured":"Guerraoui R., Herlihy M., Pochon B.: Polymorphic contention management. In: Fraigniaud, P. (ed) Distributed Computing, Lecture Notes in Computer Science, vol. 3724, pp. 303\u2013323. Springer, Berlin, Heidelberg (2005)"},{"key":"159_CR18","doi-asserted-by":"crossref","unstructured":"Guerraoui, R., Herlihy, M., Pochon, B.: Toward a theory of transactional contention managers. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 258\u2013264 (2005)","DOI":"10.1145\/1073814.1073863"},{"issue":"3","key":"159_CR19","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1145\/1272998.1273029","volume":"41","author":"R. Guerraoui","year":"2007","unstructured":"Guerraoui R., Kapalka M., Vitek J.: Stmbench7: a benchmark for software transactional memory. SIGOPS Oper. Syst. Rev. 41(3), 315\u2013324 (2007)","journal-title":"SIGOPS Oper. Syst. Rev."},{"issue":"2","key":"159_CR20","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0890-5401(02)00032-9","volume":"180","author":"M.M. Halld\u00f3rsson","year":"2003","unstructured":"Halld\u00f3rsson M.M., Kortsarz G., Proskurowski A., Salman R., Shachnai H., Telle J.A.: Multicoloring trees. Inf. Comput. 180(2), 113\u2013129 (2003)","journal-title":"Inf. Comput."},{"issue":"6","key":"159_CR21","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1109\/MM.2004.91","volume":"24","author":"L. Hammond","year":"2004","unstructured":"Hammond L., Carlstrom B.D., Wong V., Chen M., Kozyraki C., Olukotun K.: Transactional coherence and consistency: simplifying parallel hardware and software. IEEE Micro 24(6), 92\u2013103 (2004)","journal-title":"IEEE Micro"},{"issue":"11","key":"159_CR22","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1145\/949343.949340","volume":"38","author":"T. Harris","year":"2003","unstructured":"Harris T., Fraser K.: Language support for lightweight transactions. SIGPLAN Notices 38(11), 388\u2013402 (2003)","journal-title":"SIGPLAN Notices"},{"key":"159_CR23","doi-asserted-by":"crossref","unstructured":"Harris, T., Marlow, S., Peyton-Jones, S., Herlihy, M.: Composable memory transactions. In: Proceedings of the 10th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 48\u201360 (2005)","DOI":"10.1145\/1065944.1065952"},{"key":"159_CR24","doi-asserted-by":"crossref","unstructured":"Hasenfratz, D., Schneider, J., Wattenhofer, R.: Transactional memory: how to perform load adaption in a simple and distributed manner. In: Proceedings of the 2010 International Conference on High Performance Computing and Simulation (HPCS), pp. 163\u2013170 (2010)","DOI":"10.1109\/HPCS.2010.5547141"},{"key":"159_CR25","unstructured":"Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: double-ended queues as an example. In: Proceedings of the 23th International Conference on Distributed Computing Systems (ICDCS), pp. 522\u2013529 (2003)"},{"issue":"10","key":"159_CR26","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1145\/1167515.1167495","volume":"41","author":"M. Herlihy","year":"2006","unstructured":"Herlihy M., Luchangco V., Moir M.: A flexible framework for implementing software transactional memory. SIGPLAN Notices 41(10), 253\u2013262 (2006)","journal-title":"SIGPLAN Notices"},{"key":"159_CR27","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Luchangco, V., Moir, M., Scherer III, W.N.: Software transactional memory for dynamic-sized data structures. In: Proceedings of the 22th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 92\u2013101 (2003)","DOI":"10.1145\/872035.872048"},{"key":"159_CR28","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Moss, J.E.B.: Transactional memory: architectural support for lock-free data structures. In: Proceedings of the 20th Annual International Symposium on Computer Architecture (ISCA), pp. 289\u2013300 (1993)","DOI":"10.1109\/ISCA.1993.698569"},{"key":"159_CR29","unstructured":"Irani, S., Leung, V.: Scheduling with conflicts, and applications to traffic signal control. In: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 85\u201394. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1996)"},{"key":"159_CR30","doi-asserted-by":"crossref","unstructured":"Khot, S.: Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In: Proceedings of the 42th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 600\u2013609 (2001)","DOI":"10.1109\/SFCS.2001.959936"},{"issue":"4","key":"159_CR31","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131055 (1986)","journal-title":"SIAM J. Comput."},{"key":"159_CR32","unstructured":"Marathe, V.J., Spear, M.F., Heriot, C., Acharya, A., Eisenstat, D., Scherer, W.N. III, Scott, M.L.: Lowering the overhead of software transactional memory. Tech. Rep. TR 893, Computer Science Department, University of Rochester (2006)"},{"key":"159_CR33","doi-asserted-by":"crossref","unstructured":"Minh, C.C., Trautmann, M., Chung, J., McDonald, A., Bronson, N., Casper, J., Kozyrakis, C., Olukotun, K.: An effective hybrid transactional memory system with strong isolation guarantees. In: Proceedings of the 34th Annual International Symposium on Computer Architecture (ISCA), pp. 69\u201380. ACM, New York, NY, USA (2007)","DOI":"10.1145\/1250662.1250673"},{"issue":"1","key":"159_CR34","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0304-3975(94)90151-1","volume":"130","author":"R. Motwani","year":"1994","unstructured":"Motwani R., Phillips S., Torng E.: Non-clairvoyant scheduling. Theor. Comput. Sci. 130(1), 17\u201347 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"159_CR35","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W. Pugh","year":"1990","unstructured":"Pugh W.: Skip lists: a probabilistic alternative to balanced trees. Commun. ACM 33(6), 668\u2013676 (1990)","journal-title":"Commun. ACM"},{"key":"159_CR36","doi-asserted-by":"crossref","unstructured":"Rajwar, R., Goodman, J.R.: Transactional lock-free execution of lock-based programs. In: Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-X), pp. 5\u201317. ACM (2002)","DOI":"10.1145\/605397.605399"},{"issue":"1","key":"159_CR37","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1109\/MM.2008.10","volume":"28","author":"H.E. Ramadan","year":"2008","unstructured":"Ramadan H.E., Rossbach C.J., Porter D.E., Hofmann O.S., Bhandari A., Witchel E.: Metatm\/txlinux: Transactional memory for an operating system. IEEE Micro 28(1), 42\u201351 (2008)","journal-title":"IEEE Micro"},{"key":"159_CR38","doi-asserted-by":"crossref","unstructured":"Scherer, W.N. III, Scott, M.L.: Advanced contention management for dynamic software transactional memory. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 240\u2013248 (2005)","DOI":"10.1145\/1073814.1073861"},{"key":"159_CR39","doi-asserted-by":"crossref","unstructured":"Scherer, W.N. III, Scott, M.L.: Contention management in dynamic software transactional memory. In: Proceedings of the ACM PODC Workshop on Concurrency and Synchronization in Java Programs (CSJP). St. John\u2019s, NL, Canada (2004)","DOI":"10.1145\/1073814.1073861"},{"issue":"32","key":"159_CR40","doi-asserted-by":"crossref","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."},{"key":"159_CR41","doi-asserted-by":"crossref","unstructured":"Sharma, G., Busch, C.: A competitive analysis for balanced transactional memory workloads. Algorithmica, Online First pp. 1\u201327, (A preliminary version In: Proceedings of the 14th International Conference on Principles of Distributed Systems (OPODIS 2010), Lecture Notes in Computer Science, vol. 6490, pp. 348\u2013363). Springer Berlin, Heidelberg (2011)","DOI":"10.1007\/978-3-642-17653-1_26"},{"key":"159_CR42","doi-asserted-by":"crossref","unstructured":"Sharma, G., Busch, C.: On the performance of window-based contention managers for transactional memory. International Symposium on Parallel and Distributed Processing Workshops and PhD Forum (IPDPSW) pp. 559\u2013568 (2011)","DOI":"10.1109\/IPDPS.2011.207"},{"key":"159_CR43","first-page":"64","volume-title":"Distributed Computing, Lecture Notes in Computer Science, vol. 6343","author":"G. Sharma","year":"2010","unstructured":"Sharma G., Estrade B., Busch C.: Window-based greedy contention management for transactional memory. In: Lynch, N., Shvartsman, A. (eds) Distributed Computing, Lecture Notes in Computer Science, vol. 6343, pp. 64\u201378. Springer, Berlin, Heidelberg (2010)"},{"issue":"2","key":"159_CR44","doi-asserted-by":"crossref","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."},{"issue":"4","key":"159_CR45","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1109\/88.260295","volume":"1","author":"J.M. Stone","year":"1993","unstructured":"Stone J.M., Stone H.S., Heidelberger P., Turek J.: Multiple reservations and the oklahoma update. IEEE Parallel Distrib. Technol. 1(4), 58\u201371 (1993)","journal-title":"IEEE Parallel Distrib. Technol."},{"key":"159_CR46","doi-asserted-by":"crossref","unstructured":"Yoo, R.M., Lee, H.H.S.: Adaptive transaction scheduling for transactional memory systems. In: Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 169\u2013178 (2008)","DOI":"10.1145\/1378533.1378564"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-012-0159-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-012-0159-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-012-0159-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T17:40:33Z","timestamp":1742406033000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-012-0159-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,2]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["159"],"URL":"https:\/\/doi.org\/10.1007\/s00446-012-0159-7","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,2]]}}}