Safe schedulability of bounded-rate multi-mode systems

D 2013

Safe schedulability of bounded-rate multi-mode systems

ALUR, Rajeev, Vojtěch FOREJT, Salar MOARREF and Ashutosh TRIVEDI

Basic information

Original name

Safe schedulability of bounded-rate multi-mode systems

Authors

ALUR, Rajeev (840 United States of America), Vojtěch FOREJT (203 Czech Republic, guarantor, belonging to the institution), Salar MOARREF (364 Islamic Republic of Iran) and Ashutosh TRIVEDI (356 India)

Edition

New York, NY, USA, Proceedings of the 16th international conference on Hybrid systems: computation and control, HSCC 2013, p. 243-252, 10 pp. 2013

Publisher

ACM

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

RIV identification code

RIV/00216224:14330/13:00072857

Organization unit

Faculty of Informatics

ISBN

978-1-4503-1567-8

DOI

http://dx.doi.org/10.1145/2461328.2461366

Keywords in English

hybrid systems; scheduling

Abstract

V originále

Bounded-rate multi-mode systems (BMS) are hybrid systems that can switch freely among a finite set of modes, and whose dynamics is specified by a finite number of real-valued variables with mode-dependent rates that can vary within given bounded sets. The schedulability problem for BMS is defined as an infinite-round game between two players— the scheduler and the environment—where in each round the scheduler proposes a time and a mode while the environment chooses an allowable rate for that mode, and the state of the system changes linearly in the direction of the rate vector. The goal of the scheduler is to keep the state of the system within a pre-specified safe set using a non-Zeno schedule, while the goal of the environment is the opposite. Green scheduling under uncertainty is a paradigmatic example of BMS where a winning strategy of the scheduler corresponds to a robust energy-optimal policy. We present an algorithm to decide whether the scheduler has a winning strategy from an arbitrary starting state, and give an algorithm to compute such a winning strategy, if it exists. We show that the schedulability problem for BMS is co-NP complete in general, but for two variables it is in PTIME. We also study the discrete schedulability problem where the environment has only finitely many choices of rate vectors in each mode and the scheduler can make decisions only at multiples of a given clock period, and show it to be EXPTIME-complete.

Links

LG13010, research and development project

Name: Zastoupení ČR v European Research Consortium for Informatics and Mathematics (Acronym: ERCIM-CZ)

Investor: Ministry of Education, Youth and Sports of the CR

MUNI/33/IP1/2013, interní kód MU

Name: Podpora perspektivních výzkumných týmů Fakulty informatiky a vynikajících vědeckých pracovníků z jiných institucí působících na Fakultě informatiky (Acronym: PVT-VVPZ)

Investor: Masaryk University

Citovat

ALUR, Rajeev, Vojtěch FOREJT, Salar MOARREF and Ashutosh TRIVEDI. Safe schedulability of bounded-rate multi-mode systems. In Calin Belta and Franjo Ivancic. Proceedings of the 16th international conference on Hybrid systems: computation and control, HSCC 2013. New York, NY, USA: ACM, 2013, p. 243-252. ISBN 978-1-4503-1567-8. Available from: https://dx.doi.org/10.1145/2461328.2461366.

@inproceedings{1174047,
   author = {Alur, Rajeev and Forejt, Vojtěch and Moarref, Salar and Trivedi, Ashutosh},
   address = {New York, NY, USA},
   booktitle = {Proceedings of the 16th international conference on Hybrid systems: computation and control, HSCC 2013},
   doi = {http://dx.doi.org/10.1145/2461328.2461366},
   editor = {Calin Belta and Franjo Ivancic},
   keywords = {hybrid systems; scheduling},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {New York, NY, USA},
   isbn = {978-1-4503-1567-8},
   pages = {243-252},
   publisher = {ACM},
   title = {Safe schedulability of bounded-rate multi-mode systems},
   year = {2013}
}

TY  - JOUR
ID  - 1174047
AU  - Alur, Rajeev - Forejt, Vojtěch - Moarref, Salar - Trivedi, Ashutosh
PY  - 2013
TI  - Safe schedulability of bounded-rate multi-mode systems
PB  - ACM
CY  - New York, NY, USA
SN  - 9781450315678
KW  - hybrid systems
KW  - scheduling
N2  - Bounded-rate multi-mode systems (BMS) are hybrid systems that can switch freely among a finite set of modes, and whose dynamics is specified by a finite number of real-valued variables with mode-dependent rates that can vary within given bounded sets. The schedulability problem for BMS is defined as an infinite-round game between two players— the scheduler and the environment—where in each round the scheduler proposes a time and a mode while the environment chooses an allowable rate for that mode, and the state of the system changes linearly in the direction of the rate vector. The goal of the scheduler is to keep the state of the system within a pre-specified safe set using a non-Zeno schedule, while the goal of the environment is the opposite. Green scheduling under uncertainty is a paradigmatic example of BMS where a winning strategy of the scheduler corresponds to a robust energy-optimal policy. We present an algorithm to decide whether the scheduler has a winning strategy from an arbitrary starting state, and give an algorithm to compute such a winning strategy, if it exists. We show that the schedulability problem for BMS is co-NP complete in general, but for two variables it is in PTIME. We also study the discrete schedulability problem where the environment has only finitely many choices of rate vectors in each mode and the scheduler can make decisions only at multiples of a given clock period, and show it to be EXPTIME-complete.
ER  -

ALUR, Rajeev, Vojtěch FOREJT, Salar MOARREF and Ashutosh TRIVEDI. Safe schedulability of bounded-rate multi-mode systems. In Calin Belta and Franjo Ivancic. \textit{Proceedings of the 16th international conference on Hybrid systems: computation and control, HSCC 2013}. New York, NY, USA: ACM, 2013, p.~243-252. ISBN~978-1-4503-1567-8. Available from: https://dx.doi.org/10.1145/2461328.2461366.

Detailed Information on Publication Record