The distributed transactional memory (DTM) abstraction aims to simplify the development of distributed concurrent programs. It frees programmers from the complicated and error-prone task of explicit concurrency control based on locks (e.g., deadlocks, livelocks, non-scalability, non-composability), which are aggravated in a distributed environment due to the complexity of multi-node concurrency. At its core, DTM's atomic section-based synchronization abstraction enables the execution of a sequence of multi-node object operations with the classical serializability property, which significantly increases the programmability of distributed systems. In this thesis, we present the first ever DTM framework for distributed concurrency control in C++, called HyflowCPP. HyflowCPP provides distributed atomic sections, and pluggable support for concurrency control algorithms, directory lookup protocols, contention management policies, and network communication protocols. The framework uses the Transaction Forwarding Algorithm (or TFA) for concurrency control. While there exists implementations of TFA and other DTM concurrency control algorithms in Scala and Java, and concomitant DTM frameworks (e.g., HyflowJava, HyflowScala, D2STM, GenRSTM), HyflowCPP provides a uniquely distinguishing TFA/DTM implementation for C++. Also, HyflowCPP supports strong atomicity, transactional nesting models including closed and open nesting (supported using modifications to TFA), and checkpointing. We evaluated HyflowCPP through an experimental study that measured transactional throughput for a set of micro- and macro-benchmarks, and comparing with competitor DTM frameworks. Our results revealed that HyflowCPP achieves up to 600% performance improvement over competitor Java DTM frameworks including D2STM, GenRSTM, HyflowScala and HyflowJava, which can be attributed to the competitors' JVM overhead and rudimentary networking support. Additionally, our experimental studies revealed that checkpointing achieves up to 100% performance improvement over flat nesting and 50% over closed nesting. Open nesting model achieves up to 140% performance improvement over flat nesting and 90% over closed nesting. / Master of Science

京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第20893号 / 理博第4345号 / 新制||理||1624(附属図書館) / 京都大学大学院理学研究科物理学・宇宙物理学専攻 / (主査)准教授 篠本 滋, 教授 佐々 真一, 教授 川上 則雄 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

The quality and reliability of software systems, in terms of their functional correctness, critically relies on the effectiveness of the testing tools and techniques to detect errors in the system before deployment. A lack of testing tools for concurrent programs that systematically control thread scheduling choices has not allowed concurrent software development to keep abreast with hardware trends of multi-core and multi-processor technologies. This motivates a need for the development of systematic testing techniques that detect errors in concurrent programs. The work in this dissertation presents a potentially scalable technique that can be used to detect concurrency errors in production code. The technique is a viable solution for software engineers and testers to detect errors in multi-threaded programs before deployment. We present a guided testing technique that combines static analysis techniques, systematic verification techniques, and heuristics to efficiently detect errors in concurrent programs. An abstraction-refinement technique lies at the heart of the guided test technique. The abstraction-refinement technique uses as input potential errors in the program generated by imprecise, but scalable, static analysis tools. The abstraction further leverages static analyses to generate a set of program locations relevant in verifying the reachability of the potential error. Program execution is guided along these points by ranking both thread and data non-determinism. The set of relevant locations is refined when program execution is unable to make progress. The dissertation also discusses various heuristics for effectively guiding program execution. We implemented the guided test technique to detect errors in Java programs. Guided test successfully detects errors caused by thread schedules and data input values in Java benchmarks and the JDK concurrent libraries for which other state of the art analysis and testing tools for concurrent programs are unable to find an error.

Complex concurrent APIs are difficult to reason about annually due to the exponential growth in the number of feasible schedules. Testing against reference solutions of these APIs is equally difficult as reference solutions implement an unknown set of allowed behaviors, and programmers have no way to directly control schedules or API internals to expose or reproduce errors. The work in this paper mechanically generates a drop-in replacement for a concurrent API from a formal specification. The specification is a guarded command system with first-order logic that is compiled into a core calculus. The term rewriting system is connected to actual C programs written against the API through lightweight wrappers in a role-based relationship with the rewriting system. The drop-in replacement supports putative what-if queries over API scenarios for behavior exploration, reproducibility for test and debug, full exhaustive search and other advanced model checking analysis methods for C programs using the API. We provide a Racket instantiation of the rewriting system with a C/Racket implementation of the role-based architecture and validate the process with an API from the Multicore Association.

My research has been on the development of concurrent algorithms for shared memory systems that provide guarantees of progress. Research into such algorithms is important to developers implementing applications on mission critical and time sensitive systems. These guarantees of progress provide safety properties and freedom from many hazards, such as dead-lock, live-lock, and thread starvation. In addition to the safety concerns, the fine-grained synchronization used in implementing these algorithms promises to provide scalable performance in massively parallel systems. My research has resulted in the development of wait-free versions of the stack, hash map, ring buffer, vector, and a multi-word compare-and-swap algorithms. Through this experience, I have learned and developed new techniques and methodologies for implementing non-blocking and wait-free algorithms. I have worked with and refined existing techniques to improve their practicality and applicability. In the creation of the aforementioned algorithms, I have developed an association model for use with descriptor-based operations. This model, originally developed for the multi-word compare-and-swap algorithm, has been applied to the design of the vector and ring buffer algorithms. To unify these algorithms and techniques, I have released Tervel, a wait-free library of common algorithms and containers. This library includes a framework that simplifies and improves the design of non-blocking algorithms. I have reimplemented several algorithms using this framework and the resulting implementation exhibits less code duplication and fewer perceivable states. When reimplementing algorithms, I have adapted their Application Programming Interface (API) specification to remove ambiguity and non-deterministic behavior found when using a sequential API in a concurrent environment. To improve the performance of my algorithm implementations, I extended OVIS's Lightweight Distributed Metric Service (LDMS)'s data collection and transport system to support performance monitoring using perf_event and PAPI libraries. These libraries have provided me with deeper insights into the behavior of my algorithms, and I was able to use these insights to improve the design and performance of my algorithms.

