The increase of computer systems complexity has led to a direct increase in the difficulty of verifying their correctness. For mastering this complexity, formal methods can be used in the development of systems providing techniques for both design and verification. Regarding concurrent and distributed systems, the necessity of a formal approach is more prominent given the substantial increase in complexity due to the countless number of interactions between their constituent systems. Unfortunately, however, current methods are not capable of dealing with the automated analysis of such systems in general, even if we consider only classical properties such as deadlock freedom; the state explosion problem is the main reason for this ineffectiveness. This work is a contribution in this direction. Particularly, considering networks of CSP processes, this work proposes a local strategy for deadlock analysis based on the notion of process refinement. The locality of this strategy prevents the state explosion problem generated by the interaction of constituent systems, which represents a major asset of our strategy. We define a refinement assertion for checking conflict freedom between pairs of processes in the network; this can be used for the local verification of networks with an acyclic communication topology. Concerning networks with a cyclic communication topology, we propose three patterns that prevent deadlocks: the resource allocation, the client/server and the async dynamic. These patterns impose behavioural and structural restrictions to prevent deadlocks. The behavioural restrictions are also captured by refinement assertions, which enable one to automatically verify these conditions using a refinement checker. Besides this, we develop four case studies to evaluate the efficiency of our strategy in practice: a ring buffer, a dining philosopher, and two variations of a leadership election algorithm. One of the variations of the leadership election algorithm consists of a model used in practice by the B&O Company, an industrial partner. In this study, we compare our strategy with two other techniques for deadlock freedom verification, the SSD algorithm of the Deadlock Checker tool and the built-in deadlock freedom assertion of FDR. This study demonstrates how our strategy can be used and that it might be a useful alternative to analysing complex industrial systems for deadlock freedom. / Submitted by Luiz Felipe Barbosa (luiz.fbabreu2@ufpe.br) on 2015-03-10T16:54:41Z No. of bitstreams: 2 DISSERTAÇÃO Pedro Ribeiro Gonçalves Antônio.pdf: 921372 bytes, checksum: 64def1c3ae98cbca7868d944c1f786f2 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-11T17:34:41Z (GMT). No. of bitstreams: 2 DISSERTAÇÃO Pedro Ribeiro Gonçalves Antônio.pdf: 921372 bytes, checksum: 64def1c3ae98cbca7868d944c1f786f2 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2014-03-31 / Com o aumento da complexidade dos sistemas computacionais, houve também um aumento da dificuldade na tarefa de verificação de sistemas. Para lidar com essa complexidade, métodos formais podem ser usados no desenvolvimento de sistemas, fornecendo técnicas para a modelagem e verificação. No contexto de sistemas concorrentes e distribuídos, a necessidade de uma abordagem formal é ainda mais proeminente, dadas as inúmeras possibilidades de interação entre seus sistemas componentes. Entretanto, infelizmente, os métodos atuais não se encontram, de forma geral, completamente aptos a lidar com a análise automática desses sistemas, mesmo em se tratando de propriedades clássicas como a ausência de deadlocks. A explosão do espaço de estados a ser analisado é o principal fator para essa ineficácia por parte desses sistemas. O trabalho apresentado é uma contribuição nesta direção. Considerando o conceito de redes de processos CSP, o presente trabalho propõe uma estratégia local para a análise de deadlocks baseada na noção de refinamento de processos. A localidade dessa estratégia previne a explosão de espaço de estados causada pela interação de sistemas componentes, o que constitui uma vantajosa característica da nossa estratégia. O trabalho define uma expressão de refinamento capturando o conceito de ausência de conflito, que pode ser usado para verificar localmente que uma rede de processos com uma topologia de comunicação acíclica é livre de deadlocks. Para as redes com topologia cíclica, o trabalho sistematiza e formaliza três padrões comportamentais que impedem deadlocks: o alocação de recursos, o cliente/servidor e o assíncrono dinâmico. Esses padrões impõem restrições comportamentais e estruturais para prevenir deadlocks. Essas restrições comportamentais também são capturadas através de expressões de refinamento, o que possibilita a verificação automática dessas condições com o uso de um verificador de refinamento. Além disso, são apresentados quatro estudos de caso usados para avaliar o desempenho da nossa técnica na prática: um buffer circular, um jantar dos filósofos e duas variações de um algoritmo para eleição de líder. Uma dessas variações consiste num modelo usado na prática pela empresa B&O, um parceiro industrial. Nesse estudo, avaliamos a nossa técnica em comparação com outras duas técnicas para verificação de ausência de deadlocks, o algoritmo SSD da ferramenta Deadlock Checker e a asserção de verificação de deadlocks padrão do verificador de modelos FDR. Esse estudo demonstra como a nossa estratégia é aplicada e que ela pode ser uma alternativa vantajosa para a verificação de sistemas complexos.

