Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Methods for Highly Concurrent Sets

IP.com Disclosure Number: IPCOM000247400D
Publication Date: 2016-Sep-01
Document File: 1 page(s) / 19K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method that allows threads to concurrently operate on the data structure while ensuring that the result is as if the threads sequentially executed.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 67% of the total text.

Page 01 of 1

Methods for Highly Concurrent Sets

Sets are a fundamental data structure used in a variety of applications to hold unique elements. Sets support three operations: add(element), remove(element), and contains (element). Many applications can have several threads that concurrently access the data structure.

Known lock-free methods require high overheads for each operation, including the common case for most applications: mostly read operations (e.g. contains (element)). These methods use only the widely popular compare-and-swap instructions. The compare-and-swap is used in add(element), remove(element) and contains(element) functions.

Another known method is blocking in the add(element) and remove(element) operations, but this is wait-free in the contains(element) operation, hence optimizing the common case of contains(element). The method uses locks only in the add(element), remove(element), but not in contains(element).

The novel contribution is a method that, instead of each thread waiting while another thread operating on the structure completes, allows threads to concurrently operate on the data structure while ensuring that the result is as if the threads sequentially executed. Allowing threads to concurrently execute on the data structure achieves better performance than sequential execution.

The novel method provides simpler and faster operations of add(element), remove(element) and contains(element) than any exiting algorithms while ensuring at least the s...