I syfte att skapa beslutsunderlag vid val av programmeringsspråk granskas och utvärderas Javas och C++ mekanismer för parallell programkörning. Åtta testprogram skapas i syfte att undersöka vilka prestandamässiga skillnader som visar sig i tre testmiljöer. Resultatet visar att kompilerade språk överlag är snabbare än interpreterade diton med vissa intressanta avvikelser.

Standard operational semantics of the majority of concurrency models is defined in terms of either sequences or step sequences, while standard concurrent history semantics is usually defined in terms of partial orders, stratified order structures (or structures equivalent to them as net processes). It is commonly assumed (first argued by N. Wiener in 1914) that any system run (execution) that can be observed by a single observer must be an interval order of event occurrences. However, generating interval orders directly is problematic for most models of concurrency, as the only feasible sequence representation of interval order is by using Fishburn Theorem (1970) and appropriate sequences of beginnings and endings of events involved. It was shown by Janicki and Koutny in 1997 that concurrent histories involving interval orders can be represented by interval order structures, but how these interval order structures could be derived for particular concurrent systems was not clear. My original contribution to knowledge is defining an interval order semantics for Petri Nets with Inhibitor Arcs. We start with introducing operational interval order semantics, and then we generalize the concept of net process to represent the set of equivalent executions modelled by interval orders. Next we will show that our interval processes correspond to appropriate interval order structures. Finally, we will prove that our model is equivalent to that of Janicki and Yin (2015) where novel interval traces are used to represent equivalent executions. We will also demonstrate that our model covers simpler cases where sequences or step sequences were used to represent system runs. / Thesis / Doctor of Philosophy (PhD)

No description available.

As more and more companies use the internet to grow their businesses and sales, it is crucial to have a fast and responsive site that keeps customers on the site. Hence, comparing two web frameworks with respect to response time is vital, as it is a significant part of delivering the page. The comparison will help developers to choose between Express.js and Ktor. Our research shows how the two frameworks, Ktor and Express.js, compare in response times for static and dynamic pages for a set of concurrent users. The comparison will explain how the frameworks’ response times change when having a different number of concurrent users and delivering static vs. dynamic content. An experiment with Locust was conducted to obtain the data needed to show the differences in response time for the two frameworks. Additionally, a literature study was conducted to find the best way to structure the servers, design the tests, and find information on how the frameworks should perform. We found that Express.js has an overall better response time than Ktor. At the same time, it was found that the Object Relational Mapper used with Ktor affected result more than the Object Relational Mapper used with Express.js. Hence, we conclude that Express.js is the better choice, but since both frameworks had low response times, we would say that even Ktor is a valid choice.

Formal studies of models of concurrency are usually focused on two major models: Interleaving abstraction (Bergstra, 2001; Milner, 1990) and partially ordered causality (Diekert and Rozenberg, 1995; Jensen, 1997; Reisig, 1998). Although very mature, these models retain a known limitation: Neither of them can model the “not later than” relationship effectively, which causes problems with specifying priorities, error recovery, time testing, inhibitor nets, etc. See for reference: Best and Koutny (1992); Janicki (2008); Janicki and Koutny (1995); Juhas et al. (2006); Kleijn and Koutny (2004). A solution, proposed independently (in this order) in (Lamport, 1986; Gaifman and Pratt, 1987) and (Janicki and Koutny, 1991), suggests to model concurrent behaviours by an ordered structure, i.e. a triple (X, R1, R2), where X is the set of event occurrences, and R1 and R2 are two binary relations on X. The relation R1 is interpreted as “causality”, i.e. an abstraction of the “earlier than” relationship, and R2 is interpreted as “weak causality”, an abstraction of the “not later than” relationship. For ordered structures’ model, the following two kinds of relational structures are of special importance: stratified order structures (SO-structures) and interval order structures (IO-structures). The SO-structures can fully model concurrent behaviours when system executions (operational semantics) are described in terms of stratified orders, while the IO-structures can fully model concurrent behaviours when system executions are described in terms of interval orders (Janicki, 2008; Janicki and Koutny, 1997). It was argued in (Janicki and Koutny, 1993), and also implicitly in a 1914 Wiener’s paper Wiener (1914), that any execution that can be observed by a single observer must be an interval order. Thus, IO-structures provide a very definitive model of concurrency. However, the theory of IO-structures remains far less developed than its simpler counterpart - the theory of SO-structures. One of the most important concepts lying at the core of partial orders and algebraic structures theory is the concept of transitive closure of relations. The equivalent of transitive closure for SO-structures, called <>-closure, has been proposed in (Janicki and Koutny, 1995) and consequently used in (Janicki and Koutny, 1995; Juhas et al., 2006; Kleijn and Koutny, 2004) and others. However, a similar concept for IO-structures has not been proposed. In this thesis we define that concept. We introduce the transitive closure for IO-structures, called the []-closure. We prove that it has same properties as the standard transitive closure for partial orders and []-closure for SO-structures (published in Janicki and Zubkova (2009); Janicki et al. (2009)), and provide some comparison of different versions of transitive closure used in various relational structures. Some properties of another recently introduced *-closure (Janicki et al., 2013) are also discussed. / Thesis / Master of Science (MSc)