Earlier Version

Automated analysis of real-time scheduling using graph games

K. Chatterjee, A. Kößler, U. Schmid, in:, Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control, ACM, 2013, pp. 163–172.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Author
; ;
Department
Abstract
In this paper, we introduce the powerful framework of graph games for the analysis of real-time scheduling with firm deadlines. We introduce a novel instance of a partial-observation game that is suitable for this purpose, and prove decidability of all the involved decision problems. We derive a graph game that allows the automated computation of the competitive ratio (along with an optimal witness algorithm for the competitive ratio) and establish an NP-completeness proof for the graph game problem. For a given on-line algorithm, we present polynomial time solution for computing (i) the worst-case utility; (ii) the worst-case utility ratio w.r.t. a clairvoyant off-line algorithm; and (iii) the competitive ratio. A major strength of the proposed approach lies in its flexibility w.r.t. incorporating additional constraints on the adversary and/or the algorithm, including limited maximum or average load, finiteness of periods of overload, etc., which are easily added by means of additional instances of standard objective functions for graph games.
Publishing Year
Date Published
2013-04-01
Proceedings Title
Proceedings of the 16th International conference on Hybrid systems: Computation and control
Page
163 - 172
Conference
HSCC: Hybrid Systems - Computation and Control
Conference Location
Philadelphia, PA, United States
Conference Date
2013-04-08 – 2013-04-11
IST-REx-ID

Cite this

Chatterjee K, Kößler A, Schmid U. Automated analysis of real-time scheduling using graph games. In: Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control. ACM; 2013:163-172. doi:10.1145/2461328.2461356
Chatterjee, K., Kößler, A., & Schmid, U. (2013). Automated analysis of real-time scheduling using graph games. In Proceedings of the 16th International conference on Hybrid systems: Computation and control (pp. 163–172). Philadelphia, PA, United States: ACM. https://doi.org/10.1145/2461328.2461356
Chatterjee, Krishnendu, Alexander Kößler, and Ulrich Schmid. “Automated Analysis of Real-Time Scheduling Using Graph Games.” In Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control, 163–72. ACM, 2013. https://doi.org/10.1145/2461328.2461356.
K. Chatterjee, A. Kößler, and U. Schmid, “Automated analysis of real-time scheduling using graph games,” in Proceedings of the 16th International conference on Hybrid systems: Computation and control, Philadelphia, PA, United States, 2013, pp. 163–172.
Chatterjee K, Kößler A, Schmid U. 2013. Automated analysis of real-time scheduling using graph games. Proceedings of the 16th International conference on Hybrid systems: Computation and control. HSCC: Hybrid Systems - Computation and Control 163–172.
Chatterjee, Krishnendu, et al. “Automated Analysis of Real-Time Scheduling Using Graph Games.” Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control, ACM, 2013, pp. 163–72, doi:10.1145/2461328.2461356.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search