FC-DI - PhD Thesis
Permanent URI for this collection
Browse
Browsing FC-DI - PhD Thesis by Title
Now showing 1 - 10 of 36
Results Per Page
Sort Options
- Uma Arquitectura Multiagente para um Sistema de Processamento de Línguas Naturais Robusto e EvolutivoPublication . Balsa, João; Lopes, José Gabriel PereiraIn this work I propose an architecture that can serve as a basis to natural language processing systems that, besides pursuing its language processing goals, are robust (in the sense that the nonrecognition of some input can be automatically overcome) and/or can evolve (in the sense that the recovery from detected faults may contribute to the update of system components, allowing for an improved performance in future analogous situations). This architecture is developed in a context where the main goal is to improve the quality of the entries of Portuguese lexicons. For instance, one of the goals is to improve the subcategorization information assigned to verbs. The fact that the techniques that are used fore this purpose need large amounts of real text (therefore, faulty text), and the fact that the tools used (part-of-speech taggers, for instance) also produce mistakes, motivates the need to consider the development of robust techniques for this process. The need to face different potential problems and to integrate tools of different nature motivated the definition of a distributed architecture allowing the integration of heterogeneous components. On one hand, this approach results in an improved system performance (due to parallelism) and, on the other hand, it allows for a greater design simplicity with respect to some system components. I propose, in first place, a hierarchical architecture for diagnosing problems in the analysis of sentences that were not fully parsed, and, in second place, an architecture, in which the previous one is included, that can be used with two different perspectives: one in which the focus is on the evolution of the system, and another in which the focus is on robustness.
- Arquitecturas de Suporte ao Desenvolvimento de Protocolos de Comunicação de Tempo-realPublication . Rodrigues, João; Rodrigues, Luís Eduardo TeixeiraA crescente complexidade das aplicações distribuídas de tempo-real leva a que estas necessitem de serviços de comunicação cada vez mais sofisticados e diversificados. Enquanto as concretizações monolitíticas de protocolos de comunicação são difíceis de expandir, aperfeiçoar e ajustar às necessidades de cada aplicação, as concretizações baseadas na composição de camadas modulares são mais facilmente configuráveis e, por isso, mais atraentes para sistemas de tempo-real, onde não interessa gastar recursos com funcionalidades desnecessárias. A dissertação estuda a construção de molduras de suporte à concepção, composição e execução de sistemas de comunicação modulares para aplicações de tempo-real. Um aspecto ao qual se dá particular ênfase é a capacidade de validar a correcção da composição de protocolos no domínio do tempo. A moldura proposta inclui os seguintes componentes: i) Um modelo de suporte à composição e desenvolvimento de protocolos de comunicação que facilita a posterior análise temporal da composição; ii) Uma ferramenta de análise temporal de composição de protocolos; iii) Uma ferramenta que automatiza o processo de alocação e atribuição de prioridades; iv) Um protótipo de um ambiente de execução de composições num sistema concreto. Uma das principais contribuições deste trabalho consiste em demonstrar que é possível, através do uso de uma moldura de composição adequada, extrair informação relevante para a análise temporal a partir do código sem recorrer a linguagens de programação especializadas, facilitando desta maneira a análise e desenvolvimento do sistema. Um aspecto relevante da aproximação proposta consiste no facto da moldura usar um conjunto integrado de mecanismos que permite, simultaneamente, simplificar a tarefa de calcular o pior tempo de resposta das composições de protocolos e a optimização e depuramento da concretização resultante
- Byzantine Fault-Tolerant Agreement Protocols for Wireless Ad hoc NetworksPublication . Moniz, Henrique Lícias Senra; Neves, Nuno Fuentecilla Maia Ferreira; Correia, Miguel PupoThe thesis investigates the problem of fault- and intrusion-tolerant consensus in resource-constrained wireless ad hoc networks. This is a fundamental problem in distributed computing because it abstracts the need to coordinate activities among various nodes. It has been shown to be a building block for several other important distributed computing problems like state-machine replication and atomic broadcast. The thesis begins by making a thorough performance assessment of existing intrusion-tolerant consensus protocols, which shows that the performance bottlenecks of current solutions are in part related to their system modeling assumptions. Based on these results, the communication failure model is identified as a model that simultaneously captures the reality of wireless ad hoc networks and allows the design of efficient protocols. Unfortunately, the model is subject to an impossibility result stating that there is no deterministic algorithm that allows n nodes to reach agreement if more than n2 omission transmission failures can occur in a communication step. This result is valid even under strict timing assumptions (i.e., a synchronous system). The thesis applies randomization techniques in increasingly weaker variants of this model, until an efficient intrusion-tolerant consensus protocol is achieved. The first variant simplifies the problem by restricting the number of nodes that may be at the source of a transmission failure at each communication step. An algorithm is designed that tolerates f dynamic nodes at the source of faulty transmissions in a system with a total of n 3f + 1 nodes. The second variant imposes no restrictions on the pattern of transmission failures. The proposed algorithm effectively circumvents the Santoro- Widmayer impossibility result for the first time. It allows k out of n nodes to decide despite dn 2 e(nk)+k2 omission failures per communication step. This algorithm also has the interesting property of guaranteeing safety during arbitrary periods of unrestricted message loss. The final variant shares the same properties of the previous one, but relaxes the model in the sense that the system is asynchronous and that a static subset of nodes may be malicious. The obtained algorithm, called Turquois, admits f < n 3 malicious nodes, and ensures progress in communication steps where dnf 2 e(n k f) + k 2. The algorithm is subject to a comparative performance evaluation against other intrusiontolerant protocols. The results show that, as the system scales, Turquois outperforms the other protocols by more than an order of magnitude.
- Byzantine Fault-Tolerant Agreement Protocols for Wireless Ad hoc NetworksPublication . Moniz, Henrique Lícias Senra; Neves, Nuno Fuentecilla Maia Ferreira; Correia, Miguel PupoEsta tese investiga o problema do consenso tolerante a faltas acidentais e maliciosas em redes ad hoc sem fios. Trata-se de um problema fundamental que captura a essência da coordenação em actividades envolvendo vários nós de um sistema, sendo um bloco construtor de outros importantes problemas dos sistemas distribuídos como a replicação de máquina de estados ou a difusão atómica. A tese começa por efectuar uma avaliação de desempenho a protocolos tolerantes a intrusões já existentes na literatura. Os resultados mostram que as limitações de desempenho das soluções existentes estão em parte relacionadas com o seu modelo de sistema. Baseado nestes resultados, é identificado o modelo de falhas de comunicação como um modelo que simultaneamente permite capturar o ambiente das redes ad hoc sem fios e projectar protocolos eficientes. Todavia, o modelo é restrito por um resultado de impossibilidade que afirma não existir algoritmo algum que permita a n nós chegaram a acordo num sistema que admita mais do que n2 transmissões omissas num dado passo de comunicação. Este resultado é válido mesmo sob fortes hipóteses temporais (i.e., em sistemas síncronos) A tese aplica técnicas de aleatoriedade em variantes progressivamente mais fracas do modelo até ser alcançado um protocolo eficiente e tolerante a intrusões. A primeira variante do modelo, de forma a simplificar o problema, restringe o número de nós que estão na origem de transmissões faltosas. É apresentado um algoritmo que tolera f nós dinâmicos na origem de transmissões faltosas em sistemas com um total de n 3f + 1 nós. A segunda variante do modelo não impõe quaisquer restrições no padrão de transmissões faltosas. É apresentado um algoritmo que contorna efectivamente o resultado de impossibilidade Santoro-Widmayer pela primeira vez e que permite a k de n nós efectuarem progresso nos passos de comunicação em que o número de transmissões omissas seja dn 2 e(n k) + k 2. O algoritmo possui ainda a interessante propriedade de tolerar períodos arbitrários em que o número de transmissões omissas seja superior a . A última variante do modelo partilha das mesmas características da variante anterior, mas com pressupostos mais fracos sobre o sistema. Em particular, assume-se que o sistema é assíncrono e que um subconjunto estático dos nós pode ser malicioso. O algoritmo apresentado, denominado Turquois, admite f < n 3 nós maliciosos e assegura progresso nos passos de comunicação em que dnf 2 e(n k f) + k 2. O algoritmo é sujeito a uma análise de desempenho comparativa com outros protocolos na literatura. Os resultados demonstram que, à medida que o número de nós no sistema aumenta, o desempenho do protocolo Turquois ultrapassa os restantes em mais do que uma ordem de magnitude.
- Construção Modular de Redes Neuronais Recorrentes AnalógicasPublication . Neto, João Pedro; Costa, José FélixThis work lies within the scientific areas of Theory of Computation and artificial neural networks. It researches some possible knowledge bridges between both areas, and tries to integrate concepts in order to achieve a common and broader computational framework. This effort concentrates, firstly, on a computational architecture definition, based on a certain neural model (and subsequent demonstration that its power is equivalent to Turing Machines). Secondly, it will be developed a set of working tools to maximize and take advantage of this computational model. This will be achieved by using a high level programming language, and an automatic compilation process, able to translate the algorithmic representation of a certain problem into a parallel and modular neural network. These tools focus on two computational concepts: control and learning. In this context, control means all algorithms that use symbolic information, i.e., information with a well-defined context and meaning. Learning, on the other side, consists in a set of sub-symbolic algorithms, where there is no individual meaning for each basic piece of information, and all knowledge is distributed. It will also be presented a proposal for a specific hardware to execute the neural model neural, and a structure of a multiagent entity based on the previous concepts
- Contribuições Metodológicas para o Desenvolvimento de Assistentes de Informação PersonalizadaPublication . Afonso, Ana Paula; Silva, Mário Jorge Costa Gaspar daOs Assistentes de Informação Personalizada (AIP) são uma nova classe de aplicações especializadas de software, com requisitos específicos determinados pelas suas condições de utilização em ambiente móvel: interfaces de reduzida dimensão, conectividade intermitente e fraco poder computacional no dispositivo do utilizador. Estas características requerem que os processos de desenvolvimento tradicionais sejam revistos e novas metáforas de interacção com exploração de informação de contexto do utilizador. Propõe-se uma metodologia de desenvolvimento de AIP que conjuga o modelo de agentes como arquitectura computacional, o modelo de disseminação de informação como meio de distribuição de dados e o modelo de recuperação de informação como paradigma de interacção para acesso aos dados. Os contributos específicos deste trabalho incluem a análise dos requisitos de concepção e desenvolvimento dos AIP e a proposta de um modelo de arquitectura computacional baseado em sistemas de agentes para desenvolvimento de sistemas informáticos de suporte a este tipo de aplicações. A validação dos conceitos, modelos, infra-estruturas de software e processo de desenvolvimento propostos foi feita através da concepção e realização de dois AIP
- Controlling Security Policies in a Distributed EnvironmentPublication . Martins, Francisco; Vasconcelos, Vasco Manuel Thudichum de SerpaThis thesis proposes a typing discipline to control the migration of code in a distributed, mobile environment. Our approach is to express security policies as types, to characterise security faults as typing errors, and to use a type system to statically enforce a given security policy. We prove a type safety result that ensures that well-typed programs do not violate the prescribed security policy. We start by analysing a simple, yet non-trivial, approach to control the access to resources in a concurrent language (the $\pi-$calculus). In the concurrent framework we study the control of actions at program level and, in a finer-grained scenario, at resource level. Moving into a distributed, concurrent platform (using the D$\pi$-calculus as the underlying language), we analyse the impact of code mobility in the verification of security. In a first stage, we control mobility by specifying security policies at site level, and by considering only the source site, the target site, and the action to be executed, as the relevant information to decide if an action should be performed. This approach revealed some vulnerabilities, namely that a site cannot control by itself its own security: it always need to trust in third-parties. Aiming at overcoming this undesired lacuna, as well as simplifying the writing and maintenance of security policies, we introduce the concepts of groups, a cluster of sites that share the same security polices, and of path to account for the sequence of sites visited by migrating code. We define security at group level, avoiding the replication of polices by the sites that are members of the same group. Granting privileges to migrating paths allows for a site to precisely select the action that it grants permission to be executed (without needing to depend on third-parties). Our major result is that, recalling Milners motto, well-typed programs do not go wrong, in the sense that, if a network has no typing error, then it does not incur in a security fault.
- Controlo de Acesso em Fluxos de Trabalho AdaptáveisPublication . Domingos, Dulce; Veiga, Pedro Manuel BarbosaTo meet their flexibility requirements, workflow management systems have been extended with a set of features that support process definition and process instances changes, while ensuring their correctness. These features impose new access control requirements, since they increase the number of objects and operations that need to be protected and require mechanisms to support access control changes. In this dissertation, we define an access control model that applies and extends the role-based access control reference model to adaptive workflow management systems. Considering the generality of this model, we apply it by interpreting the permission concept in terms of the objects and the operations that need protection. The extensions we propose aim to adapt the model to the peculiarities of adaptive workflow management systems, among which we point out the mechanisms that support access control changes and that ensure the correctness of process definitions and process instances. We also define an access control system that applies our model, which has been developed according to the abstract model of a reference monitor. By using the aspect-oriented programming paradigm we achieve the separation of the access control logic, as well as the isolation of the access control functionalities that are shared by other systems, promoting their reuse. Finally, we define guidelines to integrate access control into adaptive workflow based application process development, by using the information that business process models provide.
- Controlo Distribuído de Agentes Não-Cooperantes - Exploradores e TraidoresPublication . Mariano, Pedro; Correia, LuísPretende-se dotar agentes cooperantes da capacidade de resistirem a agentes não-cooperantes. Assumimos que os agentes interagem no contexto de um jogo. O modelo desenvolvido, intitulado Jogo de Recusa, consiste num meta-jogo através do qual os agentes podem recusar-se a interagir com determinados agentes. Por ser um meta-jogo é aplicável a qualquer cenário, desde que modelado através de um jogo. O algoritmo a utilizar pelos agentes cooperantes é distribuído no sentido em que não há armazenamento central de quem são os agentes não-cooperantes. É apresentada uma análise teórica das condições em que o modelo permite obter o objectivo proposto, a par de uma avaliação experimental na qual são utilizados jogos, tais como o Dilema do Prisioneiro Iterado e o Dilema do Lenhador, comuns em trabalhos sobre cooperação. Adicionalmente, foi desenvolvido um novo jogo, de seu nome Give-Take, que além de permitir o estudo de comportamentos cooperantes, tem como característica original a existência de múltiplas estratégias cooperantes. Quando agentes com estratégias cooperantes diferentes se encontram para jogar, podem utilizar um acordo para seleccionar uma única estratégia. Este jogo pode ser utilizado no estudo da negociação de acordos.
- Design and Evaluation of Adaptative Multimodal SystemsPublication . Duarte, Carlos; Carriço, LuísThis thesis focuses on the design and evaluation of adaptive multimodal systems. The design of such systems is approached from an integrated perspective, with the goal of obtaining a solution where aspects related to both adaptive and multimodal systems are considered. The result is FAME, a model based framework for the design and development of adaptive multimodal systems, where adaptive capabilities impact directly over the process of multimodal fusion and fission operations. FAME overviews the design of systems capable of adapting to a diversified context, including variations in users, execution platform, and environment. FAME represents an evolution from previous frameworks by incorporating aspects specific to multimodal interfaces directly in the development of an adaptive platform. One of FAME's components is the Behavioral Matrix, a multipurpose instrument, used during the design phase to represent the adaptation rules. In addition, the Behavioral Matrix is also the component responsible for bridging the gap between design and evaluation stages. Departing from an analogy between transition networks for representing interaction with a system, and behavioral spaces, the Behavioral Matrix makes possible the application of behavioral complexity metrics to general adaptive systems. Moreover, this evaluation is possible during the design stages, which translates into a reduction of the resources required for evaluation of adaptive systems. The Behavioral Matrix allows a designer to emulate the behavior of a non-adaptive version of the adaptive system, allowing for comparison of the versions, one of the most used approaches to adaptive systems evaluation. In addition, the designer may also emulate the behavior of different user profiles and compare their complexity measures. The feasibility of FAME was demonstrated with the development of an adaptive multimodal Digital Book Player. The process was successful, as demonstrated by usability evaluations. Besides these evaluations, behavioral complexity metrics, computed in accordance with the proposed methodology, were able to discern between adaptive and non-adaptive versions of the player. When applied to user profiles of different perceived complexity, the metrics were also able to detect the different interaction complexity