In this dissertation, we consider scheduling distributed soft real-time tasks in unreliable (e.g., those with arbitrary node and network failures) and untrustworthy systems (e.g., those with Byzantine node behaviors). We present a distributed real-time scheduling algorithm called Gamma. Gamma considers a distributed (i.e., multi-node) task model where tasks are subject to Time/Utility Function (or TUF) end-to-end time constraints, and the scheduling optimality criterion of maximizing the total accrued utility. The algorithm makes three novel contributions. First, Gamma uses gossip for reliably propagating task scheduling parameters and for discovering task execution nodes. Second, Gamma achieves distributed real-time mutual exclusion in unreliable environments. Third, the algorithm guards against potential disruption of message propagation due to Byzantine attacks using a mechanism called Launcher-Attacker-Infective-Susceptible-Immunized-Removed-Consumer (or LAISIRC). By doing so, the algorithm schedules tasks with probabilistic termination-time satisfactions, despite system unreliability and untrustworthiness. We analytically establish several timeliness and non-timeliness properties of the algorithm including probabilistic end-to-end task termination time satisfactions, optimality of message overheads, mutual exclusion guarantees, and the mathematical model of the LAISIRC mechanism. We conducted simulation-based experimental studies and compared Gamma with its competitors. Our experimental studies reveal that Gamma's scheduling algorithm accrues greater utility and satisfies a greater number of deadlines than do competitor algorithms (e.g., HVDF) by as much as 47% and 45%, respectively. LAISIRC is more tolerant to Byzantine attacks than competitor protocols (e.g., Path Verification) by obtaining as much as 28% higher correctness ratio. Gamma's mutual exclusion algorithm accrues greater utility than do competitor algorithms (e.g., EDF-Sigma) by as much as 25%. Further, we implemented the basic Gamma algorithm in the Emulab/ChronOS 250-node testbed, and measured the algorithm's performance. Our implementation measurements validate our theoretical analysis and the algorithm's effectiveness and robustness. / Ph. D.

Dynamic real-time distributed systems are characterized by significant run-time uncertainties at the mission and system levels. Typically, processing and communication latencies in such systems do not have known upper bounds and event and task arrivals and failure occurrences are non-deterministically distributed. This thesis proposes adaptive resource management heuristic techniques for periodic tasks in dynamic real-time distributed systems with the (soft real-time) objective of minimizing missed deadline ratios. The proposed resource management techniques continuously monitor the application tasks at run-time for adherence to the desired real-time requirements, detects timing failures or trends for impending failures (due to workload fluctuations), and dynamically allocate resources by replicating subtasks of application tasks for load sharing. We present "predictive" resource allocation algorithms that determine the number of subtask replicas that are required for adapting the application to a given workload situation using statistical regression theory. The algorithms use regression equations that forecast subtask timeliness as a function of external load parameters such as number of sensor reports and internal resource load parameters such as CPU utilization. The regression equations are determined off-line and on-line from application profiles that are collected off-line and on-line, respectively. To evaluate the performance of the predictive algorithms, we consider algorithms that determine the number of subtask replicas using empirically determined functions. The empirical functions compute the number of replicas as a function of the rate of change in the application workload during a "window" of past task periods. We implemented the resource management algorithms as part of a middleware infrastructure and measured the performance of the algorithms using a real-time benchmark. The experimental results indicate that the predictive, regression theory-based algorithms generally produce lower missed deadline ratios than the empirical strategies under the workload conditions that were studied. / Master of Science

This work is devoted to the issue of monitoring of distributed real-time systems. In particular, it focuses on formal aspects of model-based supervision and problems which are related to it. In its first part, we present the basic properties of two well-known formal models used to model distributed systems: networks of timed automata and time Petri nets. We show that the behavior of these models can be represented with so-called branching processes. We also introduce the key conceptual elements of the supervisory system. The second part of the work is dedicated to the issue of constrained unfoldings which enable us to track causal relationships between events in a distributed system. This type of structure can be used to reproduce processes of the system on the basis of a completely unordered set of previously observed events. Moreover, we show that time constraints imposed on a system and observations submitted to the supervisory system can significantly affect a course of events in the system. We also raise the issue of parameters in time constraints. The proposed methods are illustrated with case studies. The third part of the work deals with the issue of unobservable cyclical behaviors in distributed systems. This type of behaviors leads to an infinite number of events in constrained unfoldings. We explain how we can obtain a finite structure that stores information about all observed events in the system, even if this involves processes that are infinite due to such unobservable loops. The fourth and final part of the work is dedicated to implementation issues of the previously described methods.

