Redundância provê tolerância a falhas. Um serviço pode ser executado em múltiplos servidores que se replicam uns aos outros, de maneira a prover disponibilidade do serviço em caso de falhas. Uma maneira de implementar um tal serviço replicado é através de técnicas como replicação de máquina de estados (SMR). SMR provê tolerância a falhas, ao mesmo tempo que é linearizável, isto é, clientes não são capazes de distinguir o comportamento do sistema replicado daquele de um sistema não replicado. No entanto, ter um sistema completamente replicado e linearizável vem com um custo, que é escalabilidade – por escalabilidade, queremos dizer que adicionar servidores ao sistema aumenta a sua vazão, pelo menos para algumas cargas de trabalho. Mesmo com uma configuração cuidadosa e usando otimizações que evitam que os servidores executem ações redundantes desnecessárias, em um determinado ponto a vazão de um sistema replicado com SMR não pode ser mais aumentada acrescentando-se servidores; na verdade, adicionar réplicas pode até degradar a sua performance. Uma maneira de conseguir escalabilidade é particionar o serviço e então permitir que partições trabalhem independentemente. Por outro lado, ter um sistema particionado, porém linearizável e com razoavelmente boa performance não é trivial, e esse é o tópico de pesquisa tratado aqui. Para permitir que sistemas escalem, ao mesmo tempo que se garante linearizabilidade, nós propomos as seguinte ideias: (i) Replicação Escalável de Máquina de Estados (SSMR), (ii) Multicast Atômico Otimista (Opt-amcast) e (iii) S-SMR Rápido (Fast-SSMR). S-SMR é um modelo de execução que permite que a vazão do sistema escale de maneira linear com o número de servidores, sem sacrificar consistência. Para reduzir o tempo de resposta dos comandos, nós definimos o conceito de Opt-amcast, que permite que mensagens sejam entregues duas vezes: uma entrega garante ordem atômica (entrega atômica), enquanto a outra é mais rápida, mas nem sempre garante ordem atômica (entrega otimista). A implementação de Opt-amcast que nós propomos nessa tese se chama Ridge, um protocolo que combina baixa latência com alta vazão. Fast-SSMR é uma extensão do S-SMR que utiliza a entrega otimista do Opt-amcast: enquanto um comando é ordenado de maneira atômica, pode-se fazer alguma pré-computação baseado na entrega otimista, reduzindo assim tempo de resposta. / Redundancy provides fault-tolerance. A service can run on multiple servers that replicate each other, in order to provide service availability even in the case of crashes. A way to implement such a replicated service is by using techniques like state machine replication (SMR). SMR provides fault tolerance, while being linearizable, that is, clients cannot distinguish the behaviour of the replicated system to that of a single-site, unreplicated one. However, having a fully replicated, linearizable system comes at a cost, namely, scalability—by scalability we mean that adding servers will always increase the maximum system throughput, at least for some workloads. Even with a careful setup and using optimizations that avoid unnecessary redundant actions to be taken by servers, at some point the throughput of a system replicated with SMR cannot be increased by additional servers; in fact, adding replicas may even degrade performance. A way to achieve scalability is by partitioning the service state and then allowing partitions to work independently. Having a partitioned, yet linearizable and reasonably performant service is not trivial, and this is the topic of research addressed here. To allow systems to scale, while at the same time ensuring linearizability, we propose and implement the following ideas: (i) Scalable State Machine Replication (S-SMR), (ii) Optimistic Atomic Multicast (Opt-amcast), and (iii) Fast S-SMR (Fast-SSMR). S-SMR is an execution model that allows the throughput of the system to scale linearly with the number of servers without sacrificing consistency. To provide faster responses for commands, we developed Opt-amcast, which allows messages to be delivered twice: one delivery guarantees atomic order (conservative delivery), while the other is fast, but not always guarantees atomic order (optimistic delivery). The implementation of Opt-amcast that we propose is called Ridge, a protocol that combines low latency with high throughput. Fast-SSMR is an extension of S-SMR that uses the optimistic delivery of Opt-amcast: while a command is atomically ordered, some precomputation can be done based on its fast, optimistically ordered delivery, improving response time.

