Modern computing systems typically relax execution determinism, for instance by allowing the CPU scheduler to inter- leave the execution of several threads. While beneficial for performance, execution non-determinism affects programs' execution traces and hampers the comparability of repeated executions. We present TraceSanitizer, a novel approach for execution trace comparison in Error Propagation Analyses (EPA) of multi-threaded programs. TraceSanitizer can identify and compensate for non- determinisms caused either by dynamic memory allocation or by non-deterministic scheduling. We formulate a condition under which TraceSanitizer is guaranteed to achieve a 0% false positive rate, and automate its verification using Satisfiability Modulo Theory (SMT) solving techniques. TraceSanitizer is comprehensively evaluated using execution traces from the PARSEC and Phoenix benchmarks. In contrast with other approaches, Trace- Sanitizer eliminates false positives without increasing the false negative rate (for a specific class of programs), with reasonable performance overheads.

Scaling out database management systems (DBMSs) requires distributed coordination, which can easily become a bottleneck. Recent work on speeding up distributed transactions has addressed this problem by proposing scale-out techniques that are deeply integrated with the concurrency control mechanism of the DBMS. This paper explores the design of modular coordination layers, which encapsulate all scale-out logic and can be applied to scale out any unmodified single-server DBMS. It proposes Gyro, a modular coordination layer that runs on top of a collection of single-server DBMS instances and interacts with them only through their client interface. Gyro distributes the load by ensuring that as many requests as possible are executed by only one DBMS instance. Our experiments show that modular distributed coordination is practically viable and that it can be much faster than traditional distributed transaction protocols using two-phase commit.

Error Propagation Analysis (EPA) is a technique forunderstanding how errors affect a program's execution and resultin program failures. For this purpose, EPA usually compares thetraces of a fault-free (golden) run with those from a faulty run ofthe program. This makes existing EPA approaches brittle for multithreadedprograms, which do not typically have a deterministicgolden run. In this paper, we study the use of likely invariantsgenerated by automated approaches as alternatives for goldenrun based EPA in multithreaded programs. We present InvariantPropagation Analysis (IPA), an approach and a framework forautomatically deriving invariants for multithreaded programs, and using the invariants for EPA. We evaluate the invariantsderived by IPA in terms of their coverage for different faulttypes across six representative programs through fault injectionexperiments. We find that stable invariants can be inferred in allsix programs, although their coverage of faults depends on theapplication and the fault type.

The most prominent advantage of software verification over testing is a rigorous check of every possible software behavior. However, large state spaces of concurrent systems, due to non-deterministic scheduling, result in a slow automated verification process. Therefore, verification introduces a large delay between completion and deployment of concurrent software. This paper introduces a novel iterative approach to verification of concurrent programs that drastically reduces this delay. By restricting the execution of concurrent programs to a small set of admissible schedules, verification complexity and time is drastically reduced. Iteratively adding admissible schedules after their verification eventually restores non-deterministic scheduling. Thereby, our framework allows to find a sweet spot between a low verification delay and sufficient execution time performance. Our evaluation of a prototype implementation on well-known benchmark programs shows that after verifying only few schedules of the program, execution time overhead is competitive to existing deterministic multi-threading frameworks.

This paper presents efficient model checking of distributed software. Key to the achieved efficiency is a novel stateful model checking strategy that is based on the decomposition of states into a relevant and an auxiliary part. We formally show this strategy to be sound, complete, and terminating for general finite-state systems. As a case study, we implement the proposed strategy within Basset/MP-Basset, a model checker for message-passing Java programs. Our evaluation with actual deployed fault-tolerant message-passing protocols shows that the proposed stateful optimization is able to reduce model checking time and memory by up to 69% compared to the naive stateful search, and 39% compared to partial-order reduction.