Submitted by Verena Bastos (verena@uefs.br) on 2015-07-28T12:52:05Z No. of bitstreams: 1 Ana Paula Rubia Oliveira do Vale Alves.pdf: 956041 bytes, checksum: 1141e73d6e9c3838a112794ff7ef544f (MD5) / Made available in DSpace on 2015-07-28T12:52:05Z (GMT). No. of bitstreams: 1 Ana Paula Rubia Oliveira do Vale Alves.pdf: 956041 bytes, checksum: 1141e73d6e9c3838a112794ff7ef544f (MD5) Previous issue date: 2014-05-16 / This research intends to show the psychological complexity of the Lygia?s characters starting from the different ways they use to deal with the suffering that arises from heartbreaks. To reach such goal it has been used Lygia Fagundes Telles? storybooks, interviews and testimonials, also academic papers and literary essays about her work besides theoretical texts: Denis de Rougemont, Bauman, Stendhal, Comte-Sponville, Freud and Lacan, among others. The corpus of this dissertation consists of 8 stories by the author, analysed in two chapters entitled: Love and rejection in female characters and The love and its deadlocks in male characters. The female characters Kori (Voc? n?o acha que esfriou?), Pomba Enamorada (homonymous story) and Alice (Emanuel) suffer from being rejected and Maria Camila (Um ch? bem forte e tr?s x?caras), from the fear of also being rejected in the future; the reactions vary between vengeance, fantasy, delirium and facing the situation. The suffering of the male protagonists come from betrayal (the saxophone man); from abandonment (Ricardo from Venha ver o p?r-do-sol); indecision (Miguel from O Noivo); and contempt (the redhead man from Hist?ria de Passarinho) and the outputs presented gravitate around sublimation/sadism, murder, forgetfulness and escape. It was observed that in female characters the loving suffering comes, mainly, from rejection, differently from the male characters whose cause for suffering is variable and the outputs present to be more radical. The different ways how female and male characters go through the love impasses created interest of deepen the theme of gender differences, what is only superficially discussed in this paper. This study confirms the psychological complexity of Lygia?s characters whose analyses point to unconscious motivations underlying attitudes, thoughts and feelings, all suggested in the interstices of the text, allowing many reflections about real characters and their positions on issues of love. / Nesta pesquisa pretendeu-se demonstrar a complexidade psicol?gica das personagens lygianas, a partir das diferentes maneiras pelas quais elas lidam com o sofrimento decorrente das desilus?es amorosas. Para alcan?ar tal objetivo, foram utilizados livros de contos, entrevistas e depoimentos de Lygia Fagundes Telles, trabalhos acad?micos e ensaios liter?rios sobre sua obra, al?m de textos dos te?ricos: Denis de Rougemont, Bauman, Stendhal, Comte-Sponville, Freud e Lacan, dentre outros. O corpus da disserta??o consiste em oito contos da autora, analisados em dois cap?tulos intitulados: Amor e rejei??o em personagens femininas e O amor e seus impasses em personagens masculinas. As personagens femininas Kori (?Voc? n?o acha que esfriou??), Pomba Enamorada (conto hom?nimo) e Alice (?Emanuel?) sofrem por serem rejeitadas e Maria Camila (?Um ch? bem forte e tr?s x?caras?), pelo temor de vir a s?-lo; as rea??es variam entre vingan?a, fantasia, del?rio e enfrentamento da situa??o. O sofrimento dos protagonistas do sexo masculino adv?m da trai??o (?O mo?o do saxofone?); do abandono (Ricardo de ?Venha ver o p?r-do-sol?); da indecis?o (Miguel de ?O noivo?) e do desprezo (o homem ruivo de ?Hist?ria de Passarinho?) e as sa?das apresentadas gravitam em torno da sublima??o/ sadismo, assassinato, esquecimento e fuga. Observou-se que em personagens femininas o sofrimento amoroso decorre, principalmente, da rejei??o, diferentemente dos homens cuja causa ? vari?vel e as sa?das se apresentam mais radicais. A maneira distinta como personagens femininas e masculinas vivenciam os impasses amorosos, gerou interesse de aprofundar a tem?tica da diferen?a de g?nero, discutida apenas superficialmente nesse trabalho. Este estudo confirma a complexidade psicol?gica das personagens lygianas cuja an?lise aponta motiva??es inconscientes subjacentes ?s atitudes, pensamentos e sentimentos, sugeridas nos interst?cios do texto, possibilitando muitas reflex?es sobre personagens reais e seus posicionamentos diante das quest?es do amor.

