Despite extensive research on Byzantine Fault Tolerant (BFT) systems, overheads associated with such solutions preclude widespread adoption. Past efforts such as the Cross Fault Tolerance (XFT) model address this problem by making a weaker assumption that a majority of processes are correct and communicate synchronously. Although XPaxos of Liu et al. (using the XFT model) achieves similar performance as Paxos, it does not scale with the number of faults. Also, its reliance on a single leader introduces considerable downtime in case of failures. This thesis presents Elpis, the first multi-leader XFT consensus protocol. By adopting the Generalized Consensus specification from the Crash Fault Tolerance model, we were able to devise a multi-leader protocol that exploits the commutativity property inherent in the commands ordered by the system. Elpis maps accessed objects to non-faulty processes during periods of synchrony. Subsequently, these processes order all commands which access these objects. Experimental evaluation confirms the effectiveness of this approach: Elpis achieves up to 2x speedup over XPaxos and up to 3.5x speedup over state-of-the-art Byzantine Fault-Tolerant Consensus Protocols. / Master of Science / Online services like Facebook, Twitter, Netflix and Spotify to cloud services like Google and Amazon serve millions of users which include individuals as well as organizations. They use many distributed technologies to deliver a rich experience. The distributed nature of these technologies has removed geographical barriers to accessing data, services, software, and hardware. An essential aspect of these technologies is the concept of the shared state. Distributed databases with multiple replicated data nodes are an example of this shared state. Maintaining replicated data nodes provides several advantages such as (1) availability so that in case one node goes down the data can still be accessed from other nodes, (2) quick response times, by placing data nodes closer to the user, the data can be obtained quickly, (3) scalability by enabling multiple users to access different nodes so that a single node does not cause bottlenecks. To maintain this shared state some mechanism is required to maintain consistency, that is the copies of these shared state must be identical on all the data nodes. This mechanism is called Consensus, and several such mechanisms exist in practice today which use the Crash Fault Tolerance (CFT). The CFT model implies that these mechanisms provide consistency in the presence of nodes crashing. While the state-of-the-art for security has moved from assuming a trusted environment inside a firewall to a perimeter-less and semi-trusted environment with every service living on the internet, only the application layer is required to be secured while the core is built just with an idea of crashes in mind. While there exists comprehensive research on secure Consensus mechanisms which utilize what is called the Byzantine Fault Tolerance (BFT) model, the extra costs required to implement these mechanisms and comparatively lower performance in a geographically distributed setting has impeded widespread adoption. A new model recently proposed tries to find a cross between these models that is achieving security while paying no extra costs called the Cross Fault Tolerance (XFT). This thesis presents Elpis, a consensus mechanism which uses precisely this model that will secure the shared state from its core without modifications to the existing setups while delivering high performance and lower response times. We perform a comprehensive evaluation on AWS and demonstrate that Elpis achieves 3.5x over the state-of-the-art while improving response times by as much as 50%.

