Distributed Computing with Modern Shared Memory

In this thesis, we revisit classic problems in shared-memory distributed computing through the lenses of (1) emerging hardware technologies and (2) changing requirements. Our contributions consist, on the one hand, in providing a better understanding of the fundamental benefits and limitations of new technologies, and on the other hand, in introducing novel, efficient tools and systems to ease the task of leveraging new technologies or meeting new requirements. First, we look at Remote Direct Memory Access (RDMA), a networking hardware feature which enables a computer to access the memory of a remote computer without involving the remote CPU. In recent years, the distributed computing community has taken an interest in RDMA due to its ultra-low latency and high throughput and has designed systems that take advantage of these characteristics. However, we argue that the potential of RDMA for distributed computing remains largely untapped. We show that RDMAâs unique semantics enable agreement algorithms which improve on fundamental trade-offs in distributed computing between performance and failure-tolerance. Furthermore, we show the practical applicability of our theoretical results through Mu, a state machine replication system which can replicate requests in under 2 microseconds, and can fail-over in under 1 millisecond when failures occur. Muâs replication and fail-over latencies are at least 61% and 90% lower, respectively, than those of prior work. Second, we focus on persistent memory, a novel class of memory technologies which is only now starting to become available. Persistent memory provides byte-addressable persistent storage with access times comparable to traditional DRAM. Recent work has focused on designing tools for working with persistent memory, but little is known about the fundamental cost of providing consistency in persistent memory. Furthermore, important shared-memory primitives do not yet have efficient persistent implementations. We provide an answer to the former question through a tight bound on the number of persistent fences required to implement a lock-free persistent object. We address the latter problem by presenting a novel efficient multi-word compare-and-swap algorithm for persistent memory. Third and finally, we consider the current exponential increase in the amount of data worldwide. Memory capacity has been on the rise for decades, but remains scarce when compared to the rate of data growth. Given this scarcity and the prevalence of concurrent in-memory processing, the classic problem of concurrent memory reclamation remains highly relevant to this day. Previous work in this area has produced solutions which are either (a) fast but easily disrupted by process delays, or (b) slow but robust to process delays. We combine the best of both worlds in QSense, a memory reclamation algorithm which is fast in the common case when there are no process delays and falls back to a robust reclamation algorithm when process delays prevent the fast path from making progress.

Constraint consistency techniques for continuous domains

Jamila Sam

Constraint Satisfaction Problems (CSPs) are ubiquitous in computer science. Many problems, ranging from resource allocation and scheduling to fault diagnosis and design, involve constraint satisfaction as an essential component. A CSP is given by a set of variables and constraints on small subsets of these variables. It is solved by finding assignments of values to the variables such that all constraints are satisfied. In its most general form, a CSP is combinatorial and complex. In this thesis, we consider constraint satisfaction problems with variables in continuous, numerical domains. Contrary to most existing techniques, which focus on computing a single optimal solution, we address the problem of computing a compact representation of the space of all solutions that satisfy the constraints. This has the advantage that no optimization criterion has to be formulated beforehand, and that the space of possibilities can be explored systematically. In certain applications, such as diagnosis and design, these advantages are crucial. In consistency techniques, the solution space is represented by labels assigned to individual variables or combinations of variables. When the labeling is globally consistent, each label contains only those values or combinations of values which appear in at least one solution. This kind of labeling is a compact, sound and complete representation of the solution space, and can be combined with other reasoning methods. In practice, computing a globally consistent labeling is too complex. This is usually tackled in two ways. One way is to enforce consistencies locally, using propagation algorithms. This prunes the search space and hence reduces the subsequent search effort. The other way is to identify simplifying properties which guarantee that global consistency can be enforced tractably using local propagation algorithms. When constraints are represented by mathematical expressions, implementing local consistency algorithms is difficult because it requires tools for solving arbitrary systems of equations. In this thesis, we propose to approximate feasible solution regions by 2k-trees, thus providing a means of combining constraints logically rather than numerically. This representation, commonly used in computer vision and image processing, avoids using complex mathematical tools. We propose simple and stable algorithms for computing labels of arbitrary degrees of consistency using this representation. For binary constraints, it is known that simplifying convexity properties reduces the complexity of solving a CSP. These properties guarantee that local degrees of consistency are sufficient to ensure global consistency. We show how, in continuous domains, these results can be generalized to ternary and in fact arbitrary n-ary constraints. This leads to polynomial-time algorithms for computing globally consistent labels for a large class of constraint satisfaction problems with continuous variables. We describe and justify our representation of constraints and our consistency algorithms. We also give a complete analysis of the theoretical results we present. Finally, the developed techniques are illustrated using practical examples.

EPFL1995

Concurrency and dynamic protocol update for group communication middleware

Olivier Rütti

The last three decades have seen computers invading our society: computers are now present at work to improve productivity and at home to enlarge the scope of our hobbies and to communicate. Furthermore, computers have been involved in many critical systems such as anti-locking braking systems (ABS) in our cars, airplane control systems, space rockets, nuclear power plants, banking and trading systems, medical care systems, and so on. The importance of these systems requires a high level of trust in computer-based systems. For example, a failure in a trading system (even if it is temporary) may result in severe economical losses. Hence coping with failures is a key aspect of computer systems. A common approach to tolerate failures is to replicate a system that provides a critical service, so that once a failure occurs on a given replica, the requests to the critical service are still executed by other replicas. This approach has the advantage of masking failures, i.e., requests to the service are continuously executed even in the presence of failures. However, replication introduces a performance cost, mainly because the execution of the service requests must be coordinated among all replicas. Furthermore, despite its apparent simplicity, replication is rather complex to implement. Replication is made easier by group communication which defines several abstractions that can be used by the designer of replicated systems. The group communication abstractions are implemented by distributed protocols that compose a group communication middleware. The aim of the thesis is to study two techniques to improve the performance of group communication middleware, and thus, reduce the cost of replication. First, we study dynamic protocol update, which allows group communication middleware to adapt to environment changes. More particularly, dynamic protocol update consists in replacing at runtime a given protocol composing the group communication middleware with a similar but more efficient protocol. The thesis provides several solutions to dynamic protocol update. For instance, we describe two algorithms to dynamically replace consensus and atomic broadcast, two essential protocols of a group communication middleware. Second, we propose solutions to introduce concurrency within a group communication middleware in order to benefit from the advantages offered by multiprocessor (or multicore) computers.

EPFL2009

Concurrency and dynamic protocol update for group communication middleware

Olivier Rütti

EPFL2009

Constraint consistency techniques for continuous domains

Jamila Sam

EPFL1995