Patent ID: 9652302
Date: 2017-05-16
CPC Classifications: G06F

Claim:
1. A method for building a concurrent data structure in a form of a ranked register, RR, wherein rr-read and rr-write operations are defined within the RR, each of the rr-read operations takes a rank as argument and returns a rank-value pair, each of the rr-write operations takes a rank-value pair as argument and returns either commit or abort, each of the rr-read operations returns a rank-value pair that was written in a previous rr-write operation, one of the rr-write operations W=rr-write(r_1, v) commits and one of the rr-read operations R=rr-read(r_2), such that r_2>r_1, R returns (r′,v′), wherein r′>=r_1, wherein v and v′ are values, and wherein r′, r_2 and r_1 are ranks, based on a rr-write operation W invoked with rank r_1 aborting, invoking one of the rr-read or rr-write operations with rank r_2>r_1 before W returns, based on one of the rr-read or rr-write operations being invoked by a non-faulty process, eventually returning the one of the rr-read or rr-write operations invoked by the non-faulty process, and wherein the building of the RR is based on a Compare-And-Swap, CAS, functionality so as to store increasing versions of values within data objects and to ensure that newer values are never overwritten with older ones.