{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,12]],"date-time":"2026-09-12T06:34:10Z","timestamp":1789194850210,"version":"build-2803163510"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,11,16]],"date-time":"2007-11-16T00:00:00Z","timestamp":1195171200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2008,2]]},"DOI":"10.1007\/s11241-007-9042-1","type":"journal-article","created":{"date-parts":[[2007,11,15]],"date-time":"2007-11-15T16:42:04Z","timestamp":1195144924000},"page":"133-189","source":"Crossref","is-referenced-by-count":75,"title":["Tardiness bounds under global EDF scheduling on\u00a0a\u00a0multiprocessor"],"prefix":"10.1007","volume":"38","author":[{"given":"UmaMaheswari C.","family":"Devi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J. H.","family":"Anderson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,11,16]]},"reference":[{"key":"9042_CR1","doi-asserted-by":"crossref","unstructured":"Abeni L, Buttazzo G (1998) Integrating multimedia applications in hard real-time systems. In: Proceedings of the 19th IEEE real-time systems symposium, December 1998, pp 4\u201313","DOI":"10.1109\/REAL.1998.739726"},{"key":"9042_CR2","doi-asserted-by":"crossref","unstructured":"Abeni L, Buttazzo G (1999) QoS guarantees using probabilistic deadlines. In: Proceedings of the 11th Euromicro conference of real-time systems, June 1999, pp 242\u2013249","DOI":"10.1109\/EMRTS.1999.777471"},{"issue":"1","key":"9042_CR3","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/j.jcss.2003.08.002","volume":"68","author":"J Anderson","year":"2004","unstructured":"Anderson J, Srinivasan A (2004) Mixed Pfair\/ERfair scheduling of asynchronous periodic tasks. J Comput Syst Sci 68(1):157\u2013204","journal-title":"J Comput Syst Sci"},{"key":"9042_CR4","doi-asserted-by":"crossref","unstructured":"Anderson J, Bud V, Devi U (2005) An EDF-based scheduling algorithm for multiprocessor soft real-time systems. In: Proceedings of the 17th Euromicro conference on real-time systems, July 2005, pp 199\u2013208","DOI":"10.1109\/ECRTS.2005.6"},{"key":"9042_CR5","doi-asserted-by":"crossref","unstructured":"Andersson B, Baruah S, Jonsson J (2001) Static priority scheduling on multiprocessors. In: Proceedings of the 22nd real-time systems symposium, December 2001, pp 193\u2013202","DOI":"10.1109\/REAL.2001.990610"},{"key":"9042_CR6","doi-asserted-by":"crossref","unstructured":"Atlas A, Bestavros A (1998) Statistical rate monotonic scheduling. In: Proceedings of the 19th IEEE real-time systems symposium, December 1998, pp 123\u2013132","DOI":"10.1109\/REAL.1998.739737"},{"issue":"2","key":"9042_CR7","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1109\/12.908988","volume":"50","author":"H Aydin","year":"2001","unstructured":"Aydin H, Melhem R, Mosse D, Alvarez PM (2001) Optimal reward-based scheduling for periodic real-time tasks. IEEE Trans Comput 50(2):111\u2013130","journal-title":"IEEE Trans Comput"},{"key":"9042_CR8","doi-asserted-by":"crossref","unstructured":"Baker TP (2003) Multiprocessor EDF and deadline monotonic schedulability analysis. In: Proceedings of the 24th IEEE real-time systems symposium, December 2003, pp 120\u2013129","DOI":"10.1109\/REAL.2003.1253260"},{"issue":"6","key":"9042_CR9","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1109\/TC.2004.16","volume":"53","author":"S Baruah","year":"2004","unstructured":"Baruah S (2004) Optimal utilization bounds for the fixed-priority scheduling of periodic task systems on identical multiprocessors. IEEE Trans Comput 53(6):781\u2013784","journal-title":"IEEE Trans Comput"},{"issue":"1\u20132","key":"9042_CR10","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/s11241-006-4961-9","volume":"32","author":"S Baruah","year":"2006","unstructured":"Baruah S (2006) The non-preemptive scheduling of periodic tasks upon multiprocessors. Real-Time Syst 32(1\u20132):9\u201320","journal-title":"Real-Time Syst"},{"issue":"6","key":"9042_CR11","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1007\/BF01940883","volume":"15","author":"S Baruah","year":"1996","unstructured":"Baruah S, Cohen N, Plaxton CG, Varvel D (1996) Proportionate progress: a notion of fairness in resource allocation. Algorithmica 15(6):600\u2013625","journal-title":"Algorithmica"},{"issue":"4","key":"9042_CR12","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1109\/12.919277","volume":"50","author":"G Bernat","year":"2001","unstructured":"Bernat G, Burns A, Liamosi A (2001) Weakly hard real-time systems. IEEE Trans Comput 50(4):308\u2013321","journal-title":"IEEE Trans Comput"},{"key":"9042_CR13","doi-asserted-by":"crossref","unstructured":"Bertogna M, Cirinei M, Lipari G (2005a) Improved schedulability analysis of EDF on multiprocessor platforms. In: Proceedings of the 17th Euromicro conference on real-time systems, July 2005, pp\u00a0209\u2013218","DOI":"10.1109\/ECRTS.2005.18"},{"key":"9042_CR14","doi-asserted-by":"crossref","unstructured":"Bertogna M, Cirinei M, Lipari G (2005b) New schedulability tests for real-time task sets scheduled by deadline monotonic on multiprocessors. In: Proceedings of the 9th international conference on principles of distributed systems, December 2005","DOI":"10.1007\/11795490_24"},{"key":"9042_CR15","doi-asserted-by":"crossref","unstructured":"Block A, Anderson J, Devi U (2006) Task reweighting under global scheduling on multiprocessors. In: Proceedings of the 18th Euromicro conference on real-time systems, July 2006, pp 128\u2013138","DOI":"10.1109\/ECRTS.2006.27"},{"issue":"4","key":"9042_CR16","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum M, Floyd R, Pratt V, Rivest R, Tarjan R (1973) Time bounds for selection. J Comput Syst Sci 7(4):448\u2013461","journal-title":"J Comput Syst Sci"},{"key":"9042_CR17","unstructured":"Devi U (2006) Soft real-time scheduling on multiprocessors. PhD thesis, University of North Carolina at Chapel Hill, December 2006"},{"key":"9042_CR18","doi-asserted-by":"crossref","unstructured":"Devi U, Anderson J (2004) Improved conditions for bounded tardiness under EPDF fair multiprocessor scheduling. In: Proceedings of the 12th international workshop on parallel and distributed real-time systems, April 2004 (on CD-ROM)","DOI":"10.1109\/IPDPS.2004.1303077"},{"key":"9042_CR19","doi-asserted-by":"crossref","unstructured":"Devi U, Anderson J (2005) Tardiness bounds under global EDF scheduling on a multiprocessor. In: Proceedings of the 26th IEEE real-time systems symposium, December 2005, pp 330\u2013341","DOI":"10.1109\/RTSS.2005.39"},{"key":"9042_CR20","doi-asserted-by":"crossref","unstructured":"Devi U, Anderson J (2006) Flexible tardiness bounds for sporadic real-time task systems on multiprocessors. In: Proceedings of the 20th IEEE international parallel and distributed processing symposium, April 2006 (on CD-ROM)","DOI":"10.1109\/IPDPS.2006.1639265"},{"key":"9042_CR21","doi-asserted-by":"crossref","unstructured":"Devi U, Leontyev H, Anderson J (2006) Efficient synchronization under global EDF scheduling on multiprocessors. In: Proceedings of the 18th Euromicro conference on real-time systems, July 2006, pp\u00a075\u201384","DOI":"10.1109\/ECRTS.2006.10"},{"issue":"1","key":"9042_CR22","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1287\/opre.26.1.127","volume":"26","author":"SK Dhall","year":"1978","unstructured":"Dhall SK, Liu CL (1978) On a real-time scheduling problem. Oper. Res. 26(1):127\u2013140","journal-title":"Oper. Res."},{"key":"9042_CR23","doi-asserted-by":"crossref","unstructured":"Diaz JL, Garcia DF, Kim K, Lee C-G, Bello L, Lopez JM, Min SL, Mirabella O (2002) Stochastic analysis of periodic real-time systems. In: Proceedings of the 23rd IEEE real-time systems symposium, December 2002, pp 289\u2013300","DOI":"10.1109\/REAL.2002.1181583"},{"issue":"2","key":"9042_CR24","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1214\/aoap\/1015345295","volume":"11","author":"B Doytchinov","year":"2001","unstructured":"Doytchinov B, Lehoczky J, Shreve S (2001) Real-time queues in heavy traffic with Earliest-Deadline-First queue discipline. Ann Appl Probab 11(2):332\u2013378","journal-title":"Ann Appl Probab"},{"issue":"3","key":"9042_CR25","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1145\/360680.360691","volume":"18","author":"R Floyd","year":"1975","unstructured":"Floyd R, Rivest R (1975) Expected time bounds for selection. Commun ACM 18(3):165\u2013172","journal-title":"Commun ACM"},{"issue":"2-3","key":"9042_CR26","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1023\/A:1025120124771","volume":"25","author":"J Goossens","year":"2003","unstructured":"Goossens J, Funk S, Baruah S (2003) Priority-driven scheduling of periodic task systems on multiprocessors. Real-Time Syst 25(2-3):187\u2013205","journal-title":"Real-Time Syst"},{"issue":"12","key":"9042_CR27","doi-asserted-by":"crossref","first-page":"1443","DOI":"10.1109\/12.477249","volume":"44","author":"M Hamdaoui","year":"1995","unstructured":"Hamdaoui M, Ramanathan P (1995) A dynamic priority assignment technique for streams with (m,k)-firm deadlines. IEEE Trans Comput 44(12):1443\u20131451","journal-title":"IEEE Trans Comput"},{"issue":"7","key":"9042_CR28","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"CAR Hoare","year":"1961","unstructured":"Hoare CAR (1961) Algorithm 63 (PARTITION) and algorithm 65 (FIND). Commun ACM 4(7):321\u2013322","journal-title":"Commun ACM"},{"key":"9042_CR29","first-page":"304","volume-title":"Proceedings of the real-time systems symposium, Phoenix AZ, December 1999","author":"K Jeffay","year":"1999","unstructured":"Jeffay K, Goddard S (1999) A theory of rate-based execution. In: Proceedings of the real-time systems symposium, Phoenix AZ, December 1999. IEEE Computer Society, Los Alamitos, pp 304\u2013314"},{"key":"9042_CR30","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1109\/REAL.1995.495201","volume-title":"Proceedings of the 16th IEEE real-time systems symposium","author":"G Koren","year":"1995","unstructured":"Koren G, Shasha D (1995) Skip-over: algorithms and complexity for overloaded systems that allow skips. In: Proceedings of the 16th IEEE real-time systems symposium, December 1995. IEEE, New York, pp 110\u2013117"},{"issue":"3","key":"9042_CR31","doi-asserted-by":"crossref","first-page":"1306","DOI":"10.1214\/105051604000000314","volume":"14","author":"L Kurk","year":"2004","unstructured":"Kurk L, Lehoczky J, Shreve S, Yeung S-N (2004) Earliest-deadline-first service in heavy-traffic acyclic networks. Ann Appl Probab 14(3):1306\u20131352","journal-title":"Ann Appl Probab"},{"key":"9042_CR32","first-page":"201","volume-title":"Proceedings of the 11st IEEE real-time systems symposium","author":"J Lehoczky","year":"1990","unstructured":"Lehoczky J (1990) Fixed priority scheduling of periodic task sets with arbitrary deadlines. In: Proceedings of the 11st IEEE real-time systems symposium, December 1990. IEEE, New York, pp 201\u2013209"},{"key":"9042_CR33","doi-asserted-by":"crossref","unstructured":"Lehoczky JP (1996) Real-time queuing theory. In: Proceedings of the 17th IEEE Real-time systems symposium, December 1996, pp 186\u2013195","DOI":"10.1109\/REAL.1996.563715"},{"issue":"1","key":"9042_CR34","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1145\/321738.321743","volume":"20","author":"CL Liu","year":"1973","unstructured":"Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J Assoc Comput Mach 20(1):46\u201361","journal-title":"J Assoc Comput Mach"},{"issue":"5","key":"9042_CR35","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1109\/2.76287","volume":"24","author":"JWS Liu","year":"1991","unstructured":"Liu JWS, Lin K-J, Shih W-K, Yu AC (1991) Algorithms for scheduling imprecise computations. IEEE Comput 24(5):58\u201368","journal-title":"IEEE Comput"},{"key":"9042_CR36","unstructured":"Mok A (1983) Fundamental design problems of distributed systems for hard real-time environments. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 1983"},{"issue":"3","key":"9042_CR37","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1109\/90.234856","volume":"1","author":"AK Parekh","year":"1993","unstructured":"Parekh AK, Gallager RG (1993) A generalized processor sharing approach to flow control in integrated services networks: the single node case. IEEE\/ACM Trans Netw 1(3):344\u2013357","journal-title":"IEEE\/ACM Trans Netw"},{"issue":"2\/3","key":"9042_CR38","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1023\/B:TIME.0000045315.61234.1e","volume":"28","author":"L Sha","year":"2004","unstructured":"Sha L, Abdelzaher T, Arzen K-E, Cervin A, Baker T, Burns A, Buttazzo G, Caccamo M, Lehoczky J, Mok AK (2004) Real time scheduling theory: a historical perspective. Real-Time Syst 28(2\/3):101\u2013155","journal-title":"Real-Time Syst"},{"key":"9042_CR39","doi-asserted-by":"crossref","unstructured":"Srinivasan A, Anderson J (2002) Optimal rate-based scheduling on multiprocessors. In: Proceedings of the 34th ACM symposium on theory of computing, May 2002, pp 189\u2013198","DOI":"10.1145\/509907.509938"},{"key":"9042_CR40","doi-asserted-by":"crossref","unstructured":"Srinivasan A, Anderson J (2003) Efficient scheduling of soft real-time applications on multiprocessors. In: Proceedings of the 15th Euromicro conference on real-time systems, July 2003, pp\u00a051\u201359","DOI":"10.1109\/EMRTS.2003.1212727"},{"issue":"1","key":"9042_CR41","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.jss.2003.12.041","volume":"77","author":"A Srinivasan","year":"2005","unstructured":"Srinivasan A, Anderson J (2005) Fair scheduling of dynamic task systems on multiprocessors. J Syst Softw 77(1):67\u201380","journal-title":"J Syst Softw"},{"issue":"6","key":"9042_CR42","doi-asserted-by":"crossref","first-page":"1049","DOI":"10.1016\/j.jcss.2006.03.001","volume":"72","author":"A Srinivasan","year":"2006","unstructured":"Srinivasan A, Anderson J (2006) Optimal rate-based scheduling on multiprocessors. J Comput Syst Sci 72(6):1049\u20131117","journal-title":"J Comput Syst Sci"},{"issue":"2","key":"9042_CR43","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/S0020-0190(02)00231-4","volume":"84","author":"A Srinivasan","year":"2002","unstructured":"Srinivasan A, Baruah S (2002) Deadline-based scheduling of periodic task systems on multiprocessors. Inf Process Lett 84(2):93\u201398","journal-title":"Inf Process Lett"},{"key":"9042_CR44","first-page":"288","volume-title":"Proceedings of the 17th IEEE real-time systems symposium, December 1996","author":"I Stoica","year":"1996","unstructured":"Stoica I, Abdel-Wahab H, Jeffay K, Baruah S, Gehrke J, Plaxton CG (1996) A proportional share resource allocation algorithm for real-time, time-shared systems. In: Proceedings of the 17th IEEE real-time systems symposium, December 1996. IEEE, New York, pp 288\u2013299"},{"key":"9042_CR45","doi-asserted-by":"crossref","unstructured":"Tia T-S, Deng D-Z, Shankar M, Storch M, Sun J, Wu L-C, Liu J-S (1995) Probabilistic performance guarantee for real-time tasks with varying computation times. In: Proceedings of the 2nd IEEE real-time and embedded technology and applications symposium, May 1995, pp 164\u2013173","DOI":"10.1109\/RTTAS.1995.516213"},{"key":"9042_CR46","doi-asserted-by":"crossref","unstructured":"Valente P, Lipari G (2005) An upper bound to the lateness of soft real-time tasks scheduled by EDF on multiprocessors. In: Proceedings of the 26th IEEE real-time systems symposium, December 2005, pp 311\u2013320","DOI":"10.1109\/RTSS.2005.8"},{"key":"9042_CR47","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1109\/REAL.2000.896013","volume-title":"Proceedings of the 21st IEEE real-time systems symposium, December 2000","author":"R West","year":"2000","unstructured":"West R, Poellabauer C (2000) Analysis of a window-constrained scheduler for real-time and best-effort packet streams. In: Proceedings of the 21st IEEE real-time systems symposium, December 2000. IEEE, New York, pp 239\u2013248"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-007-9042-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11241-007-9042-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-007-9042-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T11:09:51Z","timestamp":1559387391000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11241-007-9042-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11,16]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,2]]}},"alternative-id":["9042"],"URL":"https:\/\/doi.org\/10.1007\/s11241-007-9042-1","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"value":"0922-6443","type":"print"},{"value":"1573-1383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11,16]]}}}