Models of true concurrency have gained a lot of interest over the last decades as models of concurrent or distributed systems which avoid the well-known problem of state space explosion of the interleaving models. In this thesis, we study such models from two perspectives. Firstly, we study the relation between Petri nets and stable event structures. Petri nets can be considered as one of the most general and perhaps wide-spread models of true concurrency. Event structures on the other hand, are simpler models of true concurrency with explicit causality and conflict relations. Stable event structures expand the class of event structures by allowing events to be enabled in more than one way. While the relation between Petri nets and event structures is well understood, the relation between Petri nets and stable event structures has not been studied explicitly. We define a new and more compact unfoldings of safe Petri nets which is directly translatable to stable event structures. In addition, the notion of complete finite prefix is defined for compact unfoldings, making the existing model checking algorithms applicable to them. We present algorithms for constructing the compact unfoldings and their complete finite prefix. Secondly, we study probabilistic models of true concurrency. We extend the definition of probabilistic event structures as defined by Abbes and Benveniste to a newly defined class of stable event structures, namely, jump-free stable event structures arising from Petri nets (characterised and referred to as net-driven). This requires defining the fundamental concept of branching cells in probabilistic event structures, for jump-free net-driven stable event structures, and by proving the existence of an isomorphism among the branching cells of these systems, we show that the latter benefit from the related results of the former models. We then move on to defining a probabilistic logic over probabilistic event structures (PESL). To our best knowledge, this is the first probabilistic logic of true concurrency. We show examples of expressivity achieved by PESL, which in particular include properties related to synchronisation in the system. This is followed by the model checking algorithm for PESL for finite event structures. Finally, we present a logic over stable event structures (SEL) along with an account of its expressivity and its model checking algorithm for finite stable event structures.

As Web services grow in maturity and use, so do the methods which are being used to test and maintain them. Regression Testing is a major component of most major testing systems but has only begun to be applied to Web services. The majority of the tools and techniques applying regression test to Web services are focused on test-case generation, thus ignoring the potential savings of regression test selection. Regression test selection optimizes the regression testing process by selecting a subset of all tests, while still maintaining some level of confidence about the system performing no worse than the unmodified system. A safe regression test selection technique implies that after selection, the level of confidence is as high as it would be if no tests were removed. Since safe regression test selection techniques generally involve code-based (white-box) testing, they cannot be directly applied to Web services due to their loosely-coupled, standards-based, and distributed nature. A framework which automates both the regression test selection and regression testing processes for Web services in a decentralized, end-to-end manner is proposed. As part of this approach, special consideration is given to the concurrency issues which may occur in an autonomous and decentralized system. The resulting synchronization method will be presented along with a set of algorithms which manage the regression testing and regression test selection processes throughout the system. A set of empirical results demonstrate the feasibility and benefit of the approach.

FOOPS is a concurrent object oriented specification language with an executable subset. In this thesis we propose an extension of FOOPS with features for specifying systems of distributed and autonomous objects. This extension supports most features of concurrent object oriented programming, including classes of objects with associated methods and attributes, object identity, dynamic object creation and deletion, overloading, polymorphism, inheritance with overriding, dynamic binding, concurrency, nondeterminism, atomic execution, evaluation of method expressions as background processes, and object protection. The main contribution of this thesis is to develop a framework for supporting formal development of software in the extension of FOOPS mentioned above. In particular, we introduce a structural operational semantics for FOOPS, a notion of refinement for concurrent object oriented programs, congruence properties of refinement of FOOPS programs, and tools for mechanising refinement proofs. The operational semantics is the core of the formal definition of FOOPS. It is used to define notions of refinement for FOOPS states, programs, and specifications. Those notions and associated proof techniques for proving refinement are used to illustrate stepwise formal development of programs in FOOPS. The congruence properties of refinement (with respect to some of FOOPS operators) justify compositional development of software in FOOPS. The tools help to validate the framework introduced in this thesis and motivate its use in practice.

