The Power of Duality: Response Time Analysis meets Integer Programming Article Swipe
Max A. Deppert
,
Klaus Jansen
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2210.02361
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2210.02361
We study a mutually enriching connection between response time analysis in real-time systems and the mixing set problem. Thereby generalizing over known results we present a new approach to the computation of response times in fixed-priority uniprocessor real-time scheduling. We even allow that the tasks are delayed by some period-constrained release jitter. By studying a dual problem formulation of the decision problem as an integer linear program we show that worst-case response times can be computed by algorithmically exploiting a conditional reduction to an instance of the mixing set problem. In the important case of harmonic periods our new technique admits a near-quadratic algorithm to the exact computation of worst-case response times. We show that generally, a smaller utilization leads to more efficient algorithms even in fixed-priority scheduling. Worst-case response times can be understood as least fixed points to non-trivial fixed point equations and as such, our approach may also be used to solve suitable fixed point problems. Furthermore, we show that our technique can be reversed to solve the mixing set problem by computing worst-case response times to associated real-time scheduling task systems. Finally, we also apply our optimization technique to solve 4-block integer programs with simple objective functions.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2210.02361
- https://arxiv.org/pdf/2210.02361
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4303441389
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4303441389Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2210.02361Digital Object Identifier
- Title
-
The Power of Duality: Response Time Analysis meets Integer ProgrammingWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-10-05Full publication date if available
- Authors
-
Max A. Deppert, Klaus JansenList of authors in order
- Landing page
-
https://arxiv.org/abs/2210.02361Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2210.02361Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2210.02361Direct OA link when available
- Concepts
-
Computer science, Mathematical optimization, Integer programming, Scheduling (production processes), Computation, Uniprocessor system, Fixed point, Integer (computer science), Mathematics, Algorithm, Parallel computing, Multiprocessing, Programming language, Mathematical analysisTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4303441389 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2210.02361 |
| ids.doi | https://doi.org/10.48550/arxiv.2210.02361 |
| ids.openalex | https://openalex.org/W4303441389 |
| fwci | |
| type | preprint |
| title | The Power of Duality: Response Time Analysis meets Integer Programming |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10933 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9994999766349792 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1708 |
| topics[0].subfield.display_name | Hardware and Architecture |
| topics[0].display_name | Real-Time Systems Scheduling |
| topics[1].id | https://openalex.org/T10904 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9776999950408936 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1708 |
| topics[1].subfield.display_name | Hardware and Architecture |
| topics[1].display_name | Embedded Systems Design Techniques |
| topics[2].id | https://openalex.org/T10142 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9746000170707703 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1703 |
| topics[2].subfield.display_name | Computational Theory and Mathematics |
| topics[2].display_name | Formal Methods in Verification |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C41008148 |
| concepts[0].level | 0 |
| concepts[0].score | 0.5274370312690735 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[0].display_name | Computer science |
| concepts[1].id | https://openalex.org/C126255220 |
| concepts[1].level | 1 |
| concepts[1].score | 0.5271344184875488 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[1].display_name | Mathematical optimization |
| concepts[2].id | https://openalex.org/C56086750 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5180466175079346 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q6042592 |
| concepts[2].display_name | Integer programming |
| concepts[3].id | https://openalex.org/C206729178 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5050337910652161 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q2271896 |
| concepts[3].display_name | Scheduling (production processes) |
| concepts[4].id | https://openalex.org/C45374587 |
| concepts[4].level | 2 |
| concepts[4].score | 0.4616711139678955 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q12525525 |
| concepts[4].display_name | Computation |
| concepts[5].id | https://openalex.org/C79189994 |
| concepts[5].level | 3 |
| concepts[5].score | 0.4541867971420288 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q3488021 |
| concepts[5].display_name | Uniprocessor system |
| concepts[6].id | https://openalex.org/C61445026 |
| concepts[6].level | 2 |
| concepts[6].score | 0.44186633825302124 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q217608 |
| concepts[6].display_name | Fixed point |
| concepts[7].id | https://openalex.org/C97137487 |
| concepts[7].level | 2 |
| concepts[7].score | 0.4334319829940796 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q729138 |
| concepts[7].display_name | Integer (computer science) |
| concepts[8].id | https://openalex.org/C33923547 |
| concepts[8].level | 0 |
| concepts[8].score | 0.4075454771518707 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[8].display_name | Mathematics |
| concepts[9].id | https://openalex.org/C11413529 |
| concepts[9].level | 1 |
| concepts[9].score | 0.35854780673980713 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[9].display_name | Algorithm |
| concepts[10].id | https://openalex.org/C173608175 |
| concepts[10].level | 1 |
| concepts[10].score | 0.11055156588554382 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q232661 |
| concepts[10].display_name | Parallel computing |
| concepts[11].id | https://openalex.org/C4822641 |
| concepts[11].level | 2 |
| concepts[11].score | 0.0800173282623291 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q846651 |
| concepts[11].display_name | Multiprocessing |
| concepts[12].id | https://openalex.org/C199360897 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[12].display_name | Programming language |
| concepts[13].id | https://openalex.org/C134306372 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[13].display_name | Mathematical analysis |
| keywords[0].id | https://openalex.org/keywords/computer-science |
| keywords[0].score | 0.5274370312690735 |
| keywords[0].display_name | Computer science |
| keywords[1].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[1].score | 0.5271344184875488 |
| keywords[1].display_name | Mathematical optimization |
| keywords[2].id | https://openalex.org/keywords/integer-programming |
| keywords[2].score | 0.5180466175079346 |
| keywords[2].display_name | Integer programming |
| keywords[3].id | https://openalex.org/keywords/scheduling |
| keywords[3].score | 0.5050337910652161 |
| keywords[3].display_name | Scheduling (production processes) |
| keywords[4].id | https://openalex.org/keywords/computation |
| keywords[4].score | 0.4616711139678955 |
| keywords[4].display_name | Computation |
| keywords[5].id | https://openalex.org/keywords/uniprocessor-system |
| keywords[5].score | 0.4541867971420288 |
| keywords[5].display_name | Uniprocessor system |
| keywords[6].id | https://openalex.org/keywords/fixed-point |
| keywords[6].score | 0.44186633825302124 |
| keywords[6].display_name | Fixed point |
| keywords[7].id | https://openalex.org/keywords/integer |
| keywords[7].score | 0.4334319829940796 |
| keywords[7].display_name | Integer (computer science) |
| keywords[8].id | https://openalex.org/keywords/mathematics |
| keywords[8].score | 0.4075454771518707 |
| keywords[8].display_name | Mathematics |
| keywords[9].id | https://openalex.org/keywords/algorithm |
| keywords[9].score | 0.35854780673980713 |
| keywords[9].display_name | Algorithm |
| keywords[10].id | https://openalex.org/keywords/parallel-computing |
| keywords[10].score | 0.11055156588554382 |
| keywords[10].display_name | Parallel computing |
| keywords[11].id | https://openalex.org/keywords/multiprocessing |
| keywords[11].score | 0.0800173282623291 |
| keywords[11].display_name | Multiprocessing |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2210.02361 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | cc-by |
| locations[0].pdf_url | https://arxiv.org/pdf/2210.02361 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2210.02361 |
| locations[1].id | doi:10.48550/arxiv.2210.02361 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2210.02361 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5013382916 |
| authorships[0].author.orcid | https://orcid.org/0000-0003-3083-7998 |
| authorships[0].author.display_name | Max A. Deppert |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Deppert, Max A. |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5071305115 |
| authorships[1].author.orcid | https://orcid.org/0000-0001-8358-6796 |
| authorships[1].author.display_name | Klaus Jansen |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Jansen, Klaus |
| authorships[1].is_corresponding | False |
| has_content.pdf | True |
| has_content.grobid_xml | True |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2210.02361 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | The Power of Duality: Response Time Analysis meets Integer Programming |
| has_fulltext | True |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10933 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9994999766349792 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1708 |
| primary_topic.subfield.display_name | Hardware and Architecture |
| primary_topic.display_name | Real-Time Systems Scheduling |
| related_works | https://openalex.org/W3089428898, https://openalex.org/W2119024804, https://openalex.org/W2989726455, https://openalex.org/W2155549897, https://openalex.org/W2017977262, https://openalex.org/W2047683846, https://openalex.org/W2044902158, https://openalex.org/W2109912052, https://openalex.org/W1711527768, https://openalex.org/W2350876336 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2210.02361 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2210.02361 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2210.02361 |
| primary_location.id | pmh:oai:arXiv.org:2210.02361 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | cc-by |
| primary_location.pdf_url | https://arxiv.org/pdf/2210.02361 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2210.02361 |
| publication_date | 2022-10-05 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 2, 25, 54, 79, 101, 116 |
| abstract_inverted_index.By | 52 |
| abstract_inverted_index.In | 90 |
| abstract_inverted_index.We | 0, 39, 112 |
| abstract_inverted_index.an | 63, 83 |
| abstract_inverted_index.as | 62, 134, 144 |
| abstract_inverted_index.be | 74, 132, 150, 165 |
| abstract_inverted_index.by | 47, 76, 173 |
| abstract_inverted_index.in | 10, 34, 125 |
| abstract_inverted_index.of | 31, 58, 85, 94, 108 |
| abstract_inverted_index.to | 28, 82, 104, 120, 138, 152, 167, 178, 191 |
| abstract_inverted_index.we | 23, 67, 159, 185 |
| abstract_inverted_index.and | 13, 143 |
| abstract_inverted_index.are | 45 |
| abstract_inverted_index.can | 73, 131, 164 |
| abstract_inverted_index.may | 148 |
| abstract_inverted_index.new | 26, 98 |
| abstract_inverted_index.our | 97, 146, 162, 188 |
| abstract_inverted_index.set | 16, 88, 171 |
| abstract_inverted_index.the | 14, 29, 43, 59, 86, 91, 105, 169 |
| abstract_inverted_index.also | 149, 186 |
| abstract_inverted_index.case | 93 |
| abstract_inverted_index.dual | 55 |
| abstract_inverted_index.even | 40, 124 |
| abstract_inverted_index.more | 121 |
| abstract_inverted_index.over | 20 |
| abstract_inverted_index.show | 68, 113, 160 |
| abstract_inverted_index.some | 48 |
| abstract_inverted_index.task | 182 |
| abstract_inverted_index.that | 42, 69, 114, 161 |
| abstract_inverted_index.time | 8 |
| abstract_inverted_index.used | 151 |
| abstract_inverted_index.with | 196 |
| abstract_inverted_index.allow | 41 |
| abstract_inverted_index.apply | 187 |
| abstract_inverted_index.exact | 106 |
| abstract_inverted_index.fixed | 136, 140, 155 |
| abstract_inverted_index.known | 21 |
| abstract_inverted_index.leads | 119 |
| abstract_inverted_index.least | 135 |
| abstract_inverted_index.point | 141, 156 |
| abstract_inverted_index.solve | 153, 168, 192 |
| abstract_inverted_index.study | 1 |
| abstract_inverted_index.such, | 145 |
| abstract_inverted_index.tasks | 44 |
| abstract_inverted_index.times | 33, 72, 130, 177 |
| abstract_inverted_index.admits | 100 |
| abstract_inverted_index.linear | 65 |
| abstract_inverted_index.mixing | 15, 87, 170 |
| abstract_inverted_index.points | 137 |
| abstract_inverted_index.simple | 197 |
| abstract_inverted_index.times. | 111 |
| abstract_inverted_index.4-block | 193 |
| abstract_inverted_index.Thereby | 18 |
| abstract_inverted_index.between | 6 |
| abstract_inverted_index.delayed | 46 |
| abstract_inverted_index.integer | 64, 194 |
| abstract_inverted_index.jitter. | 51 |
| abstract_inverted_index.periods | 96 |
| abstract_inverted_index.present | 24 |
| abstract_inverted_index.problem | 56, 61, 172 |
| abstract_inverted_index.program | 66 |
| abstract_inverted_index.release | 50 |
| abstract_inverted_index.results | 22 |
| abstract_inverted_index.smaller | 117 |
| abstract_inverted_index.systems | 12 |
| abstract_inverted_index.Finally, | 184 |
| abstract_inverted_index.analysis | 9 |
| abstract_inverted_index.approach | 27, 147 |
| abstract_inverted_index.computed | 75 |
| abstract_inverted_index.decision | 60 |
| abstract_inverted_index.harmonic | 95 |
| abstract_inverted_index.instance | 84 |
| abstract_inverted_index.mutually | 3 |
| abstract_inverted_index.problem. | 17, 89 |
| abstract_inverted_index.programs | 195 |
| abstract_inverted_index.response | 7, 32, 71, 110, 129, 176 |
| abstract_inverted_index.reversed | 166 |
| abstract_inverted_index.studying | 53 |
| abstract_inverted_index.suitable | 154 |
| abstract_inverted_index.systems. | 183 |
| abstract_inverted_index.algorithm | 103 |
| abstract_inverted_index.computing | 174 |
| abstract_inverted_index.efficient | 122 |
| abstract_inverted_index.enriching | 4 |
| abstract_inverted_index.equations | 142 |
| abstract_inverted_index.important | 92 |
| abstract_inverted_index.objective | 198 |
| abstract_inverted_index.problems. | 157 |
| abstract_inverted_index.real-time | 11, 37, 180 |
| abstract_inverted_index.reduction | 81 |
| abstract_inverted_index.technique | 99, 163, 190 |
| abstract_inverted_index.Worst-case | 128 |
| abstract_inverted_index.algorithms | 123 |
| abstract_inverted_index.associated | 179 |
| abstract_inverted_index.connection | 5 |
| abstract_inverted_index.exploiting | 78 |
| abstract_inverted_index.functions. | 199 |
| abstract_inverted_index.generally, | 115 |
| abstract_inverted_index.scheduling | 181 |
| abstract_inverted_index.understood | 133 |
| abstract_inverted_index.worst-case | 70, 109, 175 |
| abstract_inverted_index.computation | 30, 107 |
| abstract_inverted_index.conditional | 80 |
| abstract_inverted_index.formulation | 57 |
| abstract_inverted_index.non-trivial | 139 |
| abstract_inverted_index.scheduling. | 38, 127 |
| abstract_inverted_index.utilization | 118 |
| abstract_inverted_index.Furthermore, | 158 |
| abstract_inverted_index.generalizing | 19 |
| abstract_inverted_index.optimization | 189 |
| abstract_inverted_index.uniprocessor | 36 |
| abstract_inverted_index.fixed-priority | 35, 126 |
| abstract_inverted_index.near-quadratic | 102 |
| abstract_inverted_index.algorithmically | 77 |
| abstract_inverted_index.period-constrained | 49 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/16 |
| sustainable_development_goals[0].score | 0.7900000214576721 |
| sustainable_development_goals[0].display_name | Peace, Justice and strong institutions |
| citation_normalized_percentile |