Le Reservoir Computing (RC) est un paradigme s’inspirant du cerveau humain, apparu récemment au début des années2000. Il s'agit d'un calculateur neuromorphique habituellement décomposé en trois parties dont la plus importanteappelée "réservoir" est très proche d'un réseau de neurones récurrent. Il se démarque des autres réseaux de neuronesartificiels notamment grâce aux traditionnelles phases d'apprentissage et d’entraînement qui ne sont plus appliquées surla totalité du réseau de neurones mais uniquement sur la lecture du réservoir, ce qui simplifie le fonctionnement etfacilite une réalisation physique. C'est précisément dans ce contexte qu’ont été réalisés les travaux de recherche de cettethèse, durant laquelle nous avons réalisé une première implémentation physique opto-électronique de système RC.Notre approche des systèmes physiques RC repose sur l'utilisation de dynamiques non-linéaires à retards multiples dansl'objectif de reproduire le comportement complexe d'un réservoir. L'utilisation d'un système dynamique purementtemporel pour reproduire la dimension spatio-temporelle d'un réseau de neurones traditionnel, nécessite une mise enforme particulière des signaux d'entrée et de sortie, appelée multiplexage temporel ou encore étape de masquage. Troisannées auront été nécessaires pour étudier et construire expérimentalement nos démonstrateurs physiques basés sur desdynamiques non-linéaires à retards multiples opto-électroniques, en longueur d'onde et en intensité. La validationexpérimentale de nos systèmes RC a été réalisée en utilisant deux tests de calcul standards. Le test NARMA10 (test deprédiction de séries temporelles) et la reconnaissance vocale de chiffres prononcés (test de classification de données) ontpermis de quantifier la puissance de calcul de nos systèmes RC et d'atteindre pour certaines configurations l'état del'art. / Reservoir Computing (RC) is a currently emerging new brain-inspired computational paradigm, which appeared in theearly 2000s. It is similar to conventional recurrent neural network (RNN) computing concepts, exhibiting essentiallythree parts: (i) an input layer to inject the information in the computing system; (ii) a central computational layercalled the Reservoir; (iii) and an output layer which is extracting the computed result though a so-called Read-Outprocedure, the latter being determined after a learning and training step. The main originality compared to RNNconsists in the last part, which is the only one concerned by the training step, the input layer and the Reservoir beingoriginally randomly determined and fixed. This specificity brings attractive features to RC compared to RNN, in termsof simplification, efficiency, rapidity, and feasibility of the learning, as well as in terms of dedicated hardwareimplementation of the RC scheme. This thesis is indeed concerned by one of the first a hardware implementation of RC,moreover with an optoelectronic architecture.Our approach to physical RC implementation is based on the use of a sepcial class of complex system for the Reservoir,a nonlinear delay dynamics involving multiple delayed feedback paths. The Reservoir appears thus as a spatio-temporalemulation of a purely temporal dynamics, the delay dynamics. Specific design of the input and output layer are shownto be possible, e.g. through time division multiplexing techniques, and amplitude modulation for the realization of aninput mask to address the virtual nodes in the delay dynamics. Two optoelectronic setups are explored, one involving awavelength nonlinear dynamics with a tunable laser, and another one involving an intensity nonlinear dynamics with anintegrated optics Mach-Zehnder modulator. Experimental validation of the computational efficiency is performedthrough two standard benchmark tasks: the NARMA10 test (prediction task), and a spoken digit recognition test(classification task), the latter showing results very close to state of the art performances, even compared with purenumerical simulation approaches.

Over the past two decades, autonomous driving technology has made tremendous breakthroughs. With this technology, human drivers have been able to take their hands off the wheel in many scenarios and let the vehicle drive itself. Highway scenarios are less disturbed than urban scenarios, so autonomous driving is much simpler to implement and can be accomplished very well with a rule-based approach. However, a significant drawback of the rule-based approach compared to human drivers is that it is difficult to predict the intent of the vehicles in the surrounding environment by designing the algorithm’s logic. In contrast, human drivers can easily implement the intent analysis. Therefore, in this research work, we introduce the prediction module as the upstream of the autonomous driving decision-making module, so that the autonomous driving decision-maker has richer input information to better optimize the decision output by getting the intent of the surrounding vehicles. The evaluation of the final results confirms that our proposed approach is helpful for optimizing Rule-based autonomous driving decisions. / Under de senaste två decennierna har tekniken för autonom körning gjort enorma genombrott. Med denna teknik har mänskliga förare kunnat ta bort händerna från ratten i många situationer och låta fordonet köra sig självt. Scenarier på motorvägar är mindre störda än scenarier i städer, så autonom körning är mycket enklare att genomföra och kan åstadkommas mycket bra med en regelbaserad metod. En betydande nackdel med det regelbaserade tillvägagångssättet jämfört med mänskliga förare är dock att det är svårt att förutsäga avsikten hos fordonen i den omgivande miljön genom att utforma algoritmens logik. Däremot kan mänskliga förare lätt genomföra avsiktsanalysen. I det här forskningsarbetet inför vi därför förutsägelsemodulen som en uppströmsmodul för beslutsfattandet vid autonom körning, så att beslutsfattaren vid autonom körning har mer omfattande information för att bättre optimera beslutsutfallet genom att få reda på de omgivande fordonens intentioner. Utvärderingen av slutresultaten bekräftar att vårt föreslagna tillvägagångssätt är till hjälp för att optimera regelbaserade beslut om autonom körning.

