Programming multicores safely : handling barrier deadlocks

Tese de doutoramento, Informática (Ciências da Computação), Universidade de Lisboa, Faculdade de Ciências, 2015

Correctness ensuring process configuration : an approach based on partner synthesis

A configurable process model describes a family of similar process models in a given domain. Such a model can be configured to obtain a specific process model that is subsequently used to handle individual cases, for instance, to process customer orders. Process configuration is notoriously difficult as there may be all kinds of interdependencies between configuration decisions.} In fact, an incorrect configuration may lead to behavioral issues such as deadlocks and livelocks. To address this problem, we present a novel verification approach inspired by the ``operating guidelines'' used for partner synthesis. We view the configuration process as an external service, and compute a characterization of all such services which meet particular requirements using the notion of configuration guideline. As a result, we can characterize all feasible configurations (i.\,e., configurations without behavioral problems) at design time, instead of repeatedly checking each individual configuration while configuring a process model.

Automated error correction of business process models

As order dependencies between process tasks can get complex, it is easy to make mistakes in process model design, especially behavioral ones such as deadlocks. Notions such as soundness formalize behavioral errors and tools exist that can identify such errors. However these tools do not provide assistance with the correction of the process models. Error correction can be very challenging as the intentions of the process modeler are not known and there may be many ways in which an error can be corrected. We present a novel technique for automatic error correction in process models based on simulated annealing. Via this technique a number of process model alternatives are identified that resolve one or more errors in the original model. The technique is implemented and validated on a sample of industrial process models. The tests show that at least one sound solution can be found for each input model and that the response times are short.

Soundness of workflow nets: classification, decidability, and analysis

Workflow nets, a particular class of Petri nets, have become one of the standard ways to model and analyze workflows. Typically, they are used as an abstraction of the workflow that is used to check the so-called soundness property. This property guarantees the absence of livelocks, deadlocks, and other anomalies that can be detected without domain knowledge. Several authors have proposed alternative notions of soundness and have suggested to use more expressive languages, e.g., models with cancellations or priorities. This paper provides an overview of the different notions of soundness and investigates these in the presence of different extensions of workflow nets.We will show that the eight soundness notions described in the literature are decidable for workflow nets. However, most extensions will make all of these notions undecidable. These new results show the theoretical limits of workflow verification. Moreover, we discuss some of the analysis approaches described in the literature.

Ensuring Correctness During Process Configuration via Partner Synthesis

Variants of the same process can be encountered within one organization or across different organizations. For example, different municipalities, courts, and rental agencies all need to support highly similar processes. In fact, procurement and sales processes can be found in almost any organization. However, despite these similarities, there is also the need to allow for local variations in a controlled manner. Therefore, many academics and practitioners have advocated the use of configurable process models (sometimes referred to as reference models). A configurable process model describes a family of similar process models in a given domain. Such a model can be configured to obtain a specific process model that is subsequently used to handle individual cases, for instance, to process customer orders. Process configuration is notoriously difficult as there may be all kinds of interdependencies between configuration decisions. In fact, an incorrect configuration may lead to behavioral issues such as deadlocks and livelocks. To address this problem, we present a novel verification approach inspired by the “operating guidelines” used for partner synthesis. We view the configuration process as an external service, and compute a characterization of all such services which meet particular requirements via the notion of configuration guideline. As a result, we can characterize all feasible configurations (i. e., configurations without behavioral problems) at design time, instead of repeatedly checking each individual configuration while configuring a process model.

Non-desynchronizable service choreographies

A precise definition of interaction behavior between services is a prerequisite for successful business-to-business integration. Service choreographies provide a view on message exchanges and their ordering constraints from a global perspective. Assuming message sending and receiving as one atomic step allows to reduce the modelers’ effort. As downside, problematic race conditions resulting in deadlocks might appear when realizing the choreography using services that exchange messages asynchronously. This paper presents typical issues when desynchronizing service choreographies. Solutions from practice are discussed and a formal approach based on Petri nets is introduced for identifying desynchronizable choreographies.

