{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,12]],"date-time":"2026-09-12T17:22:51Z","timestamp":1789233771860,"version":"build-2803163510"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"name":"Innovate UK SCHEME","award":["10065634"],"award-info":[{"award-number":["10065634"]}]},{"name":"EPSRC Research Data Management","award":["RPG-2019-020"],"award-info":[{"award-number":["RPG-2019-020"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2025,11,30]]},"abstract":"<jats:p>\n            This article presents a general formal framework for describing the relationship between a criticality-aware scheduler, a set of application jobs that are assigned different criticality levels, and an environment that generates both work and faults that the run-time system must control. The proposed formalism extends the rely-guarantee approach, which facilitates formal reasoning about the functional behaviour of concurrent systems, to address\n            <jats:italic toggle=\"yes\">real-time<\/jats:italic>\n            properties. The exposition of the general framework is supplemented by a seven step approach that enables it to be instantiated to deliver the formal specification of any proposed mixed-criticality scheduling protocol. The expressive power of the approach is explored via a non-trivial instantiation.\n          <\/jats:p>\n          <jats:p\/>\n          <jats:p\/>","DOI":"10.1145\/3765522","type":"journal-article","created":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T11:24:33Z","timestamp":1756725873000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A Specification Framework for Mixed-Criticality Scheduling Protocols"],"prefix":"10.1145","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5621-8816","authenticated-orcid":false,"given":"Alan","family":"Burns","sequence":"first","affiliation":[{"name":"Computer Science, University of York","place":["York, United Kingdom of Great Britain and Northern Ireland"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0038-6623","authenticated-orcid":false,"given":"Cliff","family":"Jones","sequence":"additional","affiliation":[{"name":"School of Computing, Newcastle University","place":["Newcastle upon Tyne, United Kingdom of Great Britain and Northern Ireland"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,10,13]]},"reference":[{"key":"e_1_3_4_2_2","volume-title":"The B-Book: Assigning Programs to Meanings","author":"Abrial J.-R.","unstructured":"J.-R. Abrial. 1996. The B-Book: Assigning Programs to Meanings. Cambridge University Press."},{"key":"e_1_3_4_3_2","volume-title":"The Event-B Book","author":"Abrial J.-R.","unstructured":"J.-R. Abrial. 2010. The Event-B Book. Cambridge University Press, Cambridge, UK."},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00165-4"},{"key":"e_1_3_4_5_2","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1049\/sej.1993.0034","article-title":"Applying new scheduling theory to static priority preemptive scheduling","volume":"8","author":"Audsley N. C.","year":"1993","unstructured":"N. C. Audsley, A. Burns, M. Richardson, K. Tindell, and A. J. Wellings. 1993. Applying new scheduling theory to static priority preemptive scheduling. Software Engineering Journal 8, 5 (1993), 284\u2013292.","journal-title":"Software Engineering Journal"},{"key":"e_1_3_4_6_2","volume-title":"Proceedings of the IEEE Real-Time Systems Symposium. 34\u201343","author":"Baruah S. K.","unstructured":"S. K. Baruah, A. Burns, and R. I. Davis. 2011 Response-time analysis for mixed criticality systems. In Proceedings of the IEEE Real-Time Systems Symposium. 34\u201343."},{"key":"e_1_3_4_7_2","volume-title":"Proceedings of the IEEE Real-Time Systems Symposium. 182\u2013190","author":"Baruah S. K.","unstructured":"S. K. Baruah, A. K. Mok, and L. E. Rosier. 1990. Preemptive scheduling of hard real-time sporadic tasks on one processor. In Proceedings of the IEEE Real-Time Systems Symposium. 182\u2013190."},{"key":"e_1_3_4_8_2","volume-title":"Proceedings of the 27th ECRTS. 259\u2013268","author":"Bate I.","unstructured":"I. Bate, A. Burns, and R. I. Davis. 2015. A bailout protocol for mixed criticality systems. In Proceedings of the 27th ECRTS. 259\u2013268."},{"key":"e_1_3_4_9_2","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1109\/TSE.2016.2592907","article-title":"An enhanced bailout protocol for mixed criticality embedded software","volume":"43","author":"Bate I.","year":"2016","unstructured":"I. Bate, A. Burns, and R. I. Davis. 2016. An enhanced bailout protocol for mixed criticality embedded software. IEEE Transactions on Software Engineering 43, 4 (2016), 298\u2013320.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"e_1_3_4_10_2","volume-title":"Proceedings of the 2022 IEEE Real-Time Systems Symposium. IEEE, 197\u2013210","author":"Bedarkar Kimaya","unstructured":"Kimaya Bedarkar, Mariam Vardishvili, Sergey Bozhko, Marco Maida, and Bj\u00f6rn B. Brandenburg. 2022. From intuition to Coq: A case study in verified response-time analysis of FIFO scheduling. In Proceedings of the 2022 IEEE Real-Time Systems Symposium. IEEE, 197\u2013210."},{"key":"e_1_3_4_11_2","volume-title":"Proceedings of the 32nd Euromicro Conference on Real-Time Systems. 6.1\u20136.23","author":"Bozhko Sergey","unstructured":"Sergey Bozhko and Bj\u00f6rn B. Brandenburg. 2020. Abstract response-time analysis: A formal foundation for the busy-window principle. In Proceedings of the 32nd Euromicro Conference on Real-Time Systems. 6.1\u20136.23."},{"key":"e_1_3_4_12_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3131347","article-title":"A survey of research into mixed criticality systems","volume":"50","author":"Burns A.","year":"2017","unstructured":"A. Burns and R. I. Davis. 2017. A survey of research into mixed criticality systems. ACM Computer Surveys 50, 6 (2017), 1\u201337.","journal-title":"ACM Computer Surveys"},{"key":"e_1_3_4_13_2","volume-title":"Retrieved","author":"Burns A.","year":"2025","unstructured":"A. Burns and R. I. Davis. 2022. Mixed criticality systems: A review (13th edition). Technical report MCC-1(13). Retrieved September 23, 2025 from https:\/\/www-users.cs.york.ac.uk\/ab38\/review.pdf"},{"key":"e_1_3_4_14_2","unstructured":"A. Burns and A. J. Wellings. 2016. Analysable Real-Time Systems Programmed in Ada. ISBN: 9781530265503."},{"key":"e_1_3_4_15_2","first-page":"1","article-title":"A timeband framework for modelling real-time systems","volume":"45","author":"Burns Alan","year":"2010","unstructured":"Alan Burns and Ian J. Hayes. 2010. A timeband framework for modelling real-time systems. Real-Time Systems 45, 1\u20132 (2010), 106\u2013142, 6.","journal-title":"Real-Time Systems"},{"key":"e_1_3_4_16_2","doi-asserted-by":"crossref","first-page":"774","DOI":"10.1093\/comjnl\/bxz019","article-title":"Deriving specifications of control programs for cyber physical systems","volume":"63","author":"Burns Alan","year":"2020","unstructured":"Alan Burns, Ian J. Hayes, and Cliff B. Jones. 2020. Deriving specifications of control programs for cyber physical systems. The Computer Journal 63, 5 (2020), 774\u2013790.","journal-title":"The Computer Journal"},{"key":"e_1_3_4_17_2","volume-title":"Jones","author":"Burns Alan","year":"2024","unstructured":"Alan Burns and Cliff B. Jones. 2024. Specifying fault-tolerant mixed-criticality scheduling. The Application of Formal Methods: Essays Dedicated to Jim Woodcock on the Occasion of His Retirement, Simon Foster and Augusto Sampaio (Eds.). Springer Nature Switzerland, 22\u201342."},{"key":"e_1_3_4_18_2","volume-title":"Proceedings of the 2016 28th Euromicro Conference on Real-Time Systems. IEEE, 273\u2013284","author":"Cerqueira Felipe","unstructured":"Felipe Cerqueira, Felix Stutz, and Bj\u00f6rn B. Brandenburg. 2016 Prosa: A case for readable mechanized schedulability analysis. In Proceedings of the 2016 28th Euromicro Conference on Real-Time Systems. IEEE, 273\u2013284."},{"key":"e_1_3_4_19_2","volume-title":"Real-time Systems: Scheduling, Analysis, and Verification","author":"Cheng Albert M. K.","year":"2003","unstructured":"Albert M. K. Cheng. 2003. Real-time Systems: Scheduling, Analysis, and Verification. John Wiley & Sons."},{"key":"e_1_3_4_20_2","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.1109\/TC.2008.66","article-title":"Efficient exact schedulability tests for fixed priority pre-emptive systems","volume":"57","author":"Davis R. I.","year":"2008","unstructured":"R. I. Davis, A. Zabos, and A. Burns. 2008. Efficient exact schedulability tests for fixed priority pre-emptive systems. IEEE Transaction on Computers 57, 9 (2008), 1261\u20131276.","journal-title":"IEEE Transaction on Computers"},{"key":"e_1_3_4_21_2","volume-title":"Concurrency Verification: Introduction to Compositional and Noncompositional Methods","author":"de Roever Willem-Paul","year":"2001","unstructured":"Willem-Paul de Roever, Frank de Boer, Ulrich Hanneman, Jozef Hooman, Yassine Lakhnech, Mannes Poel, and Job Zwiers. 2001. Concurrency Verification: Introduction to Compositional and Noncompositional Methods. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press."},{"key":"e_1_3_4_22_2","volume-title":"Proceedings (Cat. No.00CH37126)","author":"Dutertre B.","year":"2000","unstructured":"B. Dutertre and V. Stavridou. 2000. Formal analysis for real-time scheduling. In 19th DASC. 19th Digital Avionics Systems Conference. Proceedings (Cat. No.00CH37126) 1 (2000), 1D4\u20131."},{"key":"e_1_3_4_23_2","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1109\/MDAT.2016.2594790","article-title":"Mixed criticality systems?a history of misconceptions","volume":"33","author":"Ernst R.","year":"2016","unstructured":"R. Ernst and M. Di Natale. 2016. Mixed criticality systems?a history of misconceptions? IEEE Design and Test 33, 5 (2016), 65\u201374.","journal-title":"IEEE Design and Test"},{"key":"e_1_3_4_24_2","volume-title":"Proceedings of the 23rd International Conference on Real-Time Networks and Systems (RTNS","author":"Esper A.","year":"2015","unstructured":"A. Esper, G. Neilissen, V. Neils, and E. Tovar. 2015. How realistic is the mixed-criticality real-time system model. In Proceedings of the 23rd International Conference on Real-Time Networks and Systems (RTNS 2015). 139\u2013148."},{"key":"e_1_3_4_25_2","volume-title":"Proceedings of the WMC, RTSS. 19\u201324","author":"Graydon P.","unstructured":"P. Graydon and I. Bate. 2013. Safety assurance driven problem formulation for mixed-criticality scheduling. In Proceedings of the WMC, RTSS. 19\u201324."},{"key":"e_1_3_4_26_2","unstructured":"I. J. Hayes editor. 1992. Specification Case Studies. Prentice Hall International second edition."},{"key":"e_1_3_4_27_2","doi-asserted-by":"crossref","unstructured":"I. J. Hayes and C. B. Jones. 2018. A guide to rely\/guarantee thinking. In Proceedings of the 3rd International School of Engineering Trustworthy Software Systems. Jonathan Bowen Zhiming Liu and Zili Zhan (Eds) Lecture Notes in Computer Science Vol 11174 Springer-Verlag 1\u201338.","DOI":"10.1007\/978-3-030-02928-9_1"},{"key":"e_1_3_4_28_2","doi-asserted-by":"crossref","first-page":"10","DOI":"10.3390\/designs3010010","article-title":"A lazy bailout approach for dual-criticality systems on uniprocessor platforms","volume":"3","author":"Iacovelli S.","year":"2019","unstructured":"S. Iacovelli and R. Kirner. 2019. A lazy bailout approach for dual-criticality systems on uniprocessor platforms. Designs 3, 1 (2019), 10.","journal-title":"Designs"},{"key":"e_1_3_4_29_2","volume-title":"Software Abstractions: Logic, Language, and Analysis","author":"Jackson D. N.","year":"2012","unstructured":"D. N. Jackson. 2012. Software Abstractions: Logic, Language, and Analysis. MIT Press."},{"key":"e_1_3_4_30_2","volume-title":"Proceedings of the 7th WMC Workshop, IEEE Real-Time Systems Symposium, J. Li and Z. Guo (Eds.). 9\u201314","author":"Jiang Z.","year":"2019","unstructured":"Z. Jiang. 2019. How to build a mixed-criticality system in industry - from perspective of system architecture. In Proceedings of the 7th WMC Workshop, IEEE Real-Time Systems Symposium, J. Li and Z. Guo (Eds.). 9\u201314."},{"key":"e_1_3_4_31_2","volume-title":"Proceedings of the 8th WMC Workshop, IEEE Real-Time Systems Symposium. 510\u2013517","author":"Jiang Z.","year":"2020","unstructured":"Z. Jiang. 2020. How to build a mixed-criticality system in industry - from the perspective of system architecture. In Proceedings of the 8th WMC Workshop, IEEE Real-Time Systems Symposium. 510\u2013517."},{"key":"e_1_3_4_32_2","volume-title":"Proceedings of the IEEE 38th International Conference on Computer Design. 510\u2013517","author":"Jiang Z.","unstructured":"Z. Jiang, S. Zhao, P. Dong, D. Yang, R. Wei, N. Guan, and N. Audsley. 2020. Re-thinking mixed-criticality architecture for automotive industry. In Proceedings of the IEEE 38th International Conference on Computer Design. 510\u2013517."},{"key":"e_1_3_4_33_2","unstructured":"C. B. Jones. 1981. Development Methods for Computer Programs including a Notion of Interference. PhD thesis Oxford University 6. Printed as: Programming Research Group Technical Monograph 25."},{"key":"e_1_3_4_34_2","volume-title":"Proceedings of the IFIP\u201983","author":"Jones C. B.","year":"1983","unstructured":"C. B. Jones. 1983. Specification and design of (parallel) programs. In Proceedings of the IFIP\u201983. North-Holland, 321\u2013332."},{"key":"e_1_3_4_35_2","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/69575.69577","article-title":"Tentative steps toward a development method for interfering programs","volume":"5","author":"Jones C. B.","year":"1983","unstructured":"C. B. Jones. 1983. Tentative steps toward a development method for interfering programs. Transactions on Programming Languages and System 5, 4 (1983), 596\u2013619.","journal-title":"Transactions on Programming Languages and System"},{"key":"e_1_3_4_36_2","volume-title":"Systematic Software Development Using VDM","author":"Jones C. B.","unstructured":"C. B. Jones. 1990. Systematic Software Development Using VDM. Prentice Hall International, second edition."},{"key":"e_1_3_4_37_2","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/s10703-023-00441-y","article-title":"Extending rely-guarantee thinking to handle real-time scheduling","volume":"62","author":"Jones Cliff B.","year":"2024","unstructured":"Cliff B. Jones and Alan Burns. 2024. Extending rely-guarantee thinking to handle real-time scheduling. Formal Methods in System Design 62, 1 (2024), 119\u2013140.","journal-title":"Formal Methods in System Design"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/29.5.390"},{"key":"e_1_3_4_39_2","volume-title":"Proceedings of the 30th International Conference on Real Time Networks and Systems. ACM, 100\u2013110","author":"Law S.","unstructured":"S. Law, I. Bate, and B. Lesage. 2020. Justifying the service provided to low criticality tasks in a mixed criticality system. In Proceedings of the 30th International Conference on Real Time Networks and Systems. ACM, 100\u2013110."},{"key":"e_1_3_4_40_2","first-page":"1","article-title":"Generalized models of mixed-criticality systems for real-time scheduling","volume":"1","author":"Lee J.","year":"2020","unstructured":"J. Lee and M. Kim. 2020. Generalized models of mixed-criticality systems for real-time scheduling. Trans Eng Comput Sci 1, 1-50 (2020), 51.","journal-title":"Trans Eng Comput Sci"},{"key":"e_1_3_4_41_2","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1145\/321738.321743","article-title":"Scheduling algorithms for multiprogramming in a hard real-time environment","volume":"20","author":"Liu C. L.","year":"1973","unstructured":"C. L. Liu and J. W. Layland. 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. JACM 20, 1 (1973), 46\u201361.","journal-title":"JACM"},{"key":"e_1_3_4_42_2","volume-title":"Proceedings of the 34th Euromicro Conference on Real-Time Systems. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik.","author":"Maida Marco","year":"2022","unstructured":"Marco Maida, Sergey Bozhko, and Bj\u00f6rn B Brandenburg. 2022 Foundational response-time analysis as explainable evidence of timeliness. In Proceedings of the 34th Euromicro Conference on Real-Time Systems. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_4_43_2","volume-title":"Real-Time Systems: Formal Specification and Automatic Verification","author":"Olderog Ernst-R\u00fcdiger","unstructured":"Ernst-R\u00fcdiger Olderog and Henning Dierks. 2008. Real-Time Systems: Formal Specification and Automatic Verification. Cambridge University Press."},{"key":"e_1_3_4_44_2","volume-title":"Proceedings of the 30th Euromicro Conference on Real-Time Systems, Sebastian Altmeyer (Ed.).","volume":"106","author":"Papadopoulos A. V.","unstructured":"A. V. Papadopoulos, E. Bini, S. Baruah, and A. Burns. 2018. AdaptMC: A control-theoretic approach for achieving resilience in mixed-criticality systems. In Proceedings of the 30th Euromicro Conference on Real-Time Systems, Sebastian Altmeyer (Ed.). Vol. 106, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Leibniz International Proc. in Informatics (LIPIcs), 14:1\u201314:22."},{"key":"e_1_3_4_45_2","volume-title":"Proceedings of the Euromicro Conference on Digital System Design. IEEE, 453\u2013461","author":"Paulitsch M.","unstructured":"M. Paulitsch, O. M. Duarte, H. Karray, K. Mueller, D. Muench, and J. Nowotsch. 2015. Mixed-criticality embedded systems\u2013a balance ensuring partitioning and performance. In Proceedings of the Euromicro Conference on Digital System Design. IEEE, 453\u2013461."},{"key":"e_1_3_4_46_2","volume-title":"Proceedings of the 28th Asia and South Pacific Design Automation Conference. 320\u2013325","author":"Reghenzani F.","unstructured":"F. Reghenzani and W. Fornaciari. 2023. Mixed-criticality with integer multiple WCETs and dropping relations: New scheduling challenges. In Proceedings of the 28th Asia and South Pacific Design Automation Conference. 320\u2013325."},{"key":"e_1_3_4_47_2","volume-title":"Proceedings of the Real-Time Systems Symposium. 239\u2013243","author":"Vestal S.","year":"2007","unstructured":"S. Vestal. 2007. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proceedings of the Real-Time Systems Symposium. 239\u2013243."},{"key":"e_1_3_4_48_2","volume-title":"Proceedings of the 18th International Workshop on Worst-Case Execution Time Analysis, Florian Brandner (Ed.). Vol 63","author":"Wilhelm R.","year":"2018","unstructured":"R. Wilhelm. 2018. Mixed feelings about mixed criticality (invited paper). In Proceedings of the 18th International Workshop on Worst-Case Execution Time Analysis, Florian Brandner (Ed.). Vol 63, OpenAccess Series in Informatics (OASIcs), 1:1\u20131:9, Dagstuhl, Germany. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_4_49_2","volume-title":"Using Z: Specification, Refinement and Proof","author":"Woodcock Jim","unstructured":"Jim Woodcock and Jim Davies. 1996. Using Z: Specification, Refinement and Proof. Prentice Hall International."},{"key":"e_1_3_4_50_2","doi-asserted-by":"crossref","first-page":"1250","DOI":"10.1109\/TC.2009.58","article-title":"Schedulability analysis for real-time systems with EDF scheduling","volume":"58","author":"Zhang F.","year":"2008","unstructured":"F. Zhang and A. Burns. 2008. Schedulability analysis for real-time systems with EDF scheduling. IEEE Transaction on Computers 58, 9 (2008), 1250\u20131258.","journal-title":"IEEE Transaction on Computers"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3765522","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T14:11:03Z","timestamp":1760364663000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3765522"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,13]]},"references-count":49,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,11,30]]}},"alternative-id":["10.1145\/3765522"],"URL":"https:\/\/doi.org\/10.1145\/3765522","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,13]]},"assertion":[{"value":"2025-04-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}