In a System on a Chip (SoC), interconnect is the factor limiting Performance, Power, Area and Schedule (PPAS). Distributed crossbar switches also called as Switching Central Resources (SCR) are often used to implement high performance interconnect in a SoC – Network on a Chip (NoC). Multiple issue bus protocols like AXI (from ARM), VBUSM (from TI) are used in paths critical to the performance of the whole chip. Experimental analysis of effects on PPAS by architectural modifications to the SCRs is carried out, using synthesis tools and Texas Instruments (TI) in house power estimation tools. The effects of scaling of SCR sizes are discussed in this report. These results provide a quick means of estimation for architectural changes in the early design phase. Apart from SCR design, the other major domain, which is a concern, is deadlocks. Deadlocks are situations where the network resources are suspended waiting for each other. In this report various kinds of deadlocks are classified and their respective mitigations in such networks are provided. These analyses are necessary to qualify distributed SCR interconnect, which uses multiple issue protocols, across all scenarios of transactions. The entire analysis in this report is carried out using a flagship product of Texas Instruments. This ASIC SoC is a complex wireless base station developed in 2010- 2011, having 20 major cores. Since the parameters of crossbar switches with multiple issue bus protocols are commonly used in SoCs across the semiconductor industry, this reports provides us a strong basis for architectural/design selection and validation of all such high performance device interconnects. This report can be used as a seed for the development of an interface tool for architects. For a given architecture, the tool suggests architectural modifications, and reports deadlock situations. This new tool will aid architects to close design problems and bring provide a competitive specification very early in the design cycle. A working algorithm for the tool development is included in this report. / text