Intellectual property and global warming: Climate justice

Engaging in a close analysis of legal and political discourse, this chapter considers conflicts over intellectual property and climate change in three key arenas: climate law; trade law; and intellectual property law. In this chapter, it is argued that there is a need to overcome the political stalemates and deadlocks over intellectual property and climate change. It is essential that intellectual property law engage in a substantive fashion with the matrix of issues surrounding fossil fuels, clean technologies, and climate change at an international level. First, this chapter examines the debate over intellectual property and climate change under the auspices of the United Nations Framework Convention on Climate Change 1992, and the establishment of the UNFCCC Climate Technology Centre and Network. It recommends that the technology mechanism should address and deal with matters of intellectual property management and policy. Second, the piece examines the discussion of global issues in the World Intellectual Property Organization, WIPO GREEN. It supports the proposal for a Global Green Patent Highway to allow for the fast-tracking of intellectual property applications in respect of green technologies. Third, the chapter investigates the dispute in the TRIPS Council at the World Trade Organization over intellectual property, climate change, and development. This section focuses upon the TRIPS Agreement 1994. This chapter calls for a Joint Declaration on Intellectual Property and Climate Change from the UNFCCC, WIPO, and the WTO. The paper concludes that intellectual property should be reformed as part of a larger effort to promote climate justice. Rather than adopt a fragmented, piecemeal approach in various international institutions, there is a need for a co-ordinated and cohesive response to intellectual property in an age of runaway, global climate change. Patent law should be fossil fuel free. Intellectual property should encourage research, development, and diffusion of renewable energy and clean technologies. It is submitted that intellectual property law reform should promote climate justice in line with Mary Robinson’s Declaration on Climate Justice 2013.

Stochastic modelling of flexible manufacturing systems

Mathematical modelling plays a vital role in the design, planning and operation of flexible manufacturing systems (FMSs). In this paper, attention is focused on stochastic modelling of FMSs using Markov chains, queueing networks, and stochastic Petri nets. We bring out the role of these modelling tools in FMS performance evaluation through several illustrative examples and provide a critical comparative evaluation. We also include a discussion on the modelling of deadlocks which constitute an important source of performance degradation in fully automated FMSs.

Coloured Petri net models for automated manufacturing systems

In this paper, we propose an approach, using Coloured Petri Nets (CPN) for modelling flexible manufacturing systems. We illustrate our methodology for a Flexible Manufacturing Cell (FMC) with three machines and three robots. We also consider the analysis of the FMC for deadlocks using the invariant analysis of CPNs.

Multithreaded Test Synthesis for Deadlock Detection

Designing and implementing thread-safe multithreaded libraries can be a daunting task as developers of these libraries need to ensure that their implementations are free from concurrency bugs, including deadlocks. The usual practice involves employing software testing and/or dynamic analysis to detect. deadlocks. Their effectiveness is dependent on well-designed multithreaded test cases. Unsurprisingly, developing multithreaded tests is significantly harder than developing sequential tests for obvious reasons. In this paper, we address the problem of automatically synthesizing multithreaded tests that can induce deadlocks. The key insight to our approach is that a subset of the properties observed when a deadlock manifests in a concurrent execution can also be observed in a single threaded execution. We design a novel, automatic, scalable and directed approach that identifies these properties and synthesizes a deadlock revealing multithreaded test. The input to our approach is the library implementation under consideration and the output is a set of deadlock revealing multithreaded tests. We have implemented our approach as part of a tool, named OMEN1. OMEN is able to synthesize multithreaded tests on many multithreaded Java libraries. Applying a dynamic deadlock detector on the execution of the synthesized tests results in the detection of a number of deadlocks, including 35 real deadlocks in classes documented as thread-safe. Moreover, our experimental results show that dynamic analysis on multithreaded tests that are either synthesized randomly or developed by third-party programmers are ineffective in detecting the deadlocks.

