{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T05:04:36Z","timestamp":1764997476133,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031125966"},{"type":"electronic","value":"9783031125973"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"vor","delay-in-days":212,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this work, we address an online job scheduling problem in a large distributed computing environment. Each job has a priority and a demand of resources, takes an unknown amount of time, and is malleable, i.e., the number of allotted workers can fluctuate during its execution. We subdivide the problem into (a) determining a fair amount of resources for each job and (b) assigning each job to an according number of processing elements. Our approach is fully decentralized, uses lightweight communication, and arranges each job as a binary tree of workers which can grow and shrink as necessary. Using the NP-complete problem of propositional satisfiability (SAT) as a case study, we experimentally show on up to 128 machines (6144 cores) that our approach leads to near-optimal utilization, imposes minimal computational overhead, and performs fair scheduling of incoming jobs within a few milliseconds.<\/jats:p>","DOI":"10.1007\/978-3-031-12597-3_8","type":"book-chapter","created":{"date-parts":[[2022,7,31]],"date-time":"2022-07-31T10:02:21Z","timestamp":1659261741000},"page":"119-135","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Decentralized Online Scheduling of\u00a0Malleable NP-hard Jobs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3330-9349","authenticated-orcid":false,"given":"Peter","family":"Sanders","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4185-1851","authenticated-orcid":false,"given":"Dominik","family":"Schreiber","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,1]]},"reference":[{"issue":"1","key":"8_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/tc.1985.5009385","volume":"3","author":"M Ajtai","year":"1983","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: Sorting in $$\\log n$$ parallel steps. Combinatorica 3(1), 1\u201319 (1983). https:\/\/doi.org\/10.1109\/tc.1985.5009385","journal-title":"Combinatorica"},{"key":"8_CR2","unstructured":"Alquraan, A., Takruri, H., Alfatafta, M., Al-Kiswany, S.: An analysis of network-partitioning failures in cloud systems. In: Symposium on Operating Systems Design and Implementation, pp. 51\u201368 (2018)"},{"key":"8_CR3","unstructured":"Audemard, G., Simon, L.: Predicting learnt clauses quality in modern SAT solvers. In: International Joint Conference on Artificial Intelligence, pp. 399\u2013404 (2009)"},{"key":"8_CR4","doi-asserted-by":"publisher","unstructured":"Axtmann, M., Sanders, P.: Robust massively parallel sorting. In: Meeting on Algorithm Engineering and Experiments (ALENEX), pp. 83\u201397 (2017). https:\/\/doi.org\/10.1137\/1.9781611974768.7","DOI":"10.1137\/1.9781611974768.7"},{"issue":"4","key":"8_CR5","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1109\/tc.2006.58","volume":"55","author":"J Blazewicz","year":"2006","unstructured":"Blazewicz, J., Kovalyov, M.Y., Machowiak, M., Trystram, D., Weglarz, J.: Preemptable malleable task scheduling problem. IEEE Trans. Comput. 55(4), 486\u2013490 (2006). https:\/\/doi.org\/10.1109\/tc.2006.58","journal-title":"IEEE Trans. Comput."},{"key":"8_CR6","doi-asserted-by":"publisher","unstructured":"Buisson, J., Sonmez, O., Mohamed, H., Lammers, W., Epema, D.: Scheduling malleable applications in multicluster systems. In: International Conference on Cluster Computing, pp. 372\u2013381. IEEE (2007). https:\/\/doi.org\/10.1109\/clustr.2007.4629252","DOI":"10.1109\/clustr.2007.4629252"},{"key":"8_CR7","unstructured":"Castro, M., Liskov, B.: Practical byzantine fault tolerance. In: Symposium on Operating Systems Design and Implementation. pp. 173\u2013186 (1999)"},{"key":"8_CR8","doi-asserted-by":"publisher","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: ACM symposium on Theory of Computing, pp. 151\u2013158 (1971). https:\/\/doi.org\/10.7551\/mitpress\/12274.003.0036","DOI":"10.7551\/mitpress\/12274.003.0036"},{"issue":"3","key":"8_CR9","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s10586-007-0032-9","volume":"10","author":"T Desell","year":"2007","unstructured":"Desell, T., El Maghraoui, K., Varela, C.A.: Malleable applications for scalable high performance computing. Clust. Comput. 10(3), 323\u2013337 (2007). https:\/\/doi.org\/10.1007\/s10586-007-0032-9","journal-title":"Clust. Comput."},{"key":"8_CR10","unstructured":"Feitelson, D.G.: Job scheduling in multiprogrammed parallel systems (1997)"},{"key":"8_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103572","volume":"301","author":"N Froleyks","year":"2021","unstructured":"Froleyks, N., Heule, M., Iser, M., J\u00e4rvisalo, M., Suda, M.: SAT competition 2020. Artif. Intell. 301, 103572 (2021). https:\/\/doi.org\/10.1016\/j.artint.2021.103572","journal-title":"Artif. Intell."},{"key":"8_CR12","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/7056.001.0001","volume-title":"Using MPI: Portable Parallel Programming with the Message-Passing Interface","author":"W Gropp","year":"1999","unstructured":"Gropp, W., Lusk, E., Skjellum, A.: Using MPI: Portable Parallel Programming with the Message-Passing Interface, vol. 1. MIT Press, London (1999). https:\/\/doi.org\/10.7551\/mitpress\/7056.001.0001"},{"key":"8_CR13","doi-asserted-by":"publisher","unstructured":"Gupta, A., Acun, B., Sarood, O., Kal\u00e9, L.V.: Towards realizing the potential of malleable jobs. In: International Conference on High Performance Computing (HiPC), pp. 1\u201310. IEEE (2014). https:\/\/doi.org\/10.1109\/hipc.2014.7116905","DOI":"10.1109\/hipc.2014.7116905"},{"issue":"4","key":"8_CR14","doi-asserted-by":"publisher","first-page":"245","DOI":"10.3233\/sat190070","volume":"6","author":"Y Hamadi","year":"2010","unstructured":"Hamadi, Y., Jabbour, S., Sais, L.: ManySAT: a parallel SAT solver. J. Satisf. Boolean Model. Comput. 6(4), 245\u2013262 (2010). https:\/\/doi.org\/10.3233\/sat190070","journal-title":"J. Satisf. Boolean Model. Comput."},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/978-3-030-51825-7_9","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2020","author":"M Heisinger","year":"2020","unstructured":"Heisinger, M., Fleury, M., Biere, A.: Distributed cube and conquer with Paracooba. In: Pulina, L., Seidl, M. (eds.) SAT 2020. LNCS, vol. 12178, pp. 114\u2013122. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-51825-7_9"},{"key":"8_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/978-3-540-24644-2_20","volume-title":"Languages and Compilers for Parallel Computing","author":"C Huang","year":"2004","unstructured":"Huang, C., Lawlor, O., Kal\u00e9, L.V.: Adaptive MPI. In: Rauchwerger, L. (ed.) LCPC 2003. LNCS, vol. 2958, pp. 306\u2013322. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24644-2_20"},{"key":"8_CR17","doi-asserted-by":"publisher","unstructured":"Hungershofer, J.: On the combined scheduling of malleable and rigid jobs. In: Symposium on Computer Architecture and HPC, pp. 206\u2013213. IEEE (2004). https:\/\/doi.org\/10.1109\/sbac-pad.2004.27","DOI":"10.1109\/sbac-pad.2004.27"},{"key":"8_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-030-32409-4_2","volume-title":"Formal Methods and Software Engineering","author":"M Kleine B\u00fcning","year":"2019","unstructured":"Kleine B\u00fcning, M., Balyo, T., Sinz, C.: Using DimSpec for bounded and unbounded software model checking. In: Ait-Ameur, Y., Qin, S. (eds.) ICFEM 2019. LNCS, vol. 11852, pp. 19\u201335. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-32409-4_2"},{"key":"8_CR19","doi-asserted-by":"publisher","unstructured":"Marques-Silva, J., Lynce, I., Malik, S.: Conflict-driven clause learning SAT solvers. In: Handbook of Satisfiability, pp. 131\u2013153. IOS Press (2009). https:\/\/doi.org\/10.3233\/faia200987","DOI":"10.3233\/faia200987"},{"issue":"1","key":"8_CR20","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1023\/A:1006326723002","volume":"24","author":"F Massacci","year":"2000","unstructured":"Massacci, F., Marraro, L.: Logical cryptanalysis as a SAT problem. J. Autom. Reason. 24(1), 165\u2013203 (2000). https:\/\/doi.org\/10.1023\/A:1006326723002","journal-title":"J. Autom. Reason."},{"key":"8_CR21","doi-asserted-by":"publisher","unstructured":"Ozdemir, A., Wu, H., Barrett, C.: SAT solving in the serverless cloud. In: Formal Methods in Computer Aided Design (FMCAD), pp. 241\u2013245. IEEE (2021). https:\/\/doi.org\/10.34727\/2021\/isbn.978-3-85448-046-4_33","DOI":"10.34727\/2021\/isbn.978-3-85448-046-4_33"},{"key":"8_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25209-0","volume-title":"Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox","author":"P Sanders","year":"2019","unstructured":"Sanders, P., Mehlhorn, K., Dietzfelbinger, M., Dementiev, R.: Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-25209-0"},{"key":"8_CR23","doi-asserted-by":"publisher","unstructured":"Sanders, P., Schreiber, D.: Artifact and instructions to generate experimental results for the Euro-Par 2022 paper: \u201cDecentralized Online Scheduling of Malleable NP-hard Jobs\u201d. https:\/\/doi.org\/10.6084\/m9.figshare.20000642","DOI":"10.6084\/m9.figshare.20000642"},{"key":"8_CR24","doi-asserted-by":"publisher","unstructured":"Sanders, P., Speck, J.: Efficient parallel scheduling of malleable tasks. In: International Parallel and Distributed Processing Symposium, pp. 1156\u20131166. IEEE (2011). https:\/\/doi.org\/10.1109\/ipdps.2011.110","DOI":"10.1109\/ipdps.2011.110"},{"key":"8_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-642-32820-6_18","volume-title":"Euro-Par 2012 Parallel Processing","author":"P Sanders","year":"2012","unstructured":"Sanders, P., Speck, J.: Energy efficient frequency scaling and scheduling for malleable tasks. In: Kaklamanis, C., Papatheodorou, T., Spirakis, P.G. (eds.) Euro-Par 2012. LNCS, vol. 7484, pp. 167\u2013178. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32820-6_18"},{"key":"8_CR26","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1613\/jair.1.12520","volume":"70","author":"D Schreiber","year":"2021","unstructured":"Schreiber, D.: Lilotane: a lifted SAT-based approach to hierarchical planning. J. Artif. Intell. Res. 70, 1117\u20131181 (2021). https:\/\/doi.org\/10.1613\/jair.1.12520","journal-title":"J. Artif. Intell. Res."},{"key":"8_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1007\/978-3-030-80223-3_35","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2021","author":"D Schreiber","year":"2021","unstructured":"Schreiber, D., Sanders, P.: Scalable SAT solving in the cloud. In: Li, C.-M., Many\u00e0, F. (eds.) SAT 2021. LNCS, vol. 12831, pp. 518\u2013534. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-80223-3_35"}],"container-title":["Lecture Notes in Computer Science","Euro-Par 2022: Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-12597-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,11]],"date-time":"2022-08-11T23:14:34Z","timestamp":1660259674000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-12597-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031125966","9783031125973"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-12597-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 August 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Euro-Par","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Conference on Parallel Processing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Glasgow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 August 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 August 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"europar2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/2022.euro-par.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"102","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.97","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}