Sistemas de tempo-real embarcados distribuídos se caracterizam pela complexidade e especificidade de seus projetos. Tanto a complexidade quanto a especificidade apresentam forte influência dos diversos requisitos ligados às restrições advindas das três características que distinguem tais sistemas, i.e. presença de fortes restrições temporais, restrições de sistemas embarcados e distribuição de processamento. Estes requisitos, chamados de requisitos não-funcionais, afetam diversas partes do sistema de maneira não uniforme, tornando-se por esta razão difícil o seu gerenciamento. Metodologias orientadas a objetos não apresentam mecanismos específicos para tratar tais requisitos, o que implica na aplicação de um significativo esforço ao se realizar o reuso ou a manutenção de componentes afetados por requisitos de natureza nãofuncional. Novas tecnologias têm surgido com o objetivo de contornar este problema, notadamente a orientação a aspectos. Este paradigma propõe a separação no tratamento dos requisitos não-funcionais contribuindo com a modularização do sistema. Esta dissertação propõe a aplicação de orientação a aspectos para a especificação de sistemas tempo-real embarcados distribuídos. Para isto realizou-se a adaptação de uma metodologia de desenvolvimento de sistemas orientada a aspectos, a FRIDA (From RequIrements to Design using Aspects), contextualizando-a para o domínio de interesse. A utilização desta metodologia provê suporte ao mapeamento de requisitos em elementos de projeto de modo a promover a rastreabilidade entre as fases de análise e projeto. Na fase de projeto é proposta a utilização de aspectos em conjunto com elementos do perfil RT-UML para o tratamento dos requisitos identificados e especificados na fase de análise. / Distributed real-time embedded systems generally have complex and very specific projects. Those characteristics are influenced by several requirements that have relation with constraints about the time, embedded and distribution restrictions. Those requirements, called non-functional requirements, can affect the whole system in a nonuniform way, what makes it difficult to handle with this kind of requirement. Objectoriented methodologies do not present specific mechanisms to handle those requirements, what imply in a significant effort to perform reuse and maintainability tasks in those components affected by non-functional requirements. New technologies are emerging to fulfill this gap, noteworthy the aspect orientation. This paradigm proposes the separation in handling functional and non-functional requirements, giving a contribution to the system modularity. This dissertation proposes the use of aspect orientation to specify distributed realtime embedded systems. To support this proposal, it was performed an adaptation of an aspect-oriented method called FRIDA (From RequIrements to Design using Aspects). The use of this method supports the mapping of requirements in design model elements, in order to promote traceability between analysis and design phases. The presented approach proposes the use of RT-UML together with aspect oriented elements in design phase aiming to improve the handling of those requirements specified in the analysis phase.

Sistemas de tempo-real embarcados distribuídos se caracterizam pela complexidade e especificidade de seus projetos. Tanto a complexidade quanto a especificidade apresentam forte influência dos diversos requisitos ligados às restrições advindas das três características que distinguem tais sistemas, i.e. presença de fortes restrições temporais, restrições de sistemas embarcados e distribuição de processamento. Estes requisitos, chamados de requisitos não-funcionais, afetam diversas partes do sistema de maneira não uniforme, tornando-se por esta razão difícil o seu gerenciamento. Metodologias orientadas a objetos não apresentam mecanismos específicos para tratar tais requisitos, o que implica na aplicação de um significativo esforço ao se realizar o reuso ou a manutenção de componentes afetados por requisitos de natureza nãofuncional. Novas tecnologias têm surgido com o objetivo de contornar este problema, notadamente a orientação a aspectos. Este paradigma propõe a separação no tratamento dos requisitos não-funcionais contribuindo com a modularização do sistema. Esta dissertação propõe a aplicação de orientação a aspectos para a especificação de sistemas tempo-real embarcados distribuídos. Para isto realizou-se a adaptação de uma metodologia de desenvolvimento de sistemas orientada a aspectos, a FRIDA (From RequIrements to Design using Aspects), contextualizando-a para o domínio de interesse. A utilização desta metodologia provê suporte ao mapeamento de requisitos em elementos de projeto de modo a promover a rastreabilidade entre as fases de análise e projeto. Na fase de projeto é proposta a utilização de aspectos em conjunto com elementos do perfil RT-UML para o tratamento dos requisitos identificados e especificados na fase de análise. / Distributed real-time embedded systems generally have complex and very specific projects. Those characteristics are influenced by several requirements that have relation with constraints about the time, embedded and distribution restrictions. Those requirements, called non-functional requirements, can affect the whole system in a nonuniform way, what makes it difficult to handle with this kind of requirement. Objectoriented methodologies do not present specific mechanisms to handle those requirements, what imply in a significant effort to perform reuse and maintainability tasks in those components affected by non-functional requirements. New technologies are emerging to fulfill this gap, noteworthy the aspect orientation. This paradigm proposes the separation in handling functional and non-functional requirements, giving a contribution to the system modularity. This dissertation proposes the use of aspect orientation to specify distributed realtime embedded systems. To support this proposal, it was performed an adaptation of an aspect-oriented method called FRIDA (From RequIrements to Design using Aspects). The use of this method supports the mapping of requirements in design model elements, in order to promote traceability between analysis and design phases. The presented approach proposes the use of RT-UML together with aspect oriented elements in design phase aiming to improve the handling of those requirements specified in the analysis phase.