Trace Driven Dynamic Deadlock Detection and Reproduction

Dynamic analysis techniques have been proposed to detect potential deadlocks. Analyzing and comprehending each potential deadlock to determine whether the deadlock is feasible in a real execution requires significant programmer effort. Moreover, empirical evidence shows that existing analyses are quite imprecise. This imprecision of the analyses further void the manual effort invested in reasoning about non-existent defects. In this paper, we address the problems of imprecision of existing analyses and the subsequent manual effort necessary to reason about deadlocks. We propose a novel approach for deadlock detection by designing a dynamic analysis that intelligently leverages execution traces. To reduce the manual effort, we replay the program by making the execution follow a schedule derived based on the observed trace. For a real deadlock, its feasibility is automatically verified if the replay causes the execution to deadlock. We have implemented our approach as part of WOLF and have analyzed many large (upto 160KLoC) Java programs. Our experimental results show that we are able to identify 74% of the reported defects as true (or false) positives automatically leaving very few defects for manual analysis. The overhead of our approach is negligible making it a compelling tool for practical adoption.

A querela do declínio do simbólico: perspextivas e impasses do pensamento de Slavoj iek

Esse estudo tem por objetivo principal analisar as reflexões do filósofo e psicanalista teórico esloveno Slavoj iek acerca dos impactos subjetivos das transformações normativas ocorridas no Ocidente nos últimos cinqüenta anos. O problema do chamado declínio do Simbólico passou a ser amplamente discutido pela comunidade de psicanalistas lacanianos na qual se insere o filósofo a partir do final da década de 1990, o que constituiu uma inovação em um campo fortemente influenciado pela concepção estruturalista da subjetividade. Situando o autor como pioneiro na utilização de ferramentas conceituais lacanianas para a análise do social, o estudo divide-se em duas partes. Na primeira delas, exponho as bases teóricas do pensamento de iek, contextualizando o seu itinerário intelectual e político, e abordando as suas três linhas fundamentais de investigação: a filosofia política, a discussão sobre o ato ético e a ontologia do sujeito. Assim, o primeiro capítulo retraça o percurso que vai dos primeiros estudos sobre o funcionamento ideológico nos regimes totalitários à abordagem pop filosófica da ideologia na atualidade. Em seguida, apresento a sua redescrição da noção de comunismo à luz da tese dos novos antagonismos do capitalismo tardio. Por fim, trato da perspectiva universalista do filósofo a partir de sua leitura materialista do cristianismo, lançando mão sobretudo dos estudos de Alain Badiou sobre São Paulo. No segundo capítulo, delineamos as coordenadas centrais da concepção de sujeito em iek, cuja originalidade reside na articulação das formulações de Lacan e Hegel. As noções de grande Outro, objeto pequeno a, pulsão de morte e negatividade são tomadas como os pilares nos quais se assenta a descrição do sujeito iekiano. Na segunda parte do estudo, examinamos as teses de iek a respeito das relações entre subjetividade e cultura, com ênfase nos novos impasses que daí decorrem. As inibições que sucedem à injunção de gozar sem entraves, a melancolização do laço social, as metamorfoses da culpa, a vitimologia e a culpabilização do Outro são os tópicos centrais que sobressaem desse recorte. Nessa parte do trabalho, as reflexões de iek são cotejadas com as análises de autores de orientação lacaniana, considerados representativos desse tipo de discussão, como Jean-Pierre Lebrun, Charles Melman, Dany-Robert Dufour e Roland Chemama. Pretende-se com isso enriquecer a discussão, apontando as aproximações e distâncias que o pensamento de iek entretém com os referidos autores. O capítulo final do trabalho é consagrado ao exame crítico da démarche iekiana acerca do declínio do Simbólico. Dois tópicos de seu discurso são analisados, a saber: a) seu posicionamento ambivalente no que tange à crítica do catastrofismo; b) seu esforço de expurgar da noção de ato ético na qual ele quer encontrar saídas para os embaraços engendrados pelo dito declínio do Simbólico qualquer traço de pertencimento à tradição moral judaico-cristã, guardando dessa tradição apenas o exemplo do aspecto formal do ato. Para empreender tal exame, nos servimos, de um lado, do estudo crítico do sociólogo francês Alain Ehrenberg sobre a declinologia noção por ele cunhada para se referir ao conjunto de estudos que enfatizam o atual risco da dissolução dos laços sociais , e de outro lado, nos apoiamos na concepção de ética do filósofo neo-pragmatista Richard Rorty.

