- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Message-Passing Implementations of Shared Data Structures
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Message-Passing Implementations of Shared Data Structures Welch, Jennifer
Description
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 Metadata
| Title |
Message-Passing Implementations of Shared Data Structures
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2016-11-30T11:35
|
| Description |
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.
|
| Extent |
22 minutes
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: Texas A & M University
|
| Series | |
| Date Available |
2017-06-23
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0348586
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Faculty
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International