Sistemas de tempo-real embarcados distribuídos se caracterizam pela complexidade e especificidade de seus projetos. Tanto a complexidade quanto a especificidade apresentam forte influência dos diversos requisitos ligados às restrições advindas das três características que distinguem tais sistemas, i.e. presença de fortes restrições temporais, restrições de sistemas embarcados e distribuição de processamento. Estes requisitos, chamados de requisitos não-funcionais, afetam diversas partes do sistema de maneira não uniforme, tornando-se por esta razão difícil o seu gerenciamento. Metodologias orientadas a objetos não apresentam mecanismos específicos para tratar tais requisitos, o que implica na aplicação de um significativo esforço ao se realizar o reuso ou a manutenção de componentes afetados por requisitos de natureza nãofuncional. Novas tecnologias têm surgido com o objetivo de contornar este problema, notadamente a orientação a aspectos. Este paradigma propõe a separação no tratamento dos requisitos não-funcionais contribuindo com a modularização do sistema. Esta dissertação propõe a aplicação de orientação a aspectos para a especificação de sistemas tempo-real embarcados distribuídos. Para isto realizou-se a adaptação de uma metodologia de desenvolvimento de sistemas orientada a aspectos, a FRIDA (From RequIrements to Design using Aspects), contextualizando-a para o domínio de interesse. A utilização desta metodologia provê suporte ao mapeamento de requisitos em elementos de projeto de modo a promover a rastreabilidade entre as fases de análise e projeto. Na fase de projeto é proposta a utilização de aspectos em conjunto com elementos do perfil RT-UML para o tratamento dos requisitos identificados e especificados na fase de análise. / Distributed real-time embedded systems generally have complex and very specific projects. Those characteristics are influenced by several requirements that have relation with constraints about the time, embedded and distribution restrictions. Those requirements, called non-functional requirements, can affect the whole system in a nonuniform way, what makes it difficult to handle with this kind of requirement. Objectoriented methodologies do not present specific mechanisms to handle those requirements, what imply in a significant effort to perform reuse and maintainability tasks in those components affected by non-functional requirements. New technologies are emerging to fulfill this gap, noteworthy the aspect orientation. This paradigm proposes the separation in handling functional and non-functional requirements, giving a contribution to the system modularity. This dissertation proposes the use of aspect orientation to specify distributed realtime embedded systems. To support this proposal, it was performed an adaptation of an aspect-oriented method called FRIDA (From RequIrements to Design using Aspects). The use of this method supports the mapping of requirements in design model elements, in order to promote traceability between analysis and design phases. The presented approach proposes the use of RT-UML together with aspect oriented elements in design phase aiming to improve the handling of those requirements specified in the analysis phase.