Da pedra porosa no meio do caminho à metaficção: um estudo das obras de Adriana Lisboa

Este trabalho se propõe a analisar diferentes ocorrências do fenômeno da metaficção presentes nas obras da escritora Adriana Lisboa e estabelecer conexões existentes entre o fenômeno e o drama da consciência humana, constatando que os impasses derivados da busca de uma identidade expõe a arte a uma representação irônica da realidade. Nesse sentido, analisamos as obras Sinfonia em branco, romance publicado em 2001, Um beijo de colombina, de 2003 e Rakushisha de 2007, visando a interpretação e o estudo do processo de construção dos romances, sobretudo, na sua relação entre ficção, realidade, identidade, dúvida e silêncio. A partir destas perspectivas, verificamos que todas as obras guardam em si uma multiplicidade de olhares e vozes a retratar, nas pequenas coisas do cotidiano, um universo de poesia a refletir tanto a escrita quanto a nossa condição humana

Da pedra porosa no meio do caminho à metaficção: um estudo das obras de Adriana Lisboa

Este trabalho se propõe a analisar diferentes ocorrências do fenômeno da metaficção presentes nas obras da escritora Adriana Lisboa e estabelecer conexões existentes entre o fenômeno e o drama da consciência humana, constatando que os impasses derivados da busca de uma identidade expõe a arte a uma representação irônica da realidade. Nesse sentido, analisamos as obras Sinfonia em branco, romance publicado em 2001, Um beijo de colombina, de 2003 e Rakushisha de 2007, visando a interpretação e o estudo do processo de construção dos romances, sobretudo, na sua relação entre ficção, realidade, identidade, dúvida e silêncio. A partir destas perspectivas, verificamos que todas as obras guardam em si uma multiplicidade de olhares e vozes a retratar, nas pequenas coisas do cotidiano, um universo de poesia a refletir tanto a escrita quanto a nossa condição humana

Apertem os cintos, o piloto sumiu: as escolhas profissionais juvenis no mundo contemporâneo

Esses escritos compõem as escolhas profissionais juvenis, desde a sua emergência no mundo moderno ao contemporâneo. Registrado, através de uma análise histórica em que os acontecimentos não são trazidos de forma linear, contínua e progressiva, mas em suas intensidades, lutas e surpresas. Um modo de pensar que afirmou as escolhas profissionais, afastando-as de sua força de afirmação da vida. Essas experimentações se tecem em uma pesquisa-intervenção na área da Orientação Vocacional, realizada no Serviço de Psicologia Aplicada da Universidade Federal Fluminense. Essa pesquisa acolhe o não saber escolher, para provocar tensões e torções, baseadas em leituras de autores da Filosofia da Diferença, da Psicologia, do Mundo do Trabalho. Assim, equivocar o modo de pensar predominante no Ocidente e abrir lacunas para que outros sentidos de inserção no mundo do trabalho se façam. Movimentar concepções estabelecidas, para fazê-las desconcertar e vibrar, acolhendo o ainda não sentido. Poder surpreender e inventar outros modos de se conduzir frente às escolhas profissionais, no enfrentamento dos impasses que o contemporâneo apresenta.