Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.ic.2009.09.005
DC FieldValue
dc.titleQuasi-static scheduling of communicating tasks
dc.contributor.authorDarondeau, P.
dc.contributor.authorGenest, B.
dc.contributor.authorThiagarajan, P.S.
dc.contributor.authorYang, S.
dc.date.accessioned2013-07-04T08:45:04Z
dc.date.available2013-07-04T08:45:04Z
dc.date.issued2010
dc.identifier.citationDarondeau, P., Genest, B., Thiagarajan, P.S., Yang, S. (2010). Quasi-static scheduling of communicating tasks. Information and Computation 208 (10) : 1154-1168. ScholarBank@NUS Repository. https://doi.org/10.1016/j.ic.2009.09.005
dc.identifier.issn08905401
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/42168
dc.description.abstractGood scheduling policies for distributed embedded applications are required for meeting hard real time constraints and for optimizing the use of computational resources. We study the quasi-static scheduling problem in which (uncontrollable) control flow branchings can influence scheduling decisions at run time. Our abstracted distributed task model consists of a network of sequential processes that communicate via point-to-point buffers. In each round, the task gets activated by a request from the environment. When the task has finished computing the required responses, it reaches a pre-determined configuration and is ready to receive a new request from the environment. For such systems, we prove that determining the existence of a scheduling policy that guarantees upper bounds on buffer capacities is undecidable. However, we show that the problem is decidable for the important subclass of "data-branching" systems in which control flow branchings are exclusively due to data-dependent internal choices made by the sequential components. This decidability result exploits ideas derived from the Karp and Miller coverability tree for Petri nets as well as the existential boundedness notion of languages of message sequence charts. © 2010 Elsevier Inc. All rights reserved.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1016/j.ic.2009.09.005
dc.sourceScopus
dc.subjectChannel bound
dc.subjectCommunicating machines
dc.subjectQuasi-static scheduling
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.doi10.1016/j.ic.2009.09.005
dc.description.sourcetitleInformation and Computation
dc.description.volume208
dc.description.issue10
dc.description.page1154-1168
dc.description.codenINFCE
dc.identifier.isiut000281830300004
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

2
checked on Nov 13, 2019

WEB OF SCIENCETM
Citations

1
checked on Nov 5, 2019

Page view(s)

62
checked on Oct 28, 2019

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.