Commodity brain-computer interfaces (BCI) are beginning to accompany everything from toys and games to sophisticated health care devices. These contemporary interfaces allow for varying levels of interaction with a computer. Not surprisingly, the more intimately BCIs are integrated into the nervous system, the better the control a user can exert on a system. At one end of the spectrum, implanted systems can enable an individual with full body paralysis to utilize a robot arm and hold hands with their loved ones [28, 62]. On the other end of the spectrum, the untapped potential of commodity devices supporting electroencephalography (EEG) and electromyography (EMG) technologies require innovative approaches and further research. This thesis proposes a modularized software architecture designed to build flexible systems based on input from commodity BCI devices. An exploratory study using a commodity EEG provides concrete assessment of the potential for the modularity of the system to foster innovation and exploration, allowing for a combination of a variety of algorithms for manipulating data and classifying results. Specifically, this study analyzes a pipelined architecture for researchers, starting with the collection of spatio temporal brain data (STBD) from a commodity EEG device and correlating it with intentional behaviour involving keyboard and mouse input. Though classification proves troublesome in the preliminary dataset considered, the architecture demonstrates a unique and flexible combination of a liquid state machine (LSM) and a deep belief network (DBN). Research in methodologies and techniques such as these are required for innovation in BCIs, as commodity devices, processing power, and algorithms continue to improve. Limitations in terms of types of classifiers, their range of expected inputs, discrete versus continuous data, spatial and temporal considerations and alignment with neural networks are also identified. / Graduate / 0317 / 0984 / jasoncummer@gmail.com

Made available in DSpace on 2015-03-05T13:53:45Z (GMT). No. of bitstreams: 0 Previous issue date: 11 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste trabalho é proposto um método de extração de conhecimento a partir de Redes Neurais Recorrentes. Expressar formalmente o conhecimento armazenado dentro de uma Rede Neural Artificial representa um grande desafio, já que tal conhecimento precisa ser reformulado e apresentado de uma maneira simples e inteligível. Três formalismos simbólicos são abordados para a representação deste conhecimento: Autômatos Finitos Difusos, Cadeias de Markov e Autômatos Finitos Determinísticos. Para as extrações de conhecimento utilizadas no trabalho, atribui-se significado às regiões do espaço de atividade dos neurônios. O método proposto utiliza a clusterização do espaço neural para obtenção dos estados do autômato, sendo utilizados para isso, o algoritmo K-means e a clusterização difusa. A obtenção do conhecimento é feita utilizando-se Redes Neurais Recorrentes para aprender o comportamento de dois sistemas dinâmicos não lineares e, a partir das redes treinadas, extrair os estados e possíveis transições do autômato. Os sis / ln this work a method ofknowledge extraction from Recurrent Neural Network is proposed. Express formally the knowledge stored inside an Artificial Neural Network is a great challenge, because such knowledge has to be reformulated and presented by simple and understandable means. Three symbolic formats are presented for the representation of this knowledge: Fuzzy Finite Automata, Markov Chains and Deterministic Finite Automata. For the knowledge extraction used in this work, each space region of the neuron activity is associated to a meaning. The considered method uses clusterization of the neural space in order to obtain the automata states, using the K-means algorithm and the fuzzy clustering. The knowledge acquisition is made using Recurrent Neural Networks to learn the behavior of the two non linear dynamic systems and, from the trained nets, to extract the states and possible automata transitions. The dynamic systems are the lnverse Pendulum system and the Lorenz system. The presented extraction method wa