The goal of this dissertation is to present new and improved techniques for fully automatic verification of sequential and concurrent software libraries. In most cases, automatic software verification is plagued by undecidability, while in many others it suffers from prohibitively high computational complexity. Model checking -- a highly successful technique used for verifying finite state hardware circuits against logical specifications -- has been less widely adapted for software, as software verification tends to involve reasoning about potentially infinite state-spaces. Two of the biggest culprits responsible for making software model checking hard are heap-allocated data structures and concurrency. In the first part of this dissertation, we study the problem of verifying shape properties of sequential data structure libraries. Such libraries are implemented as collections of methods that manipulate the underlying data structure. Examples of such methods include: methods to insert, delete, and update data values of nodes in linked lists, binary trees, and directed acyclic graphs; methods to reverse linked lists; and methods to rotate balanced trees. Well-written methods are accompanied by documentation that specifies the observational behavior of these methods in terms of pre/post-conditions. A pre-condition [phi] for a method M characterizes the state of a data structure before the method acts on it, and the post-condition [psi] characterizes the state of the data structure after the method has terminated. In a certain sense, we can view the method as a function that operates on an input data structure, producing an output data structure. Examples of such pre/post-conditions include shape properties such as acyclicity, sorted-ness, tree-ness, reachability of particular data values, and reachability of pointer values, and data structure-specific properties such as: "no red node has a red child'', and "there is no node with data value 'a' in the data structure''. Moreover, methods are often expected not to violate certain safety properties such as the absence of dangling pointers, absence of null pointer dereferences, and absence of memory leaks. We often assume such specifications as implicit, and say that a method is incorrect if it violates such specifications. We model data structures as directed graphs, and use the two terms interchangeably. Verifying correctness of methods operating on graphs is an instance of the parameterized verification problem: for every input graph that satisfies [phi], we wish to ensure that the corresponding output graph satisfies [psi]. Control structures such as loops and recursion allow an arbitrary method to simulate a Turing Machine. Hence, the parameterized verification problem for arbitrary methods is undecidable. One of the main contributions of this dissertation is in identifying mathematical conditions on a programming language fragment for which parameterized verification is not only decidable, but also efficient from a complexity perspective. The decidable fragment we consider can be broadly sub-divided into two categories: the class of iterative methods, or methods which use loops as a control flow construct to traverse a data structure, and the class of recursive methods, or methods that use recursion to traverse the data structure. We show that for an iterative method operating on a directed graph, if we are guaranteed that if the number of destructive updates that a method performs is bounded (by a constant, i.e., O(1)), and is guaranteed to terminate, then the correctness of the method can be checked in time polynomial in the size of the method and its specifications. Further, we provide a well-defined syntactic fragment for recursive methods operating on tree-like data structures, which assures that any method in this fragment can be verified in time polynomial in the size of the method and its specifications. Our approach draws on the theory of tree automata, and we show that parameterized correctness can be reduced to emptiness of finite-state, nondeterministic tree automata that operate on infinite trees. We then leverage efficient algorithms for checking the emptiness of such tree automata to obtain a tractable verification framework. Our prototype tool demonstrates the low theoretical complexity of our technique by efficiently verifying common methods that operate on data structures. In the second part of the dissertation, we tackle another obstacle for tractable software verification: concurrency. In particular, we explore application of a static analysis technique based on interprocedural dataflow analysis to predict and document deadlocks in concurrent libraries, and analyze deadlocks in clients that use such libraries. The kind of deadlocks that we focus result from circular dependencies in the acquisition of shared resources (such as locks). Well-written applications that use several locks implicitly assume a certain partial order in which locks are acquired by threads. A cycle in the lock acquisition order is an indicator of a possible deadlock within the application. Methods in object-oriented concurrent libraries often encapsulate internal synchronization details. As a result of information hiding, clients calling the library methods may cause thread safety violations by invoking methods in a manner that violates the partial ordering between lock acquisitions that is implicit within the library. Given a concurrent library, we present a technique for inferring interface contracts that speciy permissible concurrent method calls and patterns of aliasing among method arguments that guarantee deadlock-free execution for the methods in the library. The contracts also help client developers by documenting required assumptions about the library methods. Alternatively, the contracts can be statically enforced in the client code to detect potential deadlocks in the client. Our technique combines static analysis with a symbolic encoding for tracking lock dependencies, allowing us to synthesize contracts using a satisfiability modulo theories (SMT) solver. Additionally, we investigate extensions of our technique to reason about deadlocks in libraries that employ signalling primitives such as wait-notify for cooperative synchronization. We demonstrate its scalability and efficiency with a prototype tool that analyzed over a million lines of code for some widely-used open-source Java libraries in less than 50 minutes. Furthermore, the contracts inferred by our approach have been able to pinpoint real bugs, i.e. deadlocks that have been reported by users of these libraries. / text

