Linearizable Iterators for Concurrent Sets

This paper proposes a general framework for adding linearizable iterators to a class of data structures that implement set operations. We introduce a condition on set operations, called local consistency, which informally states that set operations never make elements unreachable to a sequential ite...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-03
Main Authors: Agarwal, Archita, Liu, Zhiyu, Rosenthal, Eli, Saraph, Vikram
Format: Article
Language:English
Subjects:
Data structures
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper proposes a general framework for adding linearizable iterators to a class of data structures that implement set operations. We introduce a condition on set operations, called local consistency, which informally states that set operations never make elements unreachable to a sequential iterator's traversal. We show that sets with locally consistent operations can be augmented with a linearizable iterator via the framework. Our technique is broadly applicable to a variety of data structures, including hash tables and binary search trees. We apply the technique to sets taken from existing literature, prove their operations are locally consistent, and demonstrate that iterators do not significantly affect the performance of concurrent set operations.
ISSN:2331-8422