We have the pleasure to announce a seminar by Jennifer Welch (Texas A&M University) about her work on Message-Passing Implementations of Shared Data Structures.

Abstract: Distributed storage, or shared data, is a vital mechanism for communication among processes in distributed systems, and facilitates the development of higher-level applications. Although shared data is a convenient abstraction, it is not generally provided in large-scale distributed systems. Instead, processes keep individual copies of the data, and communicate by sending messages to keep the copies consistent. After providing background on this topic, we will focus (separately) on two intriguing aspects: systems that experience churn, where the set of participating processes changes dynamically; and target data structures whose specifications are relaxed.

We will present a recent algorithm for implementing a shared register in a dynamic system with ongoing churn that works in an asynchronous system. The algorithm is correct as long as the number of processes entering and leaving during a fixed time interval is at most a constant fraction of the current system size. The algorithm tolerates process crashes as long as the number of failed processes in the system is at most a constant fraction of the current system size. We also show a lower bound on the crash-resilience for this problem. This work is by Attiya, Chung, Ellen, Kumar, and Welch.

Finally, we will consider distributed implementations of shared data structures with relaxed specifications. Strongly consistent implementations of shared objects with strict semantics are provably expensive, fueling interest in relaxations. A data type relaxation adds a small amount of non-determinism to the specification which can reduce the required frequency of expensive synchronization. We will present recent algorithms for different kinds of relaxed queues as well as lower bounds on the worst-case and amortized operation latency for the problem. Our results show that the algorithms are asymptotically optimal and that there is an inherent complexity gap between different levels of relaxation. This work is by Byrnes, Talmage, and Welch.