Software rollout is the process of replacing the version of an application that is currently running in production with a new version. Many subtle and catastrophic bugs occur during software rollout. There are many existing techniques to improve the odds of a rollout completing successfully, but these techniques don't work well when the application has shared, persistent, mutable state. In this paper, we present a practical framework to test the rollout of stateful applications. Our framework uses diff testing to verify that the new version of an application behaves identically to the currently running version that will be replaced. The framework has three main components to safely and efficiently compare the behavior of the two versions. First, we implement database branching on top of Postgres. Second, we implement an efficient algorithm to diff two database branches. Third, we describe how to replay client requests to improve test coverage. Finally, we identify three common categories of rollout bugs and demonstrate how our framework can find these bugs with minimal performance overhead.

When writing a distributed application, conventional wisdom says to split your application into separate services that can be rolled out independently. This approach is well-intentioned, but a microservices-based architecture like this often backfires, introducing challenges that counteract the benefits the architecture tries to achieve. Fundamentally, this is because microservices conflate logical boundaries (how code is written) with physical boundaries (how code is deployed). In this paper, we propose a different programming methodology that decouples the two in order to solve these challenges. With our approach, developers write their applications as logical monoliths, offload the decisions of how to distribute and run applications to an automated runtime, and deploy applications atomically. Our prototype implementation reduces application latency by up to 15× and reduces cost by up to 9× compared to the status quo.

Since the design of lock-free data structures often poses a formidable intellectual challenge, researchers are constantly in search of abstractions and primitives that simplify this design. The multiword LL/SC object is such a primitive: many existing algorithms are based on this primitive, including the nonblocking and wait-free universal constructions [1], the closed objects construction [4] and the snapshot algorithms [12, 13]. In this paper, we consider the problem of implementing a W-word LL/SC object shared by N processes. The previous best algorithm, due to Anderson and Moir [1], is time optimal (LL and SC operations run in O(W) time), but has a space complexity of O(N²W). We present an algorithm that uses novel buffer management ideas to cut down the space complexity by a factor of N to O(NW), while still being time optimal.

Over the past decade, a pair of synchronization instructions known as LL/SC has emerged as the most suitable set of instructions to be used in the design of lock-free algorithms. However, no existing multiprocessor system supports these instructions in hardware. Instead, most modern multipro-cessors support instructions such as CAS or RLL/RSC (e.g. POWER4, MIPS, SPARC, IA-64). This paper presents two efficient algorithms that implement 64-bit LL/SC from 64-bit CAS or RLL/RSC. Our re~ults are summarized as fol-lows. We present a practical algorithm for implementing a 64-bit LL/SC object from 64-bit CAS or RLL/RSC objects. Our result shows, for the first time, a practical way of simu-lating a 64-bit LL/SC memory word using 64-bit CAS mem-ory words (or 64-bit RLL/RSC memory words), incurring only a small constant space overhead per process and a small constant factor slowdown. Although our first solution performs correctly in any practical system, its theoretical correctness depends on un-bounded sequence numbers. We present a bounded algo-rithm that implements a 64-bit LL/SC object from 64-bit CAS or RLL/RSC objects, and has the same time and space complexities as the first algorithm. This and the previous algorithm improve on existing im-plementations of LL/SC objects by Anderson and Moir in 1995, and Moir in 1997. 1.

In the group mutual exclusion problem [6], which generalizes mutual exclusion [2], a process chooses a session when it requests entry to the Critical Section. A group mutual exclusion algorithm must ensure that the mutual exclusion property holds: If two processes are in the Critical Section at the same time, then they request the same session. In addition to mutual exclusion, lockout freedom, bounded exit and concurrent entering are basic properties that are desirable in any group mutual exclusion algorithm.Hadzilacos in [4] first introduced a fairness condition, called first-come-first-served (FCFS), for group mutual exclusion. The only known FCFS group mutual exclusion algorithm is due to Hadzilacos [4], and requires Θ(N2) bounded shared registers, where N is the number of processes. We present a FCFS group mutual exclusion algorithm that uses only Θ(N) bounded shared registers. (The existence of such an algorithm was posed as an open problem by Hadzilacos.)Next, we demonstrate that the FCFS property does not fully capture our intuitive notion of fairness. We therefore propose an additional fairness property, called first-in-first-enabled (FIFE). Finally, we present a reduction that transforms any FCFS mutual exclusion algorithm M into a group mutual exclusion algorithm G. Thus, different group mutual exclusion algorithms can be obtained by instantiating M with different abortable FCFS mutual exclusion algorithms. The group mutual exclusion algorithms so obtained satisfy all of the properties mentioned above: mutual exclusion, lockout freedom, bounded exit, concurrent entering, FCFS, and FIFE.