Systems and methods for constructing composable persistent data structures
US10007581B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jan 5, 2016 |
| Grant date | Jun 26, 2018 |
| Priority date | — |
| Expiry date | May 29, 2036 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2201/86
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A technique referred to as “data structure chronicles” is described that may be used to build strictly failure resilient persistent concurrent data structures. A “chronicle” maintains a persistent history of operations invoked on a persistent data structure that can be replayed to recover the current consistent state of the data structure after a failure. The chronicle technique may also enable composability of data structure operations with the enclosing application. In addition, the chronicle technique is non-blocking, a desirable progress condition for concurrent data structures. A lock free, non-blocking chronicle stack algorithm is described that may outperform a lock-based implementation in the presence of high contention. In addition, a lock free, non-blocking chronicle queue algorithm is described.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.