{"id":193,"date":"2015-05-20T09:19:36","date_gmt":"2015-05-20T08:19:36","guid":{"rendered":"http:\/\/babel.isa.uma.es\/kipr\/?p=193"},"modified":"2015-07-16T15:29:42","modified_gmt":"2015-07-16T14:29:42","slug":"soft-real-time-scheduling-in-distributed-systems-based-on-accrued-utility-of-distributable-threads-including-situations-of-node-failures","status":"publish","type":"post","link":"https:\/\/babel.isa.uma.es\/kipr\/?p=193","title":{"rendered":"Soft-real time scheduling in distributed systems based on accrued utility of distributable threads, including situations of node failures"},"content":{"rendered":"

Ravindran B., Anderson J. S., Jensen E. D., On Distributed Real-Time Scheduling in Networked Embedded Systems in the Presence of Crash Failures<\/strong>, Lecture Notes in Computer Science, vol. 4761, pp. 67-81, DOI: 10.1007\/978-3-540-75664-4_8<\/a>.<\/h4>\n

We consider the problem of scheduling distributable real-time threads in networkedembedded systems that operate under run-time uncertainties including those on thread execution times, thread arrivals, and node failure occurrences. We present a distributed scheduling algorithm called CUA. We show that CUA satisfies thread time constraints in the presence of crash failures, is early-deciding, has an efficient message complexity of O(f n) (where f is the number of crashes that actually occur and n is the number of nodes), and is time-optimal with a time lower bound of O(D + f d + nk) (where D is the message delay upper bound, d is the failure detection bound, and k is the maximum number of threads). In crash-free runs, the algorithm constructs schedules within O(D + nk), and yields optimal total utility if nodes are also not overloaded. The algorithm is also \u201cbest-effort\u201d in that a high importance thread that may arrive at any time has a very high likelihood for feasible completion (in contrast to classical admission control algorithms which favor feasible completion of admitted threads over admitting new ones, irrespective of thread importance).<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"

Ravindran B., Anderson J. S., Jensen E. D., On Distributed Real-Time Scheduling in Networked Embedded Systems in the Presence of …<\/span> Read More →<\/span><\/a><\/span><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[56],"tags":[87,364,6],"class_list":["post-193","post","type-post","status-publish","format-standard","hentry","category-real-time-systems","tag-soft-real-time","tag-task-scheduling","tag-useful-for-teaching"],"_links":{"self":[{"href":"https:\/\/babel.isa.uma.es\/kipr\/index.php?rest_route=\/wp\/v2\/posts\/193"}],"collection":[{"href":"https:\/\/babel.isa.uma.es\/kipr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/babel.isa.uma.es\/kipr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/babel.isa.uma.es\/kipr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/babel.isa.uma.es\/kipr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=193"}],"version-history":[{"count":2,"href":"https:\/\/babel.isa.uma.es\/kipr\/index.php?rest_route=\/wp\/v2\/posts\/193\/revisions"}],"predecessor-version":[{"id":195,"href":"https:\/\/babel.isa.uma.es\/kipr\/index.php?rest_route=\/wp\/v2\/posts\/193\/revisions\/195"}],"wp:attachment":[{"href":"https:\/\/babel.isa.uma.es\/kipr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=193"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/babel.isa.uma.es\/kipr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=193"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/babel.isa.uma.es\/kipr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=193"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}