Join Jennifer L. Welch from Texas A&M University as she presents new research on shared data systems.
Invited Talk: Message-Passing Implementations of Shared Data Structures
Wednesday, October 24, 2018
12:30 p.m.
Brickyard (BYENG) 210, Tempe campus [map]
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.
This talk will cover background on the topic as well as two intriguing aspects: systems that experience churn, where the set of participating processes changes dynamically; and systems that target data structures whose specifications are relaxed.
Welch 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. Welch also shows a lower bound on the crash-resilience for this problem.
Finally, Welch discusses 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. The results show that the algorithms are asymptotically optimal and that there is an inherent complexity gap between different levels of relaxation.
About the speaker
Jennifer L. Welch is Regents Professor and Chevron Professor II in the Department of Computer Science and Engineering at Texas A&M University. She received her Master’s of Science and doctorate from the Massachusetts Institute of Technology and her Bachelors from the University of Texas at Austin. Her research interests include algorithms and lower bounds for distributed computing systems, especially distributed shared objects and dynamic networks.