Made available in DSpace on 2016-04-29T14:23:06Z (GMT). No. of bitstreams: 1 Luciano Gaspar.pdf: 1342989 bytes, checksum: 2adb8081f31a71914dc0e2627497482b (MD5) Previous issue date: 2012-05-10 / The aspects that affect the complexity in the development of systems are, also, barriers to the teaching and learning process of software modeling. Many techniques, tools and processes are adopted in this specific kind of teaching, although, one of the greatest issues found in this task is to create conditions in order to make the student experiment such a complexity in the classroom. The adoption of criteria for software quality analysis is an option that, into the architectural prospect, can reveal that, even the algorithm with few code lines are fragile and, along their life cycle, may present problems of scalability, maintenance and reuse. In this aspect, the purpose of this research is to evaluate if the codes produced by the student, supported by the concepts and techniques of the State Model, will express the initial characteristics of a modularized structure. A tool which extends the functions of the BlueJ teaching environment was developed and it is presented in this paper. That tool, associated with the BlueJ native resources and the State Machines learning make it possible for the student to accomplish software model descriptions according to the structural and environmental code prospects / Os aspectos que afetam a complexidade no desenvolvimento de sistemas também são barreiras para o processo de ensino-aprendizagem de modelagem de software. Muitas técnicas, ferramentas e processos são adotados nesse tipo específico de ensino, porém, uma das dificuldades encontradas é criar condições para que o aluno vivencie tal complexidade em sala de aula. Como alternativa, a adoção de critérios de análise da qualidade de software, sob a perspectiva arquitetural, pode revelar que mesmo os algorítmos com poucas linhas de código são frágeis e ao longo do seu ciclo de vida apresentam problemas de escalabilidade, manutenção e reuso. Nesse sentido, o propósito desta pesquisa é avaliar se o código produzido pelo aluno, apoiado nos conceitos e técnicas do Modelo de Estados, manifestará características iniciais de uma estrutura modularizada. Uma ferramenta que estende as funcionalidades do ambiente de ensino BlueJ foi desenvolvida e é apresentada neste trabalho. Esta ferramenta, associada aos recursos nativos do BlueJ e aos conhecimentos de Máquina de Estados, permite que o aluno elabore descrições de modelos de software dentro das perspectivas estrutural e comportamental do código

<p>An Adaptive Cruise Controller (ACC) is an extension of an ordinary cruise controller. In addition to maintaining a desired set velocity, an ACC can also maintain a desired time gap to the vehicle ahead. For this end, both the engine andthe brakes are controlled. </p><p>The purpose with this thesis has been to develop control strategies for an ACC used in heavy vehicles. The focus of the work has been the methods used for switching between the use of engine and brake. Two different methods have been studied, a hybrid controller and an MPC-controller. </p><p>For the hybrid controller, the main contribution has been to use the influence of the surroundings on the acceleration of the truck. This consists of several parts such as wind drag, road slope and rolling resistance. The estimated influence of the surroundings is used as a switch point between the use of engine and brakes. Ideally, these switch points give bumpless actuator switches. </p><p>The interest in the MPC-controller as an alternative solution was to achieve automatic actuator switching, thus with no explicitly defined switch points. The MPC-controller is based on a model of the system including bounds on the control signals. Using this knowledge, the MPC-controller will choose the correct actuator for the current driving situation. </p><p>Results from simulations show that both methods solve the actuator switch problem. The advantages with the hybrid controller are that it is implementable in a truck with the hardware used today and that it is relatively simple to parameterise. A drawback is that explicit switch points between the uses of the different actuators have to be included. The advantages with the MPC-controller are that no explicit switch points have to be introduced and that constraints and time delays on signals in the system can be handled in a simple way. Among the drawbacks, it can be mentioned that the variant of MPC, used in this thesis, is too complex to implement in the control system currently used in trucks. One further important drawback is that MPC demands a mathematical model of the system.</p>

