---
_id: '2820'
abstract:
- lang: eng
text: '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. '
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Alexander
full_name: Kößler, Alexander
last_name: Kößler
- first_name: Ulrich
full_name: Schmid, Ulrich
last_name: Schmid
citation:
ama: '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'
apa: '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'
chicago: '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.'
ieee: '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.'
ista: '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.'
mla: '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.'
short: '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.'
conference:
end_date: 2013-04-11
location: Philadelphia, PA, United States
name: 'HSCC: Hybrid Systems - Computation and Control'
start_date: 2013-04-08
date_created: 2018-12-11T11:59:46Z
date_published: 2013-04-01T00:00:00Z
date_updated: 2023-09-27T12:52:38Z
day: '01'
department:
- _id: KrCh
doi: 10.1145/2461328.2461356
ec_funded: 1
language:
- iso: eng
month: '04'
oa_version: None
page: 163 - 172
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: 'Proceedings of the 16th International conference on Hybrid systems:
Computation and control'
publication_identifier:
isbn:
- '978-1-4503-1567-8 '
publication_status: published
publisher: ACM
publist_id: '3981'
quality_controlled: '1'
related_material:
record:
- id: '738'
relation: later_version
status: public
scopus_import: 1
status: public
title: Automated analysis of real-time scheduling using graph games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...