---
_id: '4415'
abstract:
- lang: eng
text: 'Many computing applications, especially those in safety critical embedded
systems, require highly predictable timing properties. However, time is often
not present in the prevailing computing and networking abstractions. In fact,
most advances in computer architecture, software, and networking favor average-case
performance over timing predictability. This thesis studies several methods for
the design of concurrent and/or distributed embedded systems with precise timing
guarantees. The focus is on flexible and compositional methods for programming
and verification of the timing properties. The presented methods together with
related formalisms cover two levels of design: (1) Programming language/model
level. We propose the distributed variant of Giotto, a coordination programming
language with an explicit temporal semantics—the logical execution time (LET)
semantics. The LET of a task is an interval of time that specifies the time instants
at which task inputs and outputs become available (task release and termination
instants). The LET of a task is always non-zero. This allows us to communicate
values across the network without changing the timing information of the task,
and without introducing nondeterminism. We show how this methodology supports
distributed code generation for distributed real-time systems. The method gives
up some performance in favor of composability and predictability. We characterize
the tradeoff by comparing the LET semantics with the semantics used in Simulink.
(2) Abstract task graph level. We study interface-based design and verification
of applications represented with task graphs. We consider task sequence graphs
with general event models, and cyclic graphs with periodic event models with jitter
and phase. Here an interface of a component exposes time and resource constraints
of the component. Together with interfaces we formally define interface composition
operations and the refinement relation. For efficient and flexible composability
checking two properties are important: incremental design and independent refinement.
According to the incremental design property the composition of interfaces can
be performed in any order, even if interfaces for some components are not known.
The refinement relation is defined such that in a design we can always substitute
a refined interface for an abstract one. We show that the framework supports independent
refinement, i.e., the refinement relation is preserved under composition operations.'
acknowledgement: 978-0-549-83480-9
article_processing_charge: No
author:
- first_name: Slobodan
full_name: Matic, Slobodan
last_name: Matic
citation:
ama: Matic S. Compositionality in deterministic real-time embedded systems. 2008:1-148.
apa: Matic, S. (2008). Compositionality in deterministic real-time embedded systems.
University of California, Berkeley.
chicago: Matic, Slobodan. “Compositionality in Deterministic Real-Time Embedded
Systems.” University of California, Berkeley, 2008.
ieee: S. Matic, “Compositionality in deterministic real-time embedded systems,”
University of California, Berkeley, 2008.
ista: Matic S. 2008. Compositionality in deterministic real-time embedded systems.
University of California, Berkeley.
mla: Matic, Slobodan. Compositionality in Deterministic Real-Time Embedded Systems.
University of California, Berkeley, 2008, pp. 1–148.
short: S. Matic, Compositionality in Deterministic Real-Time Embedded Systems, University
of California, Berkeley, 2008.
date_created: 2018-12-11T12:08:44Z
date_published: 2008-01-01T00:00:00Z
date_updated: 2022-02-14T14:08:50Z
day: '01'
degree_awarded: PhD
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 1 - 148
publication_status: published
publisher: University of California, Berkeley
publist_id: '316'
status: public
supervisor:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Edward
full_name: Lee, Edward
last_name: Lee
- first_name: Raja
full_name: Sengupta, Raja
last_name: Sengupta
title: Compositionality in deterministic real-time embedded systems
type: dissertation
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2008'
...