An Adaptive Cruise Controller (ACC) is an extension of an ordinary cruise controller. In addition to maintaining a desired set velocity, an ACC can also maintain a desired time gap to the vehicle ahead. For this end, both the engine andthe brakes are controlled. The purpose with this thesis has been to develop control strategies for an ACC used in heavy vehicles. The focus of the work has been the methods used for switching between the use of engine and brake. Two different methods have been studied, a hybrid controller and an MPC-controller. For the hybrid controller, the main contribution has been to use the influence of the surroundings on the acceleration of the truck. This consists of several parts such as wind drag, road slope and rolling resistance. The estimated influence of the surroundings is used as a switch point between the use of engine and brakes. Ideally, these switch points give bumpless actuator switches. The interest in the MPC-controller as an alternative solution was to achieve automatic actuator switching, thus with no explicitly defined switch points. The MPC-controller is based on a model of the system including bounds on the control signals. Using this knowledge, the MPC-controller will choose the correct actuator for the current driving situation. Results from simulations show that both methods solve the actuator switch problem. The advantages with the hybrid controller are that it is implementable in a truck with the hardware used today and that it is relatively simple to parameterise. A drawback is that explicit switch points between the uses of the different actuators have to be included. The advantages with the MPC-controller are that no explicit switch points have to be introduced and that constraints and time delays on signals in the system can be handled in a simple way. Among the drawbacks, it can be mentioned that the variant of MPC, used in this thesis, is too complex to implement in the control system currently used in trucks. One further important drawback is that MPC demands a mathematical model of the system.

In formal language theory, studying shortest strings in languages, and variations thereof, can be useful since these strings can serve as small witnesses for properties of the languages, and can also provide bounds for other problems involving languages. For example, the length of the shortest string accepted by a regular language provides a lower bound on the state complexity of the language. In Chapter 1, we introduce some relevant concepts and notation used in automata and language theory, and we show some basic results concerning the connection between the length of the shortest string and the nondeterministic state complexity of a regular language. Chapter 2 examines the effect of the intersection operation on the length of the shortest string in regular languages. A tight worst-case bound is given for the length of the shortest string in the intersection of two regular languages, and loose bounds are given for two variations on the problem. Chapter 3 discusses languages that are defined over a free group instead of a free monoid. We study the length of the shortest string in a regular language that becomes the empty string in the free group, and a variety of bounds are given for different cases. Chapter 4 mentions open problems and some interesting observations that were made while studying two of the problems: finding good bounds on the length of the shortest squarefree string accepted by a deterministic finite automaton, and finding an efficient way to check if a finite set of finite words generates the free monoid. Some of the results in this thesis have appeared in work that the author has participated in \cite{AngPigRamSha,AngShallit}.

In formal language theory, studying shortest strings in languages, and variations thereof, can be useful since these strings can serve as small witnesses for properties of the languages, and can also provide bounds for other problems involving languages. For example, the length of the shortest string accepted by a regular language provides a lower bound on the state complexity of the language. In Chapter 1, we introduce some relevant concepts and notation used in automata and language theory, and we show some basic results concerning the connection between the length of the shortest string and the nondeterministic state complexity of a regular language. Chapter 2 examines the effect of the intersection operation on the length of the shortest string in regular languages. A tight worst-case bound is given for the length of the shortest string in the intersection of two regular languages, and loose bounds are given for two variations on the problem. Chapter 3 discusses languages that are defined over a free group instead of a free monoid. We study the length of the shortest string in a regular language that becomes the empty string in the free group, and a variety of bounds are given for different cases. Chapter 4 mentions open problems and some interesting observations that were made while studying two of the problems: finding good bounds on the length of the shortest squarefree string accepted by a deterministic finite automaton, and finding an efficient way to check if a finite set of finite words generates the free monoid. Some of the results in this thesis have appeared in work that the author has participated in \cite{AngPigRamSha,AngShallit}.