{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:28:16Z","timestamp":1772119696438,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T00:00:00Z","timestamp":1634774400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T00:00:00Z","timestamp":1634774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["UID\/CEC\/04516\/2019"],"award-info":[{"award-number":["UID\/CEC\/04516\/2019"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s10951-021-00706-6","type":"journal-article","created":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T16:31:40Z","timestamp":1634833900000},"page":"107-124","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Scheduling computations with provably low synchronization overheads"],"prefix":"10.1007","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0080-8670","authenticated-orcid":false,"given":"Guilherme","family":"Rito","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7958-9740","authenticated-orcid":false,"given":"Herv\u00e9","family":"Paulino","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,21]]},"reference":[{"key":"706_CR1","doi-asserted-by":"publisher","unstructured":"Acar, U. A., Blelloch, G. E., & Blumofe, R. D. (2002). The data locality of work stealing. Theory of Computing Systems, 35(3), 321\u2013347. https:\/\/doi.org\/10.1007\/s00224-002-1057-3","DOI":"10.1007\/s00224-002-1057-3"},{"key":"706_CR2","doi-asserted-by":"publisher","unstructured":"Acar, U. A., Chargu\u00e9raud, A., & Rainey, M. (2013). Scheduling parallel programs by work stealing with private deques. In ACM SIGPLAN symposium on principles and practice of parallel programming, PPoPP\u201913, February 23\u201327, 2013 (pp. 219\u2013228). https:\/\/doi.org\/10.1145\/2442516.2442538","DOI":"10.1145\/2442516.2442538"},{"key":"706_CR3","doi-asserted-by":"publisher","unstructured":"Agrawal, K., He, Y., Hsu, W., & Leiserson, C. E. (2007). Adaptive scheduling with parallelism feedback. In 21th International parallel and distributed processing symposium (IPDPS 2007), proceedings, 26\u201330 March 2007 (pp. 1\u20137). https:\/\/doi.org\/10.1109\/IPDPS.2007.370496","DOI":"10.1109\/IPDPS.2007.370496"},{"key":"706_CR4","doi-asserted-by":"publisher","unstructured":"Agrawal, K., Leiserson, C. E., He, Y., & Hsu, W. (2008). Adaptive work-stealing with parallelism feedback. ACM Transactions on Computing Systems. https:\/\/doi.org\/10.1145\/1394441.1394443","DOI":"10.1145\/1394441.1394443"},{"key":"706_CR5","unstructured":"Alon, N., & Spencer, J. (1992). The probabilistic method. Wiley."},{"key":"706_CR6","doi-asserted-by":"publisher","unstructured":"Arora, N. S., Blumofe, R. D., & Plaxton, C. G. (1998). Thread scheduling for multiprogrammed multiprocessors. In SPAA (pp. 119\u2013129). https:\/\/doi.org\/10.1145\/277651.277678","DOI":"10.1145\/277651.277678"},{"key":"706_CR7","doi-asserted-by":"publisher","unstructured":"Arora, N. S., Blumofe, R. D., & Plaxton, C. G. (2001). Thread scheduling for multiprogrammed multi processors. Theory of Computing Systems, 34(2), 115\u2013144. https:\/\/doi.org\/10.1007\/s00224-001-0004-z","DOI":"10.1007\/s00224-001-0004-z"},{"key":"706_CR8","doi-asserted-by":"publisher","unstructured":"Attiya, H., Guerraoui, R., Hendler, D., Kuznetsov, P., Michael, M. M., & Vechev, M. T. (2011). Laws of order: Expensive synchronization in concurrent algorithms cannot be eliminated. In Proceedings of the 38th ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL 2011, January 26\u201328, 2011 (pp. 487\u2013498). https:\/\/doi.org\/10.1145\/1926385.1926442","DOI":"10.1145\/1926385.1926442"},{"key":"706_CR9","doi-asserted-by":"publisher","unstructured":"Blumofe, R. D., Joerg, C. F., Kuszmaul, B. C., Leiserson, C. E., Randall, K. H., & Zhou, Y. (1996). Cilk: An efficient multithreaded runtime system. Journal of Parallel and Distributed Computing, 37(1), 55\u201369. https:\/\/doi.org\/10.1006\/jpdc.1996.0107","DOI":"10.1006\/jpdc.1996.0107"},{"key":"706_CR10","doi-asserted-by":"publisher","unstructured":"Blumofe, R. D., & Leiserson, C. E. (1999). Scheduling multithreaded computations by work stealing. Journal of the ACM, 46(5), 720\u2013748. https:\/\/doi.org\/10.1145\/324133.324234","DOI":"10.1145\/324133.324234"},{"key":"706_CR11","doi-asserted-by":"crossref","unstructured":"Blumofe, R. D., & Papadopoulos, D. (1998). The performance of work stealing in multiprogrammed environments. In ACM sigmetrics performance evaluation review (Vol. 26, pp. 266\u2013267).","DOI":"10.1145\/277858.277939"},{"key":"706_CR12","unstructured":"Blumofe, R. D., Plaxton, C. G., & Ray, S. (1999). Verification of a concurrent deque implementation. University of Texas at Austin."},{"key":"706_CR13","doi-asserted-by":"publisher","unstructured":"Chase, D., & Lev, Y. (2005). Dynamic circular work-stealing deque. In SPAA 2005: Proceedings of the 17th annual ACM symposium on parallelism in algorithms and architectures, July 18\u201320, 2005 (pp. 21\u201328). https:\/\/doi.org\/10.1145\/1073970.1073974","DOI":"10.1145\/1073970.1073974"},{"key":"706_CR14","doi-asserted-by":"publisher","unstructured":"Dinan, J., Krishnamoorthy, S., Larkins, D. B., Nieplocha, J., & Sadayappan, P. (2008). Scioto: A framework for global-view task parallelism. In 2008 International conference on parallel processing, ICPP 2008, September 8\u201312, 2008 (pp. 586-593). Retrieved from https:\/\/doi.org\/10.1109\/ICPP.2008.44","DOI":"10.1109\/ICPP.2008.44"},{"key":"706_CR15","doi-asserted-by":"publisher","unstructured":"Dinan, J., Larkins, D. B., Sadayappan, P., Krishnamoorthy, S., & Nieplocha, J. (2009). Scalable work stealing. In Proceedings of the ACM\/IEEE conference on high performance computing, SC 2009, November 14\u201320, 2009. https:\/\/doi.org\/10.1145\/1654059.1654113","DOI":"10.1145\/1654059.1654113"},{"key":"706_CR16","doi-asserted-by":"publisher","unstructured":"Endo, T., Taura, K., & Yonezawa, A. (1997). A scalable mark-sweep garbage collector on large-scale shared-memory machines. In Proceedings of the ACM\/IEEE conference on supercomputing, SC 1997, November 15\u201321, 1997 (p. 48). Retrieved from https:\/\/doi.org\/10.1145\/509593.509641","DOI":"10.1145\/509593.509641"},{"key":"706_CR17","doi-asserted-by":"publisher","unstructured":"Frigo, M., Leiserson, C. E., & Randall, K. H. (1998). The implementation of the Cilk-5 multithreaded language. In Proceedings of the ACM SIGPLAN \u201998 conference on programming language design and implementation (PLDI), June 17\u201319, 1998 (pp. 212\u2013223). ACM. https:\/\/doi.org\/10.1145\/277650.277725","DOI":"10.1145\/277650.277725"},{"key":"706_CR18","doi-asserted-by":"publisher","unstructured":"Hiraishi, T., Yasugi, M., Umatani, S., & Yuasa, T. (2009). Backtracking-based load balancing. In Proceedings of the 14th ACM SIGPLAN symposium on principles and practice of parallel programming, PPOPP 2009, February 14\u201318, 2009 (pp. 55\u201364). Retrieved from https:\/\/doi.org\/10.1145\/1504176.1504187","DOI":"10.1145\/1504176.1504187"},{"key":"706_CR19","doi-asserted-by":"publisher","unstructured":"Lifflander, J., Krishnamoorthy, S., & Kal\u00e9, L. V. (2012). Work stealing and persistence-based load balancers for iterative overdecomposed applications. In The 21st international symposium on high-performance parallel and distributed computing, HPDC\u201912, June 18\u201322, 2012 (pp. 137\u2013148). Retrieved from https:\/\/doi.org\/10.1145\/2287076.2287103","DOI":"10.1145\/2287076.2287103"},{"key":"706_CR20","doi-asserted-by":"publisher","unstructured":"Michael, M. M., Vechev, M. T., & Saraswat, V. A. (2009). Idempotent work stealing. In Proceedings of the 14th ACM SIGPLAN symposium on principles and practice of parallel programming, PPOPP 2009, February 14\u201318, 2009 (pp. 45\u201354). https:\/\/doi.org\/10.1145\/1504176.1504186","DOI":"10.1145\/1504176.1504186"},{"key":"706_CR21","doi-asserted-by":"publisher","unstructured":"Morrison, A., & Afek, Y. (2014). Fence-free work stealing on bounded TSO processors. In Architectural support for programming languages and operating systems, ASPLOS \u201914, March 1\u20135, 2014 (pp. 413\u2013426). https:\/\/doi.org\/10.1145\/2541940.2541987","DOI":"10.1145\/2541940.2541987"},{"key":"706_CR22","doi-asserted-by":"publisher","unstructured":"Muller, S. K., & Acar, U. A. (2016). Latency-hiding work stealing: Scheduling interacting parallel computations with work stealing. In Proceedings of the 28th ACM symposium on parallelism in algorithms and architectures, SPAA 2016, July 11\u201313, 2016 (pp. 71\u201382). https:\/\/doi.org\/10.1145\/2935764.2935793","DOI":"10.1145\/2935764.2935793"},{"key":"706_CR23","doi-asserted-by":"publisher","unstructured":"Sewell, P., Sarkar, S., Owens, S., Nardelli, F. Z., & Myreen, M. O. (2010). x86-tso: A rigorous and usable programmer\u2019s model for x86 multiprocessors. Communications of the ACM, 53(7), 89\u201397. https:\/\/doi.org\/10.1145\/1785414.1785443","DOI":"10.1145\/1785414.1785443"},{"key":"706_CR24","doi-asserted-by":"publisher","unstructured":"Tchiboukdjian, M., Gast, N., Trystram, D., Roch, J., & Bernard, J. (2010). A tighter analysis of work stealing. In Algorithms and computation\u201421st international symposium, ISAAC 2010, December 15\u201317, 2010, proceedings, part II (pp. 291\u2013302). https:\/\/doi.org\/10.1007\/978-3-642-17514-5_25","DOI":"10.1007\/978-3-642-17514-5_25"},{"key":"706_CR25","doi-asserted-by":"publisher","unstructured":"Tzannes, A., Barua, R., & Vishkin, U. (2011). Improving run-time scheduling for general-purpose parallel code. In L. Rauchwerger & V. Sarkar (Eds.), 2011 International conference on parallel architectures and compilation techniques, PACT 2011, October 10\u201314, 2011 (p. 216). IEEE Computer Society. https:\/\/doi.org\/10.1109\/PACT.2011.49","DOI":"10.1109\/PACT.2011.49"},{"key":"706_CR26","doi-asserted-by":"publisher","unstructured":"van Dijk, T., & van de Pol, J. C. (2014). Lace: Nonblocking split deque for work-stealing. In Europar 2014: Parallel processing workshops\u2014Europar 2014 international workshops, August 25\u201326, 2014, revised selected papers, part II (pp. 206\u2013217). https:\/\/doi.org\/10.1007\/978-3-319-14313-2_18","DOI":"10.1007\/978-3-319-14313-2_18"},{"key":"706_CR27","unstructured":"van Ede, T. (2015). Certainty in lockless concurrent algorithms: An informal proof of lace (Technical Report). University of Twente."}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00706-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-021-00706-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00706-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,2]],"date-time":"2022-03-02T01:05:29Z","timestamp":1646183129000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-021-00706-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,21]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["706"],"URL":"https:\/\/doi.org\/10.1007\/s10951-021-00706-6","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-562276\/v1","asserted-by":"object"}]},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,21]]},"assertion":[{"value":"10 August 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 October 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}