Brief Announcement: Fork-Consistent Constructions From Registers

摘要

So far, all implementations providing fork-consistent semantics are based on objects with read-modify-write capabilities (also termed servers). We propose constructions of fork-consistent shared objects from single-writer multiple-reader (SWMR) read/write base registers, that are strictly weaker than servers. Our shared object constructions provide lin-earizability if all base registers behave correctly, and gracefully degrade to either fork-linearizability or weak fork-lin-earizability if any number of registers fails Byzantine. We make the following contributions: (a) A fork-linearizable construction of a universal type where operations are allowed to abort under concurrency, and (b) a weak fork-linearizable implementation of a shared memory that ensures wait-freedom when the registers are correct.