The performance of transactional database systems is typically evaluated by measuring the amount of transactions they can commit to the database per second. However, fairly measuring this for the same workload on different systems is not trivial. It is therefore relevant to formalize schedule efficiency, investigate the space of all possible efficient schedules, and identify whether there is any room for improvement. Prior transaction theory largely centers on decision problems relating to safety, such as the serializability, robustness, and allocation problems. Most pertinently, these problems take already scheduled transactions as input, and do not directly consider the efficiency of those schedules. In this work, we define schedules as assignments of operations on objects to discrete points in time. This allows us to quantify efficiency as the elapsed duration between the schedule’s beginning and end, more commonly known as the makespan in the scheduling literature. We establish that, given some set of transactions and a desired makespan, it is NP-complete to decide if there exists a conflict serializable schedule which is bounded by that makespan. We additionally provide an instance optimal algorithm for scheduling transaction sets with a single contention point, that is, exactly one object may appear in conflicting operations. Lastly, we give worst-case optimal bounds on the makespan, meaning that schedules can never exceed this bound, and for the worst transaction sets, the bound is optimal.

The performance of multi-core transactional systems is a well-studied area, with the ultimate goal of optimizing the balance between high concurrency and the appearance of serial execution. In recent years, partitioning-based systems have shown that we can gain benefits from ahead-of-execution analysis on batches of transactions. However, this benefit is largely lost as contention increases. In this work, we investigate what it means for a batch to be executed optimally in the face of high contention. Intuitively, we will consider a schedule to be optimal if it minimizes the time spent waiting for exclusive access to tuples. We also design an algorithm that can optimally schedule batches, that satisfy particular properties, in quasi-linear time. We then implement it in a system called Cascade, and provide a preliminary evaluation against an existing system.

Programming asynchronous distributed systems is a challenging task in which consistency is often achieved by use of expensive coordination protocols like Paxos and 2PC. The CALM theorem, first conjectured by Hellerstein, is one of the first results to challenge this practice by stating that a problem can have a consistent, coordination-free distributed implementation if (and only if) the problem is monotonic. This result was proven for queries and shown to extend beyond monotonic (yet monotonic-like) queries for data systems having specific knowledge about the partitioning of data over the network. In this article, we extend the latter results in several ways. We consider problems that can be modeled as mappings from distributed instances to distributed instances, enabling insights into a much broader range of problems than queries. Furthermore, our model can express arbitrary system configurations, allowing us to reason about the expressiveness of any particular distributed system and thereby revealing a nuanced gradient of problems with increasing coordination-needs. Finally, we apply our model to a recent question about the expressiveness of coordination-free queries, raised by Hellerstein and Alvaro.