The thesis contributes to the theoretical study of Petri net theory. We conduct boundedness and liveness structural analysis of Synchronized Choice nets (SNC) based on fundamental structures in Petri nets and identified as first-order structures. By studying these structures, the study proposes two ways of preserving good properties: addition of second-order structures or other asymmetric structures. Liveness of these new SNC nets is studied based on the concept of siphons and traps. We prove that SNC nets thus formed are structurally bounded and live. The thesis extends this class of nets to those with pure TP and PT first-order structures and explores its structural and marking conditions. Based on this, we introduce a new class of Synchronized Choice nets called Expanded Synchronized Choice nets.

L'application de la théorie du droit des brevets à l'innovation en biotechnologies humaines révèle certaines fragilités et pose de nombreux problèmes, au regard des composantes techniques et éthiques de sa protection Juridique. Au plan technique, la condition d'une invention en particulier, longtemps laissée de côté par la doctrine et par la jurisprudence, se trouve rappelée aux États-Unis, dans le secteur des biotechnologies humaines, comme une condition essentielle. Au plan éthique, les biotechnologies humaines, porteuses d'immenses espoirs. suscitent en même temps qu'une fascination certaine, la crainte de dérives qui échapperaient au contrôle des institutions compétentes. Les exclusions éthiques à la brevetabilité sont un moyen de les appréhender. A la lumière d'une approche comparative entre le droit européen et le droit américain, à titre principal, faisant état du droit français à titre d'illustration du droit européen, la, réflexion dans ce travail porte sur les limites des exceptions et des exclusions, techniques et éthiques, à la brevetabilité des inventions en biotechnologies humaines, et formule quelques pistes de réflexion. Face à la menace de blocages de la recherche par l'effet des brevets en biotechnologies humaines, largement alléguée dans ce champ de recherche, certains partent à la conquête de modèles alternatifs de gestion collective de l'innovation. La théorie économique des communs, dont la transposition à la sphère juridique concernée par les ressources immatérielles, se révèle, à cet égard, particulièrement prometteuse à la lumière des biotechnologies humaines et peut permettre d'unifier juridiquement ce foisonnement d'initiatives. / Applying the patent law theory to innovation in the field of human biotechnology highlights weaknesses and raises multiple issues related to the technical and ethical elements of its legal protection. In terms of technique, a recent change in United States Law is shedding light on the condition of invention, now considered an essential condition, after being long disregarded by doctrine and case law. In terms of ethics, though fascinating and raising high hopes and great expectations. human biotechnology concurrently gives rise to the fear of possible drifts that might elude the control of competent institutions. Ethical exclusions from patentability are one solution to ward them off. Comparing American and European law, illustrated by a reference to French law, this study focuses on the limitations of technical and ethical exceptions and exclusions from the patentability of human biotechnology inventions and suggests some further lines of thought. Facing the threat of possible research deadlocks induced by human biotechnology patents, largely invoked in this research field, alternative models of collective innovation management are. being sought. Transposed to the legal sphere delving into the issue of immaterial resources, the economic theory of the Commons applied to human biotechnology appears as highly promising and could result in a legal unification of this profusion of initiatives.

No description available.

<p>  Modern datacenter network applications continue to demand ultra low latencies and very high throughputs. At the same time, network infrastructure keeps achieving higher speeds and larger bandwidths. We still need better network management solutions to keep these two demand and supply fronts go hand-in-hand. There are key metrics that define network performance such as flow completion time (the lower the better), throughput (the higher the better), and end-to-end latency (the lower the better) that are mainly governed by how effectively network application get their fair share of network resources. We observe that buffer utilization on network switches gives a very accurate indication of network performance. Therefore, network buffer management is important in modern datacenter networks, and other network management solutions can be efficiently built around buffer utilization. This dissertation presents three solutions based on buffer use on network switches.</p> <p>  This dissertation consists of three main sections. The first section is on a specification language for buffer management in modern programmable switches. The second section is on a congestion control solution for Remote Direct Memory Access (RDMA) networks. The third section is on a solution to head-of-the-line blocking in modern datacenter networks.</p>