Muitos dos sistemas de computação existentes atualmente são concorrentes, ou seja, neles constam diversas entidades que, ao mesmo tempo, operam sobre um conjunto de recursos compartilhados. Nesse contexto, devemos controlar a concorrência das diversas operações realizadas, ou então a interferência entre elas poderia causar inconsistências nos recursos compartilhados ou nas próprias operações realizadas. Nesse texto, vamos tratar especificamente de estruturas de dados concorrentes, ou seja, estruturas de dados cujas operações associadas -- consideramos inserção, remoção e busca -- sejam passíveis de execução simultânea por diversas entidades. Tendo em vista o controle da concorrência, vamos adotar uma abordagem baseada no emprego de locks, uma primitiva de sincronização muito usual na literatura. Nossa discussão será apresentada em termos de certas estruturas de dados chamadas skip graphs, que têm propriedades interessantes para outros contextos, como o contexto de sistemas distribuídos. / Many existing computer systems are concurrent, or, in other words, they are composed of many entities that, at the same time, operate over some set of shared resources. In this context, we must control the concurrency of the operations, otherwise the interference between them could cause inconsistencies in the shared resources or in the operations themselves. In this text, we specifically discuss concurrent data structures, or, in other words, data structures over which the associated operations -- we consider insertion, removal and search -- could be executed simultaneously by various entities. In order to control the concurrency, we will employ an aproach based on the use of locks, a widely known synchronization primitive in the literature. Our discussion will be presented in terms of data structures called skip graphs, which have interesting properties in other contexts, as the context of distributed systems.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / XML tornou-se um padrÃo amplamente utilizado na representaÃÃo e troca de dados entre aplicaÃÃes na Web. Com isso, grande volume desses dados està distribuÃdo na Web e armazenado em diversos meios de persistÃncia. SGBD relacionais que suportam XML fornecem tÃcnicas de controle de concorrÃncia para gerenciar esses dados. A estrutura dos dados XML, entretanto, dificulta a aplicaÃÃo dessas tÃcnicas. Trabalhos estÃo sendo propostos e fornecem gerenciamento de documentos XML. A maioria destes trabalhos, todavia, nÃo oferecem um controle de concorrÃncia eficiente para dados distribuÃdos. Outros trabalhos dÃo suporte ao controle distribuÃdo de dados XML, mas estes possuem protocolos com baixo grau de concorrÃncia e limitaÃÃes. Para prover um gerenciamento eficaz em ambientes distribuÃdos, este trabalho apresenta o DTX, como mecanismo para o controle de concorrÃncia distribuÃdo para dados XML, que leva em consideraÃÃo caracterÃsticas estruturais destes dados. O DTX visa a um gerenciamento eficaz de dados XML e contemplar as propriedades de isolamento e consistÃncia em transaÃÃes, utilizando um protocolo para controle de concorrÃncia multigranular que aumenta o paralelismo entre as transaÃÃes e possui uma estrutura otimizada para representaÃÃo dos dados. A soluÃÃo proposta possui uma arquitetura modular e flexÃvel, o que facilita sua integraÃÃo com diferentes estruturas de armazenamento XML, alÃm de poder ser estendido, adicionando novos recursos. Para validar o DTX, diversos testes foram feitos, comparando o DTX descrito neste trabalho com uma variaÃÃo do DTX, utilizando um protocolo de maior granulosidade, visando a simular as estratÃgias dos trabalhos relacionados. Os resultados obtidos atestam a eficÃcia do DTX, considerando diferentes aspectos em transaÃÃes distribuÃdas a dados XML, melhorando o desempenho, ou seja, o tempo de execuÃÃo destas transaÃÃes. / XML has become a widely used standard for data representation and exchange among Web applications. Consequently, a large volume of such data is distributed all over the Web and stored using several persistence methods. DBMSs provide concurrency control techniques to manage data. However, the structure of XML data makes it difficult to use these techniques. Projects are being proposed and they provide management of XML documents. Nevertheless, most of these projects do not provide efficient concurrency control mechanisms for distributed data. Some of them do provide support for distributed control of XML data, but use protocols that have limitations and offer low concurrency levels. In order to provide effective data management in distributed environments, we present DTX, a distributed concurrency control mechanism for XML data that takes into account its structural characteristics. DTX aims to provide effective management of XML data and contemplate properties such as isolation and consistency in transactions, using a multi-granular concurrency control protocol that increases parallelism among transactions and that has an optimized structure for data representation. DTX has a modular and flexible architecture, allowing for easy integration with any XML storage mechanisms. Moreover, DTX can be extended by adding new features to it. In order to evaluate DTX, several experiments were conducted comparing DTX as it is with a variation of DTX that uses a fine-grained protocol, in an attempt to simulate existing strategies in related work. Results confirm DTXâs effectiveness considering different aspects of distributed transactions on XML data, improving their performance, i.e., transaction execution time.