Máquinas de Estados Finitos, além de suas inúmeras aplicações, são amplamente utilizadas na Engenharia de Software para modelar especificações de sistemas. Nesses modelos, projetistas podem inserir, inadvertidamente, estados redundantes, ou seja, que exibem o mesmo comportamento. A eliminação desses estados traz diversos benefícios para as atividades que utilizam o modelo, como menor complexidade e menos recursos físicos para implementação. O processo de eliminação desses estados é denominado minimização, e pode ser realizado em tempo polinomial para máquinas completamente especificadas. Por outro lado, a minimização de máquinas parciais, cuja especificação não cobre todo o domínio de entrada, somente pode ser obtida em tempo polinomial com o uso de abordagens não determinísticas, ou seja, trata-se de um problema NP-Completo. Este trabalho apresenta uma estratégia para a minimização de máquinas de estados finitos parciais que faz o uso de heurísticas e otimizações para tornar o processo mais eficiente. Visando mensurar tal ganho de eficiência, foram realizados experimentos, nos quais os tempos de execução de uma implementação do método proposto foram medidos, juntamente com os tempos de implementações de dois outros métodos conhecidos. Os resultados mostraram vantagens significativas de performance para o novo método em relação aos métodos anteriores / Finite State Machines are largely used on Software Engineering to model systems specifications. In these models, designers may inadvertently include redundant states, i.e., states which exhibit the same input/output behavior. The absence of such states brings benefits to the modeling activities, reducing the complexity and taking less physical resources on implementations. The process of eliminating redundant states is known as minimization, and can be accomplished in polynomial time for completely specified machines. On the other hand, the minimization of partially specified machines, i.e., machines which have undefined behavior for some inputs, can only be done in polynomial time when non-deterministic approaches are applied. It is a known NP-Complete problem. This work presents a deterministic approach to minimize incompletely specified Finite State Machines, using heuristics and optimizations to accomplish the task more efficiently. In order to measure the performance improvements, experiments were done, observing the running time of an implementation of the proposed method, along with running times of implementations of two other known methods. The results revealed a significant performance advantage when using the proposed approach

Submitted by Rafael Santana (rafael.silvasantana@ufpe.br) on 2017-08-31T18:01:45Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Tese-tmp - Entrega Biblioteca.pdf: 5443368 bytes, checksum: 91e38ed8db35fc81cfcacf861c54bc96 (MD5) / Made available in DSpace on 2017-08-31T18:01:45Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Tese-tmp - Entrega Biblioteca.pdf: 5443368 bytes, checksum: 91e38ed8db35fc81cfcacf861c54bc96 (MD5) Previous issue date: 2016-10-07 / As linguagens declarativas normalmente atuam no desenvolvimento de aplicações multimídia, pois suas características permitem suportar adequadamente a natureza assíncrona e descritiva dessas aplicações. Neste cenário, a robustez surge como um fator determinante para a qualidade dessas aplicações, dada a vasta quantidade de plataformas e dispositivos usuais, que, ocasionalmente, apresentam problemas de execução. Neste contexto, as especificações dessas linguagens são de grande importância para o processo de desenvolvimento, pois além de direcionar a codificação, definindo as restrições léxicas, sintáticas e semânticas, também formalizam como os conteúdos devem ser executados pelos interpretadores. Este trabalho tem por objetivo investigar a viabilidade de se aplicar análises estruturais e comportamentais orientadas a conformidade para o desenvolvimento de aplicações multimídia, a fim de eliminar a dependência de interpretadores para atestar sua corretude. Para tal, a linguagem NCL foi utilizada como alvo do estudo, devido à sua representatividade para o problema. / Declarative languages are typically used in the development of multimedia applications, as its features allow to properly support the asynchronous and descriptive nature of these applications. In such a scenario, robustness appears as a determining factor in the quality of these applications, given the vast amount of platforms and devices that occasionally have implementation problems. In this context, specifications of these languages are of great importance to the development process, as they impose lexical, syntactic and semantic restrictions, and also formalize how content must be interpreted. This work aims at investigating the feasibility of applying structural and behavioral analysis oriented to compliance to the development of multimedia applications in order to eliminate dependence on interpreters to prove its correctness. To this end, NCL was used as a target of study due to its problem representativeness.

O teste baseado em modelos tem como objetivo auxiliar a atividade de testes, gerando conjuntos de casos de teste a partir de modelos, como Máquinas de Estados Finitos (MEFs). Diversos métodos de geração de conjuntos de caso de teste têm sido propostos ao longo das últimas décadas, com algumas contribuições recentes. Dentre esses trabalhos, há os que geram seqüências de verificação que são conjuntos de caso de teste formados por uma única seqüência e que são capazes de detectar os defeitos de uma implementação cujo comportamento pode ser modelado a partir de uma MEF. Neste trabalho é proposto um algoritmo de geração de seqüências de verificação que tem a finalidade de gerar seqüências menores que as seqüências geradas pelos métodos existentes. O algoritmo, que é baseado na técnica de algoritmos genéticos e nas condições de suficiência para a completude de casos de teste, consiste basicamente em criar novas seqüências a partir de seqüências menores. Por meio de mutações, novas seqüências são geradas pelo algoritmo. As condições de suficiência são utilizadas para determinar quais seqüências geradas são seqüências de verificação. Também são apresentados neste trabalho os estudos experimentais realizados para determinar o comportamento do algoritmo diante de diferentes contextos / Model-based testing aims at aiding the testing activity, generating test cases from models such as Finite State Machines (FSM). Several test cases generation methods have been proposed along the last decades, with some recent contributions. Among these works, there are those that generate checking sequences, which are test cases formed by a single sequence and which are capable of detecting faults in an implementation whose behavior can be modeled as an FSM. This work proposes a checking sequences generation algorithm which aims at generating sequences smaller than the sequences generated by existing methods. The algorithm, which is based on the genetic algorithms technique and sufficient conditions for completeness of test cases, basically consists of creating new sequences from small sequences. Through mutations, new sequences are generated by the algorithm. The suffcient conditions are used to determine which sequences are checking sequences. Experimental studies are presented in this work to determine the behavior of the algorithm on different contexts

