{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T04:27:26Z","timestamp":1778732846676,"version":"3.51.4"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T00:00:00Z","timestamp":1695254400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>\n            The Conditional DAG (CDAG) task model is used for modeling multiprocessor real-time systems containing conditional expressions for which outcomes are not known prior to their evaluation. Feasibility analysis for CDAG tasks upon multiprocessor platforms is shown to be complete for the complexity class\n            <jats:sc>pspace<\/jats:sc>\n            ; assuming\n            <jats:sc>np<\/jats:sc>\n            \u2260\n            <jats:sc>pspace<\/jats:sc>\n            , this result rules out the use of Integer Linear Programming solvers for solving this problem efficiently. It is further shown that there can be no pseudo-polynomial time algorithm that solves this problem unless\n            <jats:sc>p<\/jats:sc>\n            =\n            <jats:sc>pspace<\/jats:sc>\n            .\n          <\/jats:p>","DOI":"10.1145\/3606342","type":"journal-article","created":{"date-parts":[[2023,7,5]],"date-time":"2023-07-05T12:21:12Z","timestamp":1688559672000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["The Computational Complexity of Feasibility Analysis for Conditional DAG Tasks"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4541-3445","authenticated-orcid":false,"given":"Sanjoy","family":"Baruah","sequence":"first","affiliation":[{"name":"Washington University in Saint\u00a0Louis"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7991-4416","authenticated-orcid":false,"given":"Alberto","family":"Marchetti-Spaccamela","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,9,21]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"165","volume-title":"Proceedings of the 29th International Conference on Real-Time and Network Systems (RTNS\u201921)","author":"Baruah Sanjoy","year":"2020","unstructured":"Sanjoy Baruah. 2020. Feasibility analysis of conditional DAG tasks is co- \\(\\mathrm{NP^{\\mbox{NP}} }\\) -hard (why this matters). In Proceedings of the 29th International Conference on Real-Time and Network Systems (RTNS\u201921). ACM, 165\u2013172."},{"key":"e_1_3_2_3_2","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1109\/ECRTS.2015.27","volume-title":"Proceedings of the 26th Euromicro Conference on Real-Time Systems (ECRTS\u201915)","author":"Baruah Sanjoy","year":"2015","unstructured":"Sanjoy Baruah, Vincenzo Bonifaci, and Alberto Marchetti-Spaccamela. 2015. The global EDF scheduling of systems of conditional sporadic DAG tasks. In Proceedings of the 26th Euromicro Conference on Real-Time Systems (ECRTS\u201915). IEEE Computer Society Press, 222\u2013231."},{"key":"e_1_3_2_4_2","first-page":"63","volume-title":"Proceedings of the IEEE Real-Time Systems Symposium (RTSS\u201912)","author":"Baruah Sanjoy","year":"2012","unstructured":"Sanjoy Baruah, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Leem Stougie, and Andreas Wiese. 2012. A generalized parallel task model for recurrent real-time processes. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS\u201912). IEEE Computer Society Press, 63\u201372."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECRTS.2021.12"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/1882123.1882149"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9505-6"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3322809"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"1925","DOI":"10.1145\/2695664.2695808","volume-title":"Proceedings of the ACM\/ SIGAPP Symposium on Applied Computing (SAC\u201915)","author":"Fonseca Jose","year":"2015","unstructured":"Jose Fonseca, Vincent Nelis, Gurulingesh Raravi, and Luis Miguel Pinho. 2015. A Multi-DAG model for real-time parallel applications with conditional execution. In Proceedings of the ACM\/ SIGAPP Symposium on Applied Computing (SAC\u201915). ACM Press, 1925\u20131932."},{"key":"e_1_3_2_10_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M.","year":"1979","unstructured":"M. Garey and D. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, NY."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-012-9172-y"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/1541932"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90142-2"},{"key":"e_1_3_2_14_2","first-page":"1061","volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201920)","author":"Marchetti-Spaccamela Alberto","year":"2020","unstructured":"Alberto Marchetti-Spaccamela, Nicole Megow, Jens Schl\u00f6ter, Martin Skutella, and Leen Stougie. 2020. On the complexity of conditional DAG scheduling in multiprocessor systems. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201920). 1061\u20131070."},{"key":"e_1_3_2_15_2","first-page":"222","volume-title":"Proceedings of the 26th Euromicro Conference on Real-Time Systems (ECRTS\u201915)","author":"Melani Alessandra","year":"2015","unstructured":"Alessandra Melani, Marko Bertogna, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, and Giorgio Buttazzo. 2015. Response-time analysis of conditional DAG tasks in multiprocessor systems. In Proceedings of the 26th Euromicro Conference on Real-Time Systems (ECRTS\u201915). IEEE Computer Society Press, 222\u2013231."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80008-0"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90062-1"},{"issue":"10","key":"e_1_3_2_19_2","first-page":"1747","article-title":"The HPC-DAG task model for heterogeneous real-time systems","volume":"70","author":"Zahaf Houssam-Eddine","year":"2020","unstructured":"Houssam-Eddine Zahaf, Nicola Capodieci, Roberto Cavicchioli, Marko Bertogna, and Giuseppe Lipari. 2020. The HPC-DAG task model for heterogeneous real-time systems. IEEE Trans. Comput. 70, 10 (2020), 1747\u20131761.","journal-title":"IEEE Trans. Comput."}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3606342","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3606342","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:08Z","timestamp":1750178828000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3606342"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,21]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3606342"],"URL":"https:\/\/doi.org\/10.1145\/3606342","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,21]]},"assertion":[{"value":"2022-08-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-27","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}