Safety is a well-known and important class of property of software programs, and of systems in general. The basic notion that informs this work is that the time to think about safety is when it still exists but could be lost. The notion is not just to analyse safety as existing or not with a given system state, but also in the sense that a system is presently safe but becoming less so. Safety as considered here is not restricted to one type of property, and indeed for much of the discussion it does not matter what types of measures are used to assess safety. The work done here is for the purpose of laying a theoretical and mathematical foundation for allowing static analyses of systems to further safety. This is done using tools from lattice theory applied to the poset of system states partially ordered by reachability. Such analyses are common (e.g., with abstract interpretations of software functioning) with respect to other kinds of systems, but there does not seem to exist a formalism that permits them specifically for safety. Using the basic analytical tools developed, a study is made of the problem of composing systems from components. Three types of composition: direct sum, direct product, and exponentiation---are noted, and the first two are treated in some depth. It is shown that the set of all systems formed with the direct sum and direct product operators can be specified by a BNF grammar. A three-valued ``safety logic'' is specified, using which the safety and fault-tolerance of composed systems can be computed given the system composition. It is also shown that the set of all systems also forms separate monoids (in the sense familiar to mathematicians), and that other monoids can be derived based on equivalence classes of systems. The example of a train approaching a railroad crossing, where a gate must be closed prior to the train's arrival and opened after its exit, is considered and analysed as an example.

<p>Wireless Sensor nodes fall somewhere in between the single application devices that do</p><p>not need an operating system, and the more capable, general purpose devices with the</p><p>resources to run a traditional embedded operating system. Sensor node operating system</p><p>such as TinyOS, Contiki, MantisOS and SOS which is discussed in this paper exhibit</p><p>characteristics of both traditional embedded systems and general-purpose operating systems</p><p>providing a limited number of common services for application developers linking</p><p>software and hardware.</p><p>These common services typically include platform support, hardware management of sensors,</p><p>radios, and I/O buses and application construction etc. They also provide services</p><p>needed by applications which include task coordination, power management, adaptation</p><p>to resource constraints, and networking. The evaluation was concentrated on TinyOS</p><p>including an analysis on version 1.x and 2.x resource management and flexibility and its</p><p>operation with the other wireless sensor node operating systems.</p>

Concurrency is concerned with systems of multiple computing agents that interact with each other. Bisimilarity is one of the main representatives of these. Concurrent Constrain Programming (ccp) is a formalism that combines the traditional and algebraic view of process calculi with a declarative one based upon first-order logic. The standard definition of bisimilarity is not completely satisfactory for ccp since it yields an equivalence that is too fine grained. By building upon recent foundational investigations, we introduce a labeled transition semantics and a novel notion of bisimilarity that is fully abstract w.r.t. the observational equivalence in ccp. When the state space of a system is finite, the ordinary notion of bisimilarity can be computed via the partition refinement algorithm, but unfortunately, this algorithm does not work for ccp bisimilarity. Hence, we provide an algorithm that allows us to verify strong bisimilarity for ccp, modifying the algorithm by using a pre-refinement and a partition function based on the irredundant bisimilarity. Weak bisimilarity is a central behavioral equivalence in process calculi and it is obtained from the strong case by taking into account only the actions that are observable in the system. Typically the standard partition refinement can also be used for deciding weak bisimilarity simply by using Milner's reduction from weak to strong; a technique referred to as saturation. We demonstrate that the above-mentioned saturation technique does not work for ccp. We give a reduction that allows us to use the ccp partition refinement algorithm for deciding this equivalence.

We present Roko, a system that allows parallelization of sequential C codes with a modest user intervention. The user exposes parallelism at the function level by annotating the code with pragmas. Roko defines only two pragmas: the parallel pragma is used to denote function calls that will be executed asynchronously, and the exposed pragma is used to describe data usage of the marked function calls. Architecturally, Roko consists of three components: a compiler that analyzes pragmas, a software environment that spreads the execution over multiple processors, and a hardware support that implements a novel synchronization scheme, versioning. We have designed, implemented and evaluated an FPGA-based prototype of Roko. Our experimental evaluation shows: (i) that few simple pragmas are all that is needed to expose parallelism in benchmark applications and (ii) that Roko can deliver good performance in terms of application speedup.

We present Roko, a system that allows parallelization of sequential C codes with a modest user intervention. The user exposes parallelism at the function level by annotating the code with pragmas. Roko defines only two pragmas: the parallel pragma is used to denote function calls that will be executed asynchronously, and the exposed pragma is used to describe data usage of the marked function calls. Architecturally, Roko consists of three components: a compiler that analyzes pragmas, a software environment that spreads the execution over multiple processors, and a hardware support that implements a novel synchronization scheme, versioning. We have designed, implemented and evaluated an FPGA-based prototype of Roko. Our experimental evaluation shows: (i) that few simple pragmas are all that is needed to expose parallelism in benchmark applications and (ii) that Roko can deliver good performance in terms of application speedup.