On-line services already form an important part of modern life with an immense potential for growth. Most of these services are supported by transactional systems, which are backed by database management systems (DBMS) in many cases. Many on-line services use replication to ensure high-availability, fault tolerance and scalability. Replicated systems typically consist of different nodes running the service co-ordinated by a distributed algorithm which aims to drive all the nodes along the same sequence of states by providing a total order to their operations. Thus optimization of both local DBMS operations through concurrency control and the distributed algorithm driving replicated services can lead to enhancing the performance of the on-line services. Deferred Update Replication (DUR) is a well-known approach to design scalable replicated systems. In this method, the database is fully replicated on each distributed node. User threads perform transactions locally and optimistically before a total order is reached. DUR based systems find their best usage when remote transactions rarely conflict. Even in such scenarios, transactions may abort due to local contention on nodes. A generally adopted method to alleviate the local contention is to invoke a local certification phase to check if a transaction conflicts with other local transactions already completed. If so, the given transaction is aborted locally without burdening the ordering layer. However, this approach still results in many local aborts which significantly degrades the performance. The first main contribution of this thesis is PXDUR, a DUR based transactional system, which enhances the performance of DUR based systems by alleviating local contention and increasing the transaction commit rate. PXDUR alleviates local contention by allowing speculative forwarding of shared objects from locally committed transactions awaiting total order to running transactions. PXDUR allows transactions running in parallel to use speculative forwarding, thereby enabling the system to utilize the highly parallel multi-core platforms. PXDUR also enhances the performance by optimizing the transaction commit process. It allows the committing transactions to skip read-set validation when it is safe to do so. PXDUR achieves performance gains of an order of magnitude over closest competitors under favorable conditions. Transactions also form an important part of centralized DBMS, which tend to support multi-threaded access to utilize the highly parallel hardware platforms. The applications can be wrapped in transactions which can then access the DBMS as per the rules of concurrency control. This allows users to develop applications that can run on DBMSs without worrying about synchronization. texttt{Serializability} is the de-facto standard form of isolation required by transactions for many applications. The existing methods employed by DBMSs to enforce serializability employ explicit fine-grained locking. The eager-locking based approach is pessimistic and can be too conservative for many applications. The locking approach can severely limit the performance of DBMSs especially for scenarios with moderate to high contention. This leads to the second major contribution of this thesis is TSAsR, an adaptive transaction processing framework, which can be applied to DBMSs to improve performance. TSAsR allows the DBMS's internal synchronization to be more relaxed and enforces serializability through the processng of external meta-data in an optimistic manner. It does not require any changes in the application code and achieves orders of magnitude performance improvements for high and moderate contention cases. The replicated transaction processing systems require a distributed algorithm to keep the system consistent by ensuring that each node executes the same sequence of deterministic commands. These algorithms generally employ texttt{State Machine Replication (SMR)}. Enhancing the performance of such algorithms is a potential way to increase the performance of distributed systems. However, developing new SMR algorithms is limited in production settings because of the huge verification cost involved in proving their correctness. There are frameworks that allow easy specification of SMR algorithms and subsequent verification. However, algorithms implemented in such framework, give poor performance. This leads to the third major contribution of this thesis Verified JPaxos, a JPaxos based runtime system which can be integrated to an easy to verify I/O automaton based on Multipaxos protocol. Multipaxos is specified in Higher Order Logic (HOL) for ease of verification which is used to generates executable code representing the Multipaxos state changes (I/O Automaton). The runtime drives the HOL generated code and interacts with the service and network to create a fully functional replicated Multipaxos system. The runtime inherits its design from JPaxos along with some optimizations. It achieves significant improvement over a state-of-art SMR verification framework while still being comparable to the performance of non-verified systems. / Master of Science

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.

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)

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.