Dans cette thèse, nous analysons les réseaux des systèmes temps-réel distribués et plus particulièrement ceux des domaines de l’avionique et de l’automobile. Nous nous sommes focalisés sur deux protocoles : « Avionic Full DupleX Switched Ethernet » (AFDX), « Audio Vidéo Bridging Ethernet » (AVB). Dans ces domaines critiques, le déterminisme du réseau doit être garanti. Il consiste, notamment, en la détermination d’une borne garantie du délai de bout en bout de traversée du réseau pour chaque trame ; et un dimensionnement des files d’attente des trames suffisamment grand pour garantir qu’aucune d’entre elle ne débordera et ainsi, éviter toute perte de trame.Il existe plusieurs méthodes pour l’évaluation des délais et nous avons, principalement, travaillé sur la méthode « Forward end-to-end delay Analysis » (FA). FA avait déjà été définie avec la politique d’ordonnancement « First-In-First-Out » dans le contexte de l’AFDX. Nous sommes repartis de cette approche, nous l’avons reformulé et généralisé à n’importe quel réseau Ethernet commuté. Nous l’avons aussi étendu aux priorités statiques et au protocole AVB et sa politique de service « Credit Based Shaper ». Pour chaque contribution, des démonstrations formelles ont été présentées et une expérimentation incluant une comparaison de FA avec les principales approches d’évaluation sur un exemple industriel. Finalement, nous avons développé et démontré formellement une approche pour le dimensionnement des files d’attente en termes de nombre de trames. Cette approche a été expérimentée également sur une configuration industrielle. / In this thesis, we analyze networks in the context of distributed real-time systems, especially in the fields of avionics, with “Avionics Full DupleX Switched Ethernet” (AFDX), and automobile, with “Audio Video Bridging Ethernet” (AVB). For such applications, network determinism needs to be guaranteed. It involves, in particular, assessing a guaranteed bound on the end-to-end traversal time across the network fr each frame; and dimensioning the buffers in order to avoid any loss of frame because of a buffer overflow.There are several methods for worst-case delay analysis, and we have mainly worked on the “Forward end-to-end Delay Analysis” (FA) method. FA had already been developed for “First-In-First-Out” scheduling policy in the AFDX context, so we generalized it to any Switched Ethernet network. We have also extended it to handle static priorities and the AVB protocol, shaping policy named “Credit Based Shaper” (CBS). Each contribution has been formaly proved and experiments have been led on industrial configurations. For our experimentations, we have compared our results with the results of competing approaches. Finally, we have developed and formally demonstrated an approach for buffer dimensioning in terms of number of frames. This approach has also been tested on an industrial configuration and has produced tight bounds.

The Dynamic Distributed Dependable Real-Time Industrial communication Protocol (D3RIP) provides service guarantees for Real-Time traffic and integrates the dynamically changing requirements of automation applications in their operation to efficiently utilize the resources. The protocol dynamically allocates the network resources according to the respective system state. To this end, the protocol architecture consists of an Interface Layer that provides time-slotted operation and a Coordination Layer that assigns each time slot to a unique transmitter device based on a distributed computation. In this thesis, a software simulator for D3RIP is developed. Using the D3RIP Simulator, modifications in D3RIP can be easily examined without facing complexities in real implementations and extensive effort in terms of time and cost. The simulator simulates the Interface Layer, the Coordination Layer and additionally, the Shared Medium. Hence, using the simulator, the system-protocol couple can be easily analyzed, tested and further improvements on D3RIP can be achieved with the least amount of effort. The simulator implements the Timed Input Output Automata (TIOA) models of the D3RIP stack components using C++. The resulting code is compiled on GCC (Gnu Compiler Collection). The logs of the simulation runs and the real system with 2 devices connected via cross 100MbE cables are compared. In a 3ms time slot, the simulator and the system incidents differ about 135&micro / s on the average, causing no asynchronousity in their instantaneous operational states. The D3RIP Simulator is useful in keeping track of any variable in the D3RIP system automaton at any instant up to 1&micro / s resolution.

This thesis is concerned with the modeling and the analysis of distributedreal-time systems. In distributed systems, components evolve partlyindependently: concurrent actions may be performed in any order, withoutinfluencing each other and the state reached after these actions does notdepends on the order of execution. The time constraints in distributed real-timesystems create complex dependencies between the components and the events thatoccur. So far, distributed real-time systems have not been deeply studied, andin particular the distributed aspect of these systems is often left aside. Thisthesis explores distributed real-time systems. Our work on distributed real-timesystems is based on two formalisms: time Petri nets and networks of timedautomata, and is divided into two parts.In the first part, we highlight the differences between centralized anddistributed timed systems. We compare the main formalisms and their extensions,with a novel approach that focuses on the preservation of concurrency. Inparticular, we show how to translate a time Petri net into a network of timedautomata with the same distributed behavior. We then study a concurrency relatedproblem: shared clocks in networks of timed automata can be problematic when oneconsiders the implementation of a model on a multi-core architecture. We showhow to avoid shared clocks while preserving the distributed behavior, when thisis possible.In the second part, we focus on formalizing the dependencies between events inpartial order representations of the executions of Petri nets and time Petrinets. Occurrence nets is one of these partial order representations, and theirstructure directly provides the causality, conflict and concurrency relationsbetween events. However, we show that, even in the untimed case, some logicaldependencies between event occurrences are not directly described by thesestructural relations. After having formalized these logical dependencies, wesolve the following synthesis problem: from a formula that describes a set ofruns, we build an associated occurrence net. Then we study the logicalrelations in a simplified timed setting and show that time creates complexdependencies between event occurrences. These dependencies can be used to definea canonical unfolding, for this particular timed setting.

No description available.