Developing real-time strategy game AI is a challenging task due to that an AI-player has to deal with many different decisions and actions in an ever changing complex game world. Humans have little problem when it comes to dealing with the complexity of the game genre while it is a difficult obstacle to overcome for the computer. Adapting to the opponents strategy is one of many things that players typically have to do during the course of a game in the real-time strategy genre. This report presents a finite-state machine based solution to the mentioned problem and implements it with the help of the existing Starcraft: Broodwar AI Opprimobot. The extension is experimentally compared to the original implementation of Opprimobot. The comparison shows that both manages to achieve approximately the same win ratio against the built-in AI of Starcraft: Broodwar, but the modified version provides away to model more complex strategies.

This work deals with the design and realization of an automated test software for the Honeywell superheat controller. The first part of the project includes brief description about embedded systems and heat pumps. Afterwards testing principles are covered in a short chapter, followed by a description of the Honeywell superheat controller. After these chapters actual software structure will be introduced to the reader- with a detailed description of the most interesting parts. At the end of the document there will be a summary what was achieved exactly, and what was the plan. After this summary, the reader can study almost all the Virtual Instruments created during the development of this project.

Traits are primitive units of code reuse that serve as building blocks of classes. In this research, we enhance reuse by extending the capabilities of traits; in particular, we add modeling abstractions to them. Traits have a variety of benefits, including facilitating reuse and separation of concerns. They have appeared in several programming languages, particularly derivatives of Smalltalk. However, there is still no support for traits that contain modeling abstractions, and no straightforward support for them in general-purpose programming languages. The latter is due to structural concerns that exist for them at runtime, especially traits that contain modeling abstractions. Model-driven technologies are making inroads into the development community, albeit slowly. Modeling abstractions such as state machines and associations provide new opportunities for reuse, and can be combined with inheritance for even greater reusability. However, issues with inheritance apply also when these new abstractions are inheritable units. This suggests that traits and models ought to be able to be synergistically combined. We perform a comprehensive analysis of using modeling elements in traits. We implement such traits in Umple, which is a model-oriented programming language that permits embedding of programming concepts into models. The contributions of the thesis are: a) Adding new elements including state machines and associations into traits, hence bringing more reusability, modularity, and applications to traits; b) Developing an algorithm that allows reusing, extending, and composing state machines through traits; c) Extending traits with required interfaces so dependencies at the semantic level become part of their usage, rather than simple syntactic capture; d) Adding template parameters with associations in traits, offering new applications for traits in which it is possible to define design patterns and to have a library of most-used functionality; e) The implementation of all the above concepts, including generating code in multiple general-purpose programming languages through automatic model transformation.

The diploma thesis is focused on comparison of sensored and sensorless control of 3phase BLDC motor. This diploma thesis was compiled with engineers from Honeywell, spol. s r. o. and NXP Semiconductors comapny. Theoretical part of the diploma thesis is describing princip of function BLDC motor and different methods of control. The testing of NXP sensored and sensorless application is done in the practical part. Regarding to the fact, that applications were provided by NXP, furthemore the diploma thesis additionally contains a state machine using sensorless application from NXP. Finally, the author is evaluating a cooperation with NXP company and he thinks about next possible cooperation.

This master´s thesis thesis deals with the design of software for the control of a robotic cell, which consists of two KUKA robots and a belt conveyor. The robots will perform robotic operations similar to those in real industrial practice. At the beginning of the work will be the state of current knowledge. A key part will be the design of software for robotic cell control in the TwinCAT environment from Beckhoff. The robots and the conveyor will be controlled by a superior PLC, which will be commanded from the designed software using the HMI. The goal is to successfully implement the proposed software for robotic cell control and monitoring using a unique visualization, which will be designed specifically for the robotic cell and its associated manipulation operations.

This master’s thesis deals with analysis of state machines for embedded applications. The issue of finite-state machine is described theoretically. The document also contains a proposal for funding for modeling finite state machines in Matlab/Simulink. It is designed data representation of finite automaton. Over this data representation algorithm of minimization is applied. Finally, the algorithm is implemented to generate code in C language.