BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Message-Passing Implementations of Shared Data Structures Welch, Jennifer


Distributed storage, or shared data, is a vital mechanism for communication among processors in distributed systems, and facilitates the development of higher-level applications. Although shared data is a convenient abstraction, it is not generally provided directly in large-scale distributed systems but must be implemented on top of message-passing. In this talk, I will present an overview of some recent results by my colleagues and myself on the time complexity of operations on linearizable shared objects that are implemented on top of a partially synchronous message-passing system. First, we extend previous efforts to develop classifications of operations on shared objects based on axioms describing how the operations interact with each other. One classification facilitates the development of a general algorithm for implementing objects of any type in which the latency of operations improves on that of prior folklore algorithms. Using another classification, we prove lower bounds on several classes of operations which show that in a number of common cases, our algorithm is tight or almost tight. Second, we consider the popular idea of relaxing the specifications of data types in order to improve performance, in the context of message-passing implementations. We focus on a shared queue with a level of relaxation indicated by a parameter k, proposed by Henzinger et al. We show that, unfortunately, the worst-case time for a dequeue on this relaxed queue is almost as bad as in the unrelaxed case. However, there is an algorithm in which the amortized time for a dequeue decreases linearly as k increases, behavior which we prove is not attainable in the unrelaxed case. We also show that improved amortized